一種云計算環(huán)境下基于可變搜索樹的保序加密研究方案*

王小驥，楊 競，湯殿華，王 輝，劉 瑤

（中國電子科技集團公司第三十研究所，四川 成都 610041）

0 引 言

云計算是以互聯網為中心的一種技術，采用分布式計算、并行計算、網絡存儲和虛擬化等技術，將軟件、硬件計算和存儲等資源通過網絡連接，形成一種云狀的計算網絡，為用戶提供快速、便捷、自由的計算與存儲服務[1]。其與傳統的網絡應用模式相比，具有應用/資源虛擬化、動態(tài)可擴展、按需部署、靈活性高、可靠性高和性價比高等優(yōu)勢。云計算包括了很多服務[2]，其中最為廣泛的為基礎設施即服務（Infrastructure as a Service，IaaS）、平臺即服務（Platform as a Service，PaaS）和軟件即服務（Software as a Service，SaaS）3 種模式。云服務產生大量的個人隱私數據和商業(yè)信息等數據資源，由云服務器匯聚存儲。

由于云端服務器和用戶終端都在開放的網絡環(huán)境下運行，使得云端數據不可避免地面臨著安全風險和威脅。因此，如何在保證云端數據安全性和隱私性的前提下，在云計算環(huán)境下為用戶提供安全可靠的數據存儲和應用服務，成為亟待解決的問題[3]。

目前，在云計算環(huán)境下出于對隱私數據的保護，用戶終端一般先采用常規(guī)密碼算法對數據進行加密，再將密態(tài)數據存儲于云服務器，保證用戶的隱私數據的機密性，但同時也杜絕了在云端服務器操作用戶數據的可能性，當用戶需要對存儲在云端服務器或數據庫中的密文數據進行操作時，必須先下載至本地終端進行解密，然后才能執(zhí)行相應的操作。這種方式不僅增加了用戶操作成本，還加重了網絡和本地的負擔，極大地限制了云計算的處理能力。

近些年，結合云計算環(huán)境下對密文數據進行操作的使用需求[4]，密碼學家研究并提出了保序加密、密文檢索、同態(tài)加密等密碼體制及方案，從而實現密文狀態(tài)下的密文排序、密文檢索、密文計算等功能，通過綜合運用這些密碼算法，構建密文數據庫系統，為用戶提供安全的密文保障。其中，密文排序作為云計算安全的主要應用之一，通過保序加密密碼技術來實現。本文重點研究云計算環(huán)境的保序加密技術，通過對保序加密方案的特點進行分析，得到頻率隱藏保序加密方案的構造思路，設計了一種保序加密方案，實現云計算環(huán)境下的數據保序加密。此方案在為用戶隱私數據提供保護的同時，也能讓云服務器進行密文排序等操作。

目前，常見的Popa 方案[5]將二叉樹維持在一個B 樹的形態(tài)，具有較強的安全性，但是只要發(fā)生了數據的更新、插入或者刪除等操作，就需要對整個樹做平衡操作，時間消耗很大。文獻[6]提出可以使用非線性的加密算法實現索引加密，在數據庫中構造了索引結構，簡化數據庫檢索過程，提出了基于噪聲的非線性表達式，但是如果輸入的明文重復率很高，則很容易被推算出安全參數，影響算法的安全性。

1 保序加密概述

在云計算環(huán)境下，用戶終端一般將復雜的計算和存儲外包給云服務器。然而，不完全可信的云服務器可能會泄露用戶隱私。為保護用戶隱私數據，用戶采用傳統密碼算法對數據加密后，再外包存儲于云服務器，這些密文數據失去了原有的一些性質，無法對其進行范圍查詢。因此，在云計算環(huán)境下對密文數據實施范圍查詢提出需求，保序加密是滿足密文空間范圍查詢需求的有效方法。

1.1 系統模型

2004 年，Agrawal 等 人[7]首 次 提 出 保 序加密的概念，給出一種對數值型數據進行保序加密的方案（Order-Preserving Encryption Scheme，OPES）。保序加密系統模型主體一般包括數據擁有者、云服務器、數據使用者，如圖1 所示。

（1）數據擁有者。受限于存儲和計算能力，數據擁有者一般將外包數據進行加密后，上傳至云服務器存儲。為了保護數據可用性，數據擁有者將采用可保留明文原有特殊性質的加密方案來加密數據。

（2）數據使用者。對云服務器存儲的數據進行查詢時，數據使用者需要向數據擁有者索取密鑰，再將查詢請求發(fā)送給云服務器，收到查詢結果后，數據使用者對查詢結果進行解密。

（3）云服務器。根據數據使用者的查詢請求，云服務器在密文數據庫中進行檢索，將存儲結果發(fā)送給數據使用者。

1.2 形式化定義

定義1：保序加密方案可描述為多元組，為OPES=(Genk,Enc,Dec)。

其中，包含了密鑰生成算法Genk產生的密鑰K；加密算法Enc輸入密鑰K和明文M，輸出密文C；解密算法Dec輸入密鑰K和密文C，輸出明文M。對于每個明文M和密鑰K，需保證Dec(Enc(K,M))=M。

對于兩個隨機明文M0和M1及密鑰K，當M0≤M1時，Enc(K,M0)≤Enc(K,M1)， 則 稱這個方案為保序加密方案。

定義2：（有狀態(tài)）保序加密方案。

其中，S←KEYGEN(λ)為根據安全性參數λ生成秘密狀態(tài)S；S',y←ENCRYPT(S,x)為明文x計算密文y并將狀態(tài)從S更新到S'；x←DECRYPT(S,y)為基于狀態(tài)S通過密文y計算明文x。

如果對于任何有效狀態(tài)S和x，都滿足DECRYPT(ENCRYPT(S,x))=x，則加密方案是“正確”的。如果保留了順序（即對于任何i和j有yi≥yj?xi≤xj），則加密方案是“保序”的。

定義3：序列隨機化。

令n為序列S=x1,x2, … ,xi, …,x n(?i,xi∈N)中明文的個數。序列X滿足隨機化順序Y=y1,y2, … ,y n( ?i, 1 ≤yi≤n, ?i,j,i≠j?y i≠yj)，則?i,j:xi＞xj?y i＞yj和 ?i,j:yi＞yj?xi＞xj成立。

1.3 方案分類

保序加密方案對明文加密后，密文保留原有明文順序，用戶可直接對密文數據進行排序、比較大小等操作，既可以確保用戶數據安全，又可以增加密文數據的可操作性，目前主要應用于云服務器對密文數據庫進行范圍查詢、近似鄰檢索等[8]。

保序加密方案分類主要有檢索結構分類和密文變化情況分類。

（1）檢索結構分類。根據保序加密方案中是否含有明文檢索結構，將現有的保序加密方案分為無索引結構和基于索引結構的保序加密方案。無索引結構的保序加密方案是指加密密文直接保留原有明文順序?；谒饕Y構的保序加密方案是指明文數據采用常規(guī)分組體制加密方案進行加密，同時建立保序索引結構來比較明文順序。

（2）密文變化情況分類。根據密文是否變化，可將現有的保序加密方案大致分為密文不變和密文可變的保序加密方案。密文不變的保序加密方案是指相同的明文數據經保序加密算法加密后，產生的密文相同。密文可變的保序加密方案是指相同的明文數據加密后，產生的密文不相同。

1.4 方案選擇

保序加密方案直接對密文進行比較操作，若提高比較操作的效率，就會適當降低其安全性，密文的順序會向攻擊者泄露一些信息。在云計算環(huán)境中，攻擊者的常用手段是唯密文攻擊[9]，其中統計性攻擊是最有效的攻擊方法。攻擊者主要通過分析數據分布規(guī)律和數據頻率對密文實施統計攻擊。

（1）數據分布規(guī)律。利用保序加密方案所具有的明文空間映射密文空間的性質，攻擊者可通過統計分析密文數據分布規(guī)律，推測明文數據分布規(guī)律。

（2）數據頻率。攻擊者通過統計分析高頻率出現的密文數據來推導出對應的明文，使得密文數據出現的頻率與明文數據一致，從而攻擊加密方案成功。

經過安全性及其他性能等綜合評估，本文選擇了Kerschbaum 等人[9]于2015 年提出的以頻率隱藏保序加密方案的思想來構建一種新的方案，該方案通過動態(tài)的二叉平衡樹結構來隨機化密文隱藏明文的頻率，每個節(jié)點都有個狀態(tài)t來表示節(jié)點最大和最小范圍，利用壓縮樹來節(jié)省客戶端存儲空間。

2 基于搜索樹的保序加密方案

2.1 基本思想

頻率隱藏保序加密方案的基本思想[10]是隨機化密文分布，從而達到隱藏明文頻率的目的。該方案需要在客戶端（加解密側）維護一個搜索樹（二叉樹）狀態(tài)，以實現對數據的加密和解密，可以將搜索樹狀態(tài)看作私鑰。加密時，先檢查明文數據是否被存儲于客戶端的搜索樹中，若明文數據未被存儲于搜索樹中，則對明文數據進行確定性加密產生密文數據；若明文數據被存儲于搜索樹中，則對明文數據進行隨機化加密產生密文數據，并且更新搜索樹增加新的節(jié)點，該節(jié)點含有對應的明文數據和密文數據。總之，頻率隱藏保序加密方案對搜索樹中首次出現的明文數據進行確定性保序加密，對搜索樹中后續(xù)出現的明文數據進行隨機化保序加密。隨機化密文比確定性密文具有更高的熵，與普通保序加密方案相比，頻率隱藏保序加密方案需要在客戶端存儲更多的狀態(tài)信息，為了節(jié)省存儲空間，本方案還具備數據壓縮技術，既提供了實用性，又增強了密文的安全性。

2.2 基本原理

頻率隱藏保序加密方案采用了具有排序性質的二叉樹，在每個節(jié)點的值為明密文對，其性質如下文所述。

若它的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；若它的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；它的左、右子樹也分別為二叉排序樹。

2.3 方案描述

本文提出的一種基于搜索樹的保序加密方案是將明文數據按其被加密的順序插入到排序二叉樹中，具有動態(tài)分配的葉子和二叉搜索樹。其中，搜索樹是動態(tài)變化的，存在一定的閾值深度，超過該閾值深度后，搜索樹將被重新平衡。因此，本方案包括預處理步驟、加密算法ENCRYPT、解密算法DECRYPT 和重平衡化搜索樹算法REBALANCE。

預處理步驟如下文所述。明文數據集合X中的明文數據若非數值形式（如字符串），需要轉換成數值，最終以數值形式存在，這些數值與其他數值進行大小比較，其結果有大于、小于和等于3 種情況。當搜索樹算法開始執(zhí)行時，若搜索樹為空，則需要創(chuàng)建根節(jié)點t0 ，對明文x加密，并且將明文x和其對應的密文y存儲在根節(jié)點中，創(chuàng)建搜索樹根節(jié)點過程如圖2 所示。

搜索樹步驟開始執(zhí)行時，若已有根節(jié)點的搜索樹，也就是說，明文集合X中至少有一個明文x已被加密，并且至少有一個節(jié)點（如根節(jié)點）被包括在該搜索樹中。接收輸入集合包括明文x、當前考慮的節(jié)點t、min 值和max 值，判斷明文x是否等于當前考慮的節(jié)點t中的明文t.plain，若明文x等于t.plain，則基于RANDOMCOIN 確定判斷條件硬幣值coin為真；若明文x不等于t.plain，則coin被設置為假，表明明文x是唯一的，對其進行確定性加密。

當判斷完成明文x是否大于t.plain或coin是否等于1 時，若條件滿足其中之一，則向右遍歷搜索樹，判斷在當前考慮的節(jié)點t的右側是否已經存在子節(jié)點，若右子節(jié)點t.right不為空（右側已經存在子節(jié)點），則更新該輸入集合包括明文x、下一節(jié)點t.right作為當前考慮節(jié)點t、節(jié)點t.right的t.cipher作為min 值和max 值后，返回至起始輸入；若t.right為空（右側沒有已經存在的子節(jié)點），則判斷是否滿足搜索樹的閾值深度，即當前考慮的節(jié)點t的t.cipher與max值的差值是否小于2。若滿足閾值深度，則重平衡搜索樹，生成更新的搜索樹，將明文x及其密文右子節(jié)點密文t.right.cipher作為t.right插入到更新的搜索樹中；若沒有滿足閾值深度，則直接將明文x及其密文t.right.cipher作為新節(jié)點t.right插入到搜索樹中。

當判斷明文x是否大于t.plain或coin是否等于1 時，若明文x不大于t.plain，則向左遍歷搜索樹，判斷在當前考慮的節(jié)點t的左側是否已經存在子節(jié)點，若左子節(jié)點t.left不為空（左側已經存在子節(jié)點），則更新該輸入集合包括明文x、下一節(jié)點t.left作為當前考慮節(jié)點t、min和節(jié)點t.left的t.cipher作為max 值，返回至起始輸入；若t.left為空（左側沒有已經存在的子節(jié)點），則判斷是否滿足搜索樹的閾值深度，即當前考慮的節(jié)點t的t.cipher與min 值的差值是否小于2。若滿足閾值深度，則重平衡搜索樹，生成更新的搜索樹，將明文x及其左子節(jié)點密文t.left.cipher作為新節(jié)點t.left插入到更新的搜索樹中；若沒有滿足閾值深度，則直接將明文x及其密文t.left.cipher作為新節(jié)點t.left插入到搜索樹中。整個預處理過程如圖3 所示。

令λ為方案的安全性參數；N為不同明文數據的個數；k=[log2N]為明文數據的比特長度；l=λk為密文數據的比特長度。

算法1：加密算法FHOPE.Enc(x,t,min,max)→y

輸入：明文x，節(jié)點t，最小值min，最大值max

輸出：密文y

狀態(tài)：節(jié)點{t} 的排序二叉樹T

初始化：在初始建立二叉樹狀態(tài)時，可以將T初始化為空

1 若x=t.plain，則隨機在{0,1}選擇一個RANDOMCOIN()，令coin=RANDOMCOIN()

2 若x≠t.plain，則令coin=⊥

3 若x＞t.plain或者coin= 1，則執(zhí)行如下操作：

3.1 若max ?t.cipher≥ 2，則繼續(xù)遞歸調用FHOPE.Enc(x,t.right,t.cipher,max)

3.2 若t.right=Null，則執(zhí)行以下操作：

3.2a 若max ?t.cipher＜ 2，那么調用Rebalance(x, ?1,n)

4 若x＜t.plain或者coin=0 ，則執(zhí)行如下操作：

4.1 若t.left≠Null，則繼續(xù)遞歸調用FHOPE.Enc(x,t.left,t.cipher,max)

4.2 若t.right=Null，則執(zhí)行以下操作：

4.2a 若t.cipher?min ＜ 2，那么調用Rebalance(x, ?1,2λlog2n)

加密時，可調用FHOPE.Enc(x,root(T), ?1,2 2λlogn)→y。

算法2：解密算法FHOPE.Dec(y,t)輸入：密文y，節(jié)點t

輸出：明文x

狀態(tài)：節(jié)點{t} 的排序二叉樹T

1若y＞t.cipher，則遞歸調用FHOPE.Dec c(y,t.right)

2 若y＜t.cipher，則遞歸調用FHOPE.Dec

(y,t.left)

3 若y=t.cipher，則返回t.cipher

解密時，可以將T的根節(jié)點作為輸入來求解密文，即FHOPE.Dec(y,root(T))→x

算法3：重平衡化搜索樹算法Rebalance(x,min,max)→y

輸入：明文x，最小值min，最大值max

輸出：密文y

狀態(tài)：節(jié)點{t} 的排序二叉樹T

1 令X={t.plain}∪{x}

2 將X按照升序排列

3 創(chuàng)建一個新節(jié)點

4 令y=T.plain

5 令X'={x j|x j＜y}6 令X''={x j|xj＞y}

9 用y'和y''替換y，用X'和X''替換X，進行遞歸調用

10 在T中找到x，并返回Tx.cipher

2.4 方案安全性分析

對于保序加密的主流研究，可以用不可區(qū)分性或香農熵等指標來刻畫其安全性，實際上考慮的是從密文中恢復出正確明文的成功率。在使用保序加密的部分場景中，攻擊者不需要恢復出精確的明文，只需要恢復出一個足夠接近的近似值。為此，可以采用恢復出的明文與實際明文之間的距離，即平均絕對誤差來衡量安全性。

假設攻擊者知道一定的明密文對，相當于攻擊者已知了解密函數FHOPE.Dec(y,t)在一些定點的取值，此時攻擊者可以用插值給出解密函數FHOPE.Dec(y,t)的估計。不同的插值方法可以給出解密函數的不同估計。當攻擊者對于本方案有一定的了解時，可以根據加密函數的特性針對性地選擇插值方案。對于本文方案，假設攻擊者采用線性插值方法來恢復明文，對于密文y，若已知的明密文對中小于y的最大密文為y1，大于y的最小密文為y2，且y1和y2對應的明文為x1和x2，則解密函數FHOPE.Dec(y,t)在y的取值為：

對于最小與最大的明文，若已知的明密文對中不包含這兩個明文，則認為它們分別被映射到最小密文和最大密文，并以這兩對來對其他密文進行插值。則解密函數FHOPE.Dec(y,t)解密出的密文平均絕對誤差Dec.error為：

如果攻擊者解密出的密文平均絕對誤差為定值，則可以估計這兩個序列之間的準確映射關系，認為其成功攻擊了本文提出的保序加密方案。本文方案在預處理過程中提前判斷閾值深度，重平衡搜索樹，使得攻擊者獲得的密文平均絕對誤差會一直變化，除非其獲得了全部的明密文對才可能得到定值。所以本文方案是安全的。

2.5 實驗結果及分析

對本文提出的方案進行實驗，設置明文數據比特長度k為12，安全性參數λ為5，則密文數據比特長度l=λ×k= 60。實驗操作系統為Windows 10，處理器為Intel Core i5-6200U 2.3 GHz，內存為8 G，編程語言為C 語言。

實驗結果表明，雖然隨著明文大小的變化，加密時間也隨之變化，但是整體的加密速率是一致的，為114.441 Mbit/s，實驗結果如圖4所示。

本文方案與采用類似構造的Popa 方案在相同實驗環(huán)境下進行對比，在輸入相同明文的情況下，Popa 方案加密速率只有73.934 Mbit/s。相較于Popa 方案，本文的方案在加密速率方面提高了54.7%。

3 結 語

云計算環(huán)境下，用戶對于安全的進一步需求促使密碼技術有了很大的發(fā)展。但是傳統的密碼技術在用戶將自身隱私數據傳至云端保存的場景下存在困難，如用戶端的計算能力有限，傳統的加密技術會破壞明文數據的特性，不利于后續(xù)的范圍檢索等。

本文提出的保序加密方案對搜索樹中首次出現的明文數據進行確定性保序加密，對搜索樹中后續(xù)出現的明文數據進行隨機化保序加密，可以有效地應用于云環(huán)境下的加密數據檢索等場景中，同時本方案的加密速率在100 Mbit/s 之上，在一些交互強、延遲低的應用場景下也具有良好的效果。