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

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

0 引 言

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

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

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

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

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

1 保序加密概述

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

1.1 系統(tǒng)模型

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

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

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

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

1.2 形式化定義

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

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

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

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

其中，S←KEYGEN(λ)為根據(jù)安全性參數(shù)λ生成秘密狀態(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：序列隨機(jī)化。

令n為序列S=x1,x2, … ,xi, …,x n(?i,xi∈N)中明文的個數(shù)。序列X滿足隨機(jī)化順序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 方案分類

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

保序加密方案分類主要有檢索結(jié)構(gòu)分類和密文變化情況分類。

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

（2）密文變化情況分類。根據(jù)密文是否變化，可將現(xiàn)有的保序加密方案大致分為密文不變和密文可變的保序加密方案。密文不變的保序加密方案是指相同的明文數(shù)據(jù)經(jīng)保序加密算法加密后，產(chǎn)生的密文相同。密文可變的保序加密方案是指相同的明文數(shù)據(jù)加密后，產(chǎn)生的密文不相同。

1.4 方案選擇

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

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

（2）數(shù)據(jù)頻率。攻擊者通過統(tǒng)計分析高頻率出現(xiàn)的密文數(shù)據(jù)來推導(dǎo)出對應(yīng)的明文，使得密文數(shù)據(jù)出現(xiàn)的頻率與明文數(shù)據(jù)一致，從而攻擊加密方案成功。

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

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

2.1 基本思想

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

2.2 基本原理

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

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

2.3 方案描述

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

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

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

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

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

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

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

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

輸出：密文y

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸出：明文x

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

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

2 若y＜t.cipher，則遞歸調(diào)用FHOPE.Dec

(y,t.left)

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

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

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

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

輸出：密文y

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

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

2 將X按照升序排列

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

4 令y=T.plain

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

9 用y'和y''替換y，用X'和X''替換X，進(jìn)行遞歸調(diào)用

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

2.4 方案安全性分析

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

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

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

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

2.5 實驗結(jié)果及分析

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

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

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

3 結(jié) 語

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

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