面向云數據庫服務的隱私字符串加密查詢方案

吳宗大，江 芳，陳恩紅，徐貫東

WU Zongda1,JIANG Fang1,CHEN Enhong2,XU Guandong3

1.溫州大學 信息安全研究所，浙江 溫州 325035

2.中國科學技術大學 計算機科學與技術學院，合肥 230026

3.悉尼科技大學 工程與信息學院，澳大利亞 悉尼 2007

1.Information Security Centre,Wenzhou University,Wenzhou,Zhejiang 325035,China

2.Computer College,University of Science and Technology of China,Hefei 230026,China

3.Engineering&IT Faculty,University of Technology Sydney,Sydney 2007,Australia

1 引言

隨著互聯網技術的迅猛發展，云數據庫服務作為一種新型的數據服務形式，由于其靈活性高、成本低等優勢越來越受到人們歡迎，被廣泛地應用于各類企業信息管理系統中[1-2]。然而，不同于傳統數據庫，云數據庫部署在不可信云端，這對企業信息管理系統的各類用戶隱私信息（如個人電話號碼、身份證號等）構成了嚴重威脅[3-4]。更重要的是，這種安全威脅無法通過傳統的數據庫安全策略（如身份認證、授權訪問等）解決，也無法通過傳統的數據加密技術解決（加密后，定義在隱私數據上的查詢操作將無法在密文上執行，即密文查詢問題）[5-6]。因此，如何在不影響數據庫查詢有效性的前提下，保證存儲在不可信云數據庫中各類隱私信息的安全性，極富挑戰。

為了確保云數據庫中用戶隱私數據的安全性，最自然解決方案就是數據加密。然后，為了解決密文查詢問題，可以先對密文解密，再在解密后的明文上查詢。然而，這種方案勢必會嚴重降低數據查詢效率，嚴重制約了其實際可用性。傳統的同態加密算法[7-8]允許部分查詢操作在密文上直接執行，而無需解密數據，但這種技術容易受到統計攻擊。此外，研究者還提出了其他的一些數據加密方法以支持密文查詢[9-14]，但存在安全性差[9-11]或有效性差（即無法支持一些常見的字符串查詢）[12-14]等缺點，因而，難以直接運用它們解決云數據庫中的隱私數據加密查詢問題。最近，文獻[15]提出為密文數據建立特征索引，然后，在服務器端通過查詢索引以過濾掉絕大部分的非目標元組，較好地解決了查詢有效性問題。然而，該工作給出的索引生成方案過于簡單，嚴重降低了方法的靈活性和安全性。本文是該工作的深化和改進。本文重新設計了隱私字符串的索引生成方案，給出了新的查詢轉換方案，能在不影響查詢高效性的前提下，極大地提高方法的靈活性和安全性。

2 加密查詢方案

本文采用類似于文獻[15]的隱私數據加密查詢方案，其總體框架如圖1所示。其流程如下：（1）用戶通過可信客戶端提交明文形式的隱私字符串，由“數據加密部件”對字符串進行加密后，生成密文數據和索引數據并上傳至云端數據庫；（2）用戶通過客戶端提交針對明文字符串的原始SQL查詢語句時，由“查詢轉換部件”將原始查詢語句轉換成可以在索引數據上執行的新查詢，提交給云數據庫執行，以過濾掉絕大部分的非目標元組；（3）在云數據庫返回密文形式的元組集后，由“數據解密部件”解密為明文后存放到臨時結果中，再由“數據篩選部件”在臨時結果上執行原始查詢，從而進一步排除不滿足查詢條件的元組，返回精確結果給用戶。在該模型中，數據加密、解密以及查詢轉換過程涉及到的各類參數均存放在可信的客戶端中。從圖1可以看出，設計合理有效的字符串索引方案（應用在數據加密部件），以及將定義在明文上的原始查詢轉換為定義在索引上的新查詢（應用在查詢轉換部件），是影響云數據庫查詢效率的關鍵因素。本文的后續內容將主要圍繞特征索引方案以及查詢轉換方案兩部分展開。

2.1 數據存儲方法

為了在云數據庫中存儲隱私字符串對應的密文數據和索引數據，需要改造原有關系表。假設在云數據庫中存在關系表R(A1,A2,…,Ar,…) ，其中，Ar是存儲隱私字符串的隱私字段，則改造后的加密關系表為，其中：（1）RE中新增的密文字段（其類型為二進制型）用于存儲由R中整個元組加密后得到的密文數據；（2）RE中新增的索引字段用于存儲對應隱私字段A的索引數據（其類型與r隱私字段Ar保持一致，一般為變長字符串型）；（3）RE中其余字段與R中的原有字段保持一致（但刪除隱私字段 Ar）。

2.2 數據索引方法

根據圖1所示，當用戶通過客戶端向云數據庫提交一條元組時，“數據加密部件”首先會對元組進行加密，同時為元組里隱私字符串構建索引。這里，元組加密使用傳統加密算法完成（如AES）。傳統加密算法已經非常成熟，可以很好地保護密文的安全性。本文不再討論數據加密算法本身，而主要討論的是如何為隱私字符串構建特征索引。

對于給定關系表R的隱私字段Ar（其數據類型為可變字符串型），假定字段的最大長度為nr。一般化地，給定定義在隱私字段Ar上的任意字段值ar。以下研究如何將明文形式的字段值ar映射為索引值ax，記作ar?ax。該過程共需要4個步驟，其中，前面3個步驟在元組提交之前預先設置完成，最后1個步驟在元組提交之后在線完成。

圖1 云數據庫隱私數據加密查詢方法的總體框架

步驟1將最大長度為nr的隱私字段Ar劃分為m個子字段，記作：B1,B2,…,Bm(1 ≤m≤nr)，并且這些子字段滿足以下3個條件。

（1）任一子字段均不為空集，即任一子字段的長度均不為零，即

（2）各個子字段互不相交，即

（3）各個子字段的并集等于隱私字段Ar，即

步驟2對步驟1分段得到的各個子字段Bk(i=1,2,…,m)的值域（即子字段各個字符單位所有可能取值所構成的集合）進行分區。假設任一子字段Bk的值域為domain(Bk)，且被分成nk個分區，分別記作：,,…,，這些分區滿足以下4個條件。

（1）任一分區均不為空集，即

（2）各個分區互不相交，即

（3）各個分區的并集等于該子字段Bk的值域，即

（4）各個分區中任意元素的值均大于其相鄰分區中所有元素的值。該條件可形式化表示為

步驟3為各個子字段Bk的各個分區,,…,分別分配一個互不相同的唯一標識字符，記作id)，即

基于步驟2和步驟3的設定，給定子字段Bk的任一具體值b，均可被映射為一個標識符id)，其中k，即確定了一個映射函數，記作Xk(bk)。

步驟4給定定義在隱私字段Ar上的任意值ar，基于步驟1的設定，假定它覆蓋了隱私字段Ar的n個子字段B1,B2,…,Bn(1 ≤n≤m )，并且假定它對應于各個子字段的取值分別是b1,b2,…,bn，即ar=b1b2…bn。那么基于步驟2和步驟3，可將ar映射為一個新的字符串，記作ax=X(ar)=X1(b1)X2(b2)…Xn(bn)，作為其索引值。

例子1假設隱私字段Ar為“手機號碼”。手機號碼一般有11位字符構成，其中，前2位只能是13、15、17或18，剩余的9位可以為字符0至9的任意取值。首先，步驟1將隱私字段Ar劃分成若干個子字段。假定步驟1將隱私字段劃分成3個子字段（即m=3），且| B1|=3,|B2|=4,| B3|=4。然后，步驟2將對各個子字段進行分區。假定子字段B1被劃分2個分區，B2被劃分10個分區，B3被劃分20個分區，分別如下：

接著，步驟3為各個子字段的各個分區分配標識字符。假定分區標識符分別如下：

以上3個步驟預先離線設置完成。最后，對于用戶通過客戶端提交的定義在隱私字段Ar上的任意值ar，步驟4將其映射為一個索引值ax。假定ar=‘155 6123 4890’，則基于步驟1至步驟3的設定，映射得到索引值ax=X(ar)=‘1Gj’。

2.3 查詢轉換方法

根據圖1所示，當用戶在客戶端提交數據查詢語句時，“查詢轉換部件”負責將定義在隱私字段上的原始查詢轉換為定義在索引字段上的新查詢，并且要求：新查詢的執行結果必須是原始查詢結果的超集（即新查詢返回的元組集合必須包含所有的目標元組）。字符串相關的查詢條件主要包括：精確查詢、模糊查詢和范圍查詢。為此，本文針對這三種查詢條件給出相應的轉換方法，將定義在隱私字段上的原始查詢條件轉換為定義在索引字段上的新查詢條件，以使得它們能夠在云數據庫上正確執行。

（1）精確查詢轉換。其表示形式一般為：R.Ar=a，其中a表示字符串常量，Ar為隱私字段?；诓襟E1的設定，假定字符串常量a覆蓋了n個子字段(1 ≤n≤m )，并假定它對應于各個子字段的值分別為b1,b2,…,bn，即a=b1b2…bn，則精確查詢條件轉換如下：

（2）模糊查詢轉換。模糊查詢條件建立在謂詞“LIKE”的基礎之上，其一般語法格式為：LIKE＜匹配字符串＞，其中，匹配字符串可以含有通配符“%”、“_”或“[]”。以下分別討論基于三種通配符的模糊查詢條件轉換。

①基于通配符“%”的模糊查詢轉換?！?”代表匹配任意長度字符串。以下先考慮“%”位于右邊的情況，此時模糊查詢條件的一般形式為：R.ArLIKE a%?；诓襟E1的設定，假定字符串常量a靠左完整覆蓋了n個子字段B1,B2,…,Bn(1 ≤n≤m )，假定它對應于各子字段的值分別為b1,b2,…,bn，則模糊條件轉換如下：

當通配符“%”位于左邊時，即R.ArLIKE%a?；诓襟E1的設定，假定字符串常量a靠右完整覆蓋了(m -i+1)個子字段Bi,Bi+1,…,Bm(1 ≤i≤m )，并假定它對應于各個子字段的值分別為bi,bi+1,…,bm，則模糊查詢條件轉換如下：

②基于通配符“_”的模糊查詢轉換?！癬”代表匹配一個任意字符，此時模糊查詢條件的一般形式為：R.ArLIKE a_b，其中，a和b為字符串常量。假定字符串a_b完整覆蓋了n個子字段B1,B2,…,Bn(1≤n≤m)，其中，Bi(1≤i≤n)為包含通配符“_”的子字段。并假定a_b對應于子字段B1,B2,…,Bi-1的值分別為b1,b2,…,bi-1，對應于子字段Bi+1,Bi+2,…,Bn的值分別為bi+1,bi+2,…,bn，則模糊查詢條件轉換如下：

③基于通配符“[]”的模糊查詢轉換?！癧p]”表示匹配列表p里的一個字符，此時模糊查詢條件的一般化形式為：R.ArLIKE a[p]b（a、b、p均為字符串）。若p=p1p2…pt，則模糊查詢條件可基于精確查詢條件來完成，轉換如下：

（3）范圍查詢轉換。范圍查詢條件的一般形式為：R.Ar≥a?；诓襟E1的設定，假定字符串常量a完整覆蓋了n個子字段B1,B2,…,Bn(1 ≤n≤m )，并假定它對應于各個子字段的值分別為b1,b2,…,bn。記子字段Bi的最大取值為，記next(bi)為 Bi中大于bi的最小取值。那么，對于不小于a的任意字符串a′=b1'b2'…bz'(1 ≤z≤m )，它必定滿足條件：(n ext(b1)≤b1')；或 (b1=b1'∧next(b2)≤b2')；…；或 (b1=∧b2=∧…∧bk-1=∧next(bk)≤)，其中，k=max(n,z)?；谝陨戏治觯秶樵儣l件可基于相似查詢條件來完成，轉換如下：

以上，針對三類常見的字符串查詢條件分別給出了對應的查詢轉換方法。可以看出，云數據庫中的任意元組，如果它滿足轉換后的查詢，則它解密后必然滿足轉換前的查詢（即新查詢條件是原查詢條件的必要條件）。當用戶通過客戶端提交查詢語句時，“查詢轉換部件”分析用戶查詢中的基本查詢條件，將定義在隱私字段上的基本查詢條件轉換為定義在索引字段上的新查詢條件，從而生成可以在加密云數據庫上正確執行的新查詢。然后，再將轉換后的新查詢提交給云數據庫執行。最后，由“數據解密部件”解密云數據庫返回的查詢結果，由“數據篩選部件”在查詢結果上執行原始查詢，從而進一步過濾掉非目標元組，獲取精確結果，返回給用戶。

3 安全性分析

傳統加密算法可以保證密文的安全性，所以只討論索引的安全性，即基于索引方法生成的索引數據，攻擊者能否分析出相應的明文字符串或相關的敏感信息。將對比文獻[15]的方法（下文稱作：簡單分區法）來分析本文方法（下文稱作：復合分區法）的安全性。

在簡單分區法中，隱私文本字段的各個單位字符的值域將被統一劃分（如“手機號碼”字段的單位值域被劃分為如下5個分區：{0 ,1}、{2 ,3}、{4 ,5}、{6 ,7}和{8 ,9}），然后，為每個分區設定標識符（假設分別為：A、B、C、D和E），最后，將隱私字符串映射為相應索引值（如“155 6123 4890”將被映射為“ACC DABB CFFA”）。

分析1兩種索引方法均能很好地抵抗常見攻擊，擁有較好的安全性。不論是簡單分區法還是復合分區法，從明文字符串到索引字符串之間的映射是一種“多對一”映射（即一個索引值對應多個明文值），因此，即使利用攻擊方法（如統計攻擊、已知明文攻擊等）獲知了映射函數，也難以根據索引值獲知相應的明文。此外，還可以看出，各個分區包含的字符越大（即分區規模越大），則一個索引值對應的明文值就越多，從而索引的安全性也就越好。為此，為了獲取更好的安全性，可以適當提高方法步驟2中的各個分區的規模。

分析2相比簡單分區法，復合分區法擁有更好的安全性。對于簡單分區法，雖然難以根據索引值獲知具體的明文值，但是攻擊者還是可以根據索引值獲取一些明文的相關敏感信息，例如，可以獲知明文的長度（索引值與明文值具有相同的長度）。對于復合分區法，由于步驟1的子字段劃分，避免了這個問題。此外，相比于簡單分區法，攻擊者更加難以獲知復合分區法所構建的索引映射函數。例如，對于電話號碼的例子，根據已知明文攻擊法，攻擊者最少只需要知道5個從明文到索引的二元映射組，就可以獲知簡單分區法的映射函數，而對于復合分區法，由于各個子字段獨立分區（即分區各不相同），攻擊者需要知道大量的明文及其相應的索引值，才可能獲知映射函數。

表1 相似查詢條件和范圍查詢條件

分析3相比簡單分區法，復合分區法擁有更好的靈活性?？梢钥闯鰪秃戏謪^法是簡單分區法的深入擴展。如果步驟1將各個子字段的長度均設置為1，步驟2對所有子字段均采用統一的分區劃分方案，則復合分區法得到的索引映射函數將與簡單分區法的一致。相比于簡單分區法，復合分區法擁有更好地靈活性，能更好地滿足實際的應用需求。例如，對于電話號碼字段，雖然每個字符單位均擁有相同的值域（均是從0到9），但實際上它們的取值卻并不一致（如第一位字符只能是1）。在復合分區法中，步驟1讓用戶可以根據實際需要先進行子字段劃分，從而使得每個子字段均可擁有相似規模的值域。此外，在復合分區法中，用戶還可以根據需要，將敏感的子字段劃分粗些，以獲得更好地數據安全性，將不敏感的子字段劃分細些，以獲得更好的查詢高效性。

4 高效性評估

前文展示了基于本文的索引方案，定義在字符串型隱私字段上的各類查詢條件均可有效地轉換為索引字段上的新查詢，使得它們可以在加密云數據庫上正確執行，即本文索引方案擁有很好的查詢有效性。以下，將實驗評估本文方案的查詢高效性，即評估查詢轉換得到的新查詢能夠過濾絕大部分的加密云數據庫中的非目標元組，以提高查詢效率。

4.1 實驗設置

首先，構造實驗數據庫，隨機生成一百萬條元組，其中敏感字段由11位數字字符構成的電話號碼；然后，在兩臺電腦上進行實驗，其中一臺作為云數據庫服務器，另一臺作為客戶端，其配置為：Intel I7 4510U CPU+8 GB內存+1 TB硬盤。此外，操作系統為Win 7（64位），數據庫系統為MySQL。從圖1所示的數據查詢過程可以看出，索引方案的查詢高效性，表現在轉換得到的新查詢對加密云數據庫中非目標元組的過濾效果。這里采用文獻[9]的過濾效果衡量公式：，其中，表示滿足用戶查詢的元組數量，R′2表示滿足轉換生成的新查詢的記錄數量，R表示與用戶查詢相關的數據表規模大小。Fr的取值范圍從0到1，并且其值越大表示對非目標元組的過濾效果越好。索引方案采用例子1的設置。表1給出了實驗中涉及的基本相似查詢和基本范圍查詢，其中B1表示三個數字字符，B2和B3表示四個數字字符，它們分別對應一個隱私子字段值。

4.2 評估結果

第一組實驗評估基本相似查詢條件的高效性。實驗中，讓每個索引值對應的可能明文值數量持續增長變化（記作K值），從25增長到215（K值可通過設定索引方案的步驟1和步驟2相關參數來完成），實驗結果如圖2所示（其中，橫坐標表示K值，縱坐標為Fr值）。基于圖2的實驗結果，有以下幾個觀察。（1）隨著K值的持續增長，Fr值將持續變小，即新查詢條件對非目標元組的過濾效果將隨之變差。因為，隨著K值的增長，不同電話號碼被映射為相同索引值的概率將變大，從而使得非目標元組在云端被過濾掉的概率也隨之變小，即使得Fr值隨之變小（最極端情況下，如果所有的電話號碼都被映射為相同索引值，此時索引對非目標元組的過濾效果最差，即Fr=0）。（2）基于本文的索引方案，大部分的非目標元組將在服務器端被過濾掉（過濾比率基本大于0.9，即使K值被設置為較大的時候），從而極大地降低了返回客戶端的密文元組規模，即降低了網絡通訊開銷，減小了客戶端的數據查詢規模，從而極大地提高了相似查詢效率。（3）不同信息量的相似查詢條件會導致不同的Fr值變化趨勢，即相似查詢條件相關的匹配字符串常量包含的信息量越多，則Fr值也隨之變大（相同K值設定下，F1小于F2，F2小于F3）。這是因為，相似查詢條件包含的信息量越大，通常返回客戶端的元組規模就越少，從而增加Fr值。

圖2 基本相似查詢條件的高效性評估結果

第二組實驗評估基本范圍查詢條件的高效性。實驗結果如圖3所示?；趫D3的實驗結果，有以下幾個觀察。（1）通過使用索引方案，大部分的非目標元組將在服務器端被過濾掉，從而降低了返回客戶端的密文元組規模，減小了客戶端的數據查詢規模，極大提高了范圍查詢效率。（2）隨著K值的持續增長，新查詢條件對非目標元組的過濾效果將隨之變差。綜合以上，可以看出：對于絕大多數的相似查詢和范圍查詢，90%以上的非目標元組均能在服務器端被過濾掉。因為加密而導致的用戶查詢效率的下降比例，近似地反比于服務器端對非目標元組的過濾比例。因而，索引方案具有很好的查詢高效性，能有效地降低數據查詢開銷。最后，需要指出，簡單分區法與本文方法擁有一致的查詢高效性，為此本節不再重復給出簡單分區法的高效性實驗評估結果。

圖3 基本范圍查詢條件的高效性評估結果

5 結論

本文面向云數據庫的字符串型隱私數據的加密查詢問題，提出了一個有效解決方案。該方案核心是加密索引方法和查詢轉換方法，不僅能夠確保隱私字符串在不可信云端的安全性，還能夠確保用戶查詢操作的高效性。理論分析和實驗評估驗證了方案的實際效用：（1）安全性，即難以根據索引數據獲知字符串的敏感信息；（2）有效性，即能夠支持常見的字符串查詢條件（包括相似查詢和范圍查詢）；（3）高效性，即能在云端過濾掉絕大部分的非目標元組，極大地提高數據查詢效率；（4）靈活性，即能夠根據字符串的分布情況，靈活設置相關參數，協調安全性和高效性。

參考文獻：

[1]束柬，梁昌勇，陸文星，等.基于云的企業管理信息系統再造研究綜述[J].情報學報，2015（5）：549-560.

[2]王檸，劉國華，趙春紅，等.一種適用于外包數據庫的綜合密文索引技術[J].小型微型計算機系統，2010（9）.

[3]Bharath K，Samanthual，Wei Jiang.Efficient privacy-preserving range queries over encrypted data in cloud computing[C]//2013 IEEE Sixth International Conference on Cloud Computing，2013.

[4]Zhang Wei，Lin Yaping，Xiao Sheng，et al.Privacy preserving ranked multi-keyword search for multiple data owners in cloud computing[J].IEEE Transactions on Computers，2016，65（5）：1566-1577.

[5]崔賓閣，劉大昕，王桐.支持快速查詢的數據庫加密方法的研究[J].計算機科學，2006，33（6）：115-118.

[6]Li J，Wang Q，Wang C，et al.Fuzzy keyword search over encrypted data in cloud computing[C]//Proc of the 31st Conference on Computer Communications.New York：ACM Press，2012：1-5.

[7]Domingo F J.A new privacy homomorphism and applications[J].Information Processing Letters，1996，60（5）：277-282.

[8]Chung S S，Ozsoyoglu G.Anti-tamper databases：Processing aggregate queries over encrypted databases[C]//Proc of the 22nd International Conference on Data Engineering Workshops.Atlanta，GA，USA：IEEE Computer Society，2006.

[9]Wu Z，Xu G，Zong Y，et al.Executing SQL queries over encrypted character strings in the database-as-service model[J].Knowledge-Based Systems，2012，35：332-348.

[10]Wang Z，Dai J，Wang W，et al.Fast query over encrypted character data in database[J].Communications in Information and Systems，2004，4（4）：289-300.

[11]俞志斌，周彥暉.基于關鍵字的云加密數據索引保護檢索[J].計算機科學，2015，42（6A）：365-369.

[12]Fu Zhangjie，Sun Xingming，Xia Zhihua，et al.Multi-keyword ranked search supporting synonym query over encrypted data in cloud computing[C]//Performance Computing and Communications Conference（IPCCC），2013：1-8.

[13]Xu Zhiyong，Kang Wansheng，Li Ruixuan，et al.Efficient multi-keyword ranked query on encrypted data in the cloud[C]//2012 IEEE 18th International Conference on Parallel and Distributed Systems（ICPADS），2012：244-251.

[14]Cao Ning，Wang Cong，Li Ming，et al.Privacy-preserving multi-keyword ranked serach over encrypted cloud data[J].IEEE Transactions on Parallel and Distributed Systems，2014，25（1）：222-233.

[15]盧成浪，劉明雍，吳宗大，等.針對網絡信息系統的個人隱私保護方案[J].小型微型計算機系統，2015，36（6）：1291-1295.