具有隱私保護(hù)的外包數(shù)據(jù)庫(kù)合計(jì)查詢方案

蔣亞軍 ，楊 波，張明武，陳旭日

(1. 華南農(nóng)業(yè)大學(xué) 信息學(xué)院，廣東 廣州，510642；2. 湖南科技學(xué)院 計(jì)算機(jī)與通信工程系，湖南 永州，425100；3. 上海大學(xué) 計(jì)算機(jī)工程與科學(xué)學(xué)院，上海，200072)

隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的迅速發(fā)展，數(shù)據(jù)庫(kù)外包已成為一個(gè)重要的發(fā)展趨勢(shì)。數(shù)據(jù)所有者將數(shù)據(jù)管理業(yè)務(wù)委托給第三方服務(wù)提供者，服務(wù)提供者提供軟硬件和網(wǎng)絡(luò)資源，為數(shù)據(jù)所有者及用戶提供遠(yuǎn)程的數(shù)據(jù)庫(kù)創(chuàng)建、存儲(chǔ)、更新和查詢等數(shù)據(jù)管理服務(wù)，從而優(yōu)化數(shù)據(jù)所有者的資源配置，降低軟硬件投資成本，減輕管理和維護(hù)任務(wù)[1-2]。然而，由于第三方服務(wù)提供者并非完全可信，因此，數(shù)據(jù)的隱私性和安全性已成為數(shù)據(jù)庫(kù)外包系統(tǒng)中一個(gè)重點(diǎn)關(guān)注的問(wèn)題。大型數(shù)據(jù)庫(kù)中合計(jì)查詢是一項(xiàng)非常頻繁和重要的操作，而外包數(shù)據(jù)庫(kù)系統(tǒng)中的合計(jì)查詢除了要求得到正確的查詢結(jié)果外，還要保護(hù)查詢過(guò)程中數(shù)據(jù)的隱私和安全。近年來(lái)，許多外包數(shù)據(jù)庫(kù)查詢方法利用數(shù)據(jù)加密隱藏外包數(shù)據(jù)[3-7]，然而，數(shù)據(jù)加解密的計(jì)算復(fù)雜性增加了計(jì)算和通信代價(jià)，因而效率不高。而通過(guò)秘密共享實(shí)現(xiàn)數(shù)據(jù)庫(kù)外包，并對(duì)外包數(shù)據(jù)進(jìn)行隱私保護(hù)計(jì)算[2,8-10]，避免了數(shù)據(jù)加解密，極大地提高了計(jì)算效率，目前已成為外包數(shù)據(jù)庫(kù)查詢方法研究中的熱點(diǎn)。在此，本文作者提出一種基于秘密共享的合計(jì)查詢方案，利用Mignotte秘密共享方案將數(shù)據(jù)庫(kù)外包給服務(wù)提供者，服務(wù)提供者根據(jù)用戶提出的合計(jì)查詢要求，在不泄露外包數(shù)據(jù)的前提下協(xié)同計(jì)算查詢結(jié)果并將之響應(yīng)給用戶，用戶在信賴數(shù)據(jù)所有者的前提下，根據(jù)數(shù)據(jù)所有者對(duì)數(shù)據(jù)項(xiàng)的承諾和生成的 Merkle哈希樹對(duì)查詢結(jié)果進(jìn)行驗(yàn)證。

1 基礎(chǔ)知識(shí)

1.1 Mignotte秘密共享方案

Mignotte秘密共享方案[11-12]是通過(guò)中國(guó)剩余定理將秘密x讓m個(gè)用戶共享，由其中任意k個(gè)用戶能夠恢復(fù)秘密x，但少于k個(gè)用戶不能恢復(fù)秘密x。

設(shè)m為大于2的正整數(shù)，2≤k≤m，選擇m個(gè)兩兩互質(zhì)的正整數(shù) d1, d2, …, dm(d1＜d2＜…＜dm)，令，要求 β ＜x＜α。方案描述如下：

1.2 Pedersen承諾方案

Pedersen承諾方案[13]包括承諾者和驗(yàn)證者兩方，雙方商定 g ∈ Gq， h ∈ Gq，且 lo ggh 未知。承諾者隨機(jī)選擇隨機(jī)數(shù) r ∈ Zq，其對(duì) x ∈ Zq的承諾為 Cr(x)=gxhr∈ G 。驗(yàn)證者不能從Cr中得到任何x的消息，而承諾者不能謊稱Cr為x′的承諾，這里 x ≠ x'。

1.3 Merkle哈希樹

Merkle哈希樹[14]是一個(gè)二叉樹，給定向量=(,… ,xn)，F(xiàn)(·)為公開的單向哈希函數(shù)，定義結(jié)點(diǎn)函數(shù)H(i,j,)如下：

2 本文方案

在外包數(shù)據(jù)庫(kù)模型中有3個(gè)實(shí)體：數(shù)據(jù)所有者、服務(wù)提供者和用戶，這些實(shí)體的角色如下所述。

(1) 數(shù)據(jù)所有者創(chuàng)建和維護(hù)數(shù)據(jù)庫(kù)，對(duì)數(shù)據(jù)項(xiàng)進(jìn)行承諾，產(chǎn)生和維護(hù)Merkle哈希樹，并將數(shù)據(jù)庫(kù)外包給服務(wù)提供者；數(shù)據(jù)所有者的符號(hào)為DO。

(2) 服務(wù)提供者負(fù)責(zé)外包數(shù)據(jù)庫(kù)的存儲(chǔ)和管理，響應(yīng)用戶查詢；本文方案中假設(shè)有m個(gè)服務(wù)提供者，符號(hào)為SP1, SP2, …, SPm。

(3) 用戶通過(guò)服務(wù)提供者進(jìn)行查詢，并通過(guò)數(shù)據(jù)所有者對(duì)數(shù)據(jù)項(xiàng)的承諾和產(chǎn)生的 Merkle哈希樹驗(yàn)證查詢結(jié)果的正確性；用戶的符號(hào)為U。

數(shù)據(jù)所有者、服務(wù)提供者和用戶三者的關(guān)系如圖1所示。

圖1 外包數(shù)據(jù)庫(kù)模型Fig.1 Outsourced database model

為簡(jiǎn)化描述，假設(shè)數(shù)據(jù)庫(kù)D為n行1列，且每個(gè)數(shù)據(jù)項(xiàng)為正整數(shù)，設(shè)D=(x1, …, xn)(其中，β＜xi＜α，1≤i≤n)，且 。方案分為承諾、分配、查詢、響應(yīng)和驗(yàn)證5個(gè)階段。下面以用戶提出的求和查詢?yōu)槔M(jìn)行闡述。

2.1 承諾階段

在承諾階段，數(shù)據(jù)所有者完成對(duì)數(shù)據(jù)的承諾，并根據(jù)承諾產(chǎn)生Merkle哈希樹。設(shè)數(shù)據(jù)所有者選擇公共參數(shù)g和h， g ∈ Gq， h ∈ Gq，然后對(duì)各數(shù)據(jù)項(xiàng)承諾：c1= Cr1(x1)， c2= Cr2(x2)，…， cn= Crn(xn)。令向量=(c1, c2, …, cn)，數(shù)據(jù)所有者根據(jù)向量產(chǎn)生Merkle哈希樹。設(shè)數(shù)據(jù)所有者的公開鑰和秘密鑰分別為pk和sk，則數(shù)據(jù)所有者利用自己的秘密鑰sk對(duì)根結(jié)點(diǎn)簽名為sigsk(H (1 ,n,，并將和sigsk(H ( 1,n,廣播給所有服務(wù)提供者。

2.2 分配階段

在分配階段，數(shù)據(jù)所有者將數(shù)據(jù)庫(kù)外包給m個(gè)服務(wù)提供者。對(duì)于每個(gè)數(shù)據(jù)項(xiàng)xi和相應(yīng)的隨機(jī)數(shù)ri，服務(wù)提供者SPj的共享為yij和zij。其中：

2.3 查詢階段

在查詢階段，用戶向服務(wù)提供者發(fā)出查詢請(qǐng)求。設(shè)用戶向服務(wù)提供者SP1提出求和的請(qǐng)求S?{1 ,2,…,n}，SP1則向其余任意的k-1個(gè)服務(wù)提供者發(fā)出合作求和的請(qǐng)求。

2.4 響應(yīng)階段

在響應(yīng)階段，k個(gè)服務(wù)提供者在保證各自共享隱私的前提下協(xié)同計(jì)算查詢結(jié)果，并將之響應(yīng)給用戶。設(shè)Ω是k個(gè)服務(wù)提供者的聯(lián)盟(包括SP1)，它們共同計(jì)算XS。其中任意服務(wù)提供者SPj中，j∈Ω，Ω?{1,2,…,m}。

(1) Ω中每一個(gè)服務(wù)提供者SPj計(jì)算：

然后，SPj將傳送至SP1。

(2) SP1收集其他k-1個(gè)后，計(jì)算：

(3) 服務(wù)提供者 SP1將 XS，RS，C和sigsk(H ( 1,n傳送至用戶。

2.5 驗(yàn)證階段

在驗(yàn)證階段，用戶在不知道數(shù)據(jù)庫(kù)D的數(shù)據(jù)項(xiàng)和服務(wù)提供者獲得的共享的前提下驗(yàn)證XS。

3 方案分析

3.1 正確性分析

因此，XS可通過(guò)求Ω中每個(gè)服務(wù)提供者的而獲得，即響應(yīng)階段中的求和 XS是正確的。顯然，相對(duì)應(yīng)的平均值為： ||/SXS(其中 ||S為集合S中元素個(gè)數(shù))。

3.2 隱私性和安全性分析

定理1 半誠(chéng)實(shí)的服務(wù)提供者的共享對(duì)于其他服務(wù)提供者具有隱私保護(hù)。

證明 在SP1與其他k-1個(gè)服務(wù)提供者協(xié)同計(jì)算求和時(shí)，是通過(guò)求Ω中每個(gè)服務(wù)提供者的而獲得，而，因此，SP1無(wú)法從中分離出uij，其他k-1個(gè)服務(wù)提供者的共享具有隱私性。

定理2 本文方案面對(duì)k-1個(gè)惡意服務(wù)提供者共謀時(shí)，數(shù)據(jù)在計(jì)算上是安全的。

證明 當(dāng)k-1個(gè)服務(wù)提供者勾結(jié)時(shí)，這k-1個(gè)服務(wù)者設(shè)為 S Pj1,SPj2,… ,S Pjk-1。如果它們想用其共享恢復(fù) xi時(shí)，根據(jù)Mignotte秘密共享方案，可以求得1個(gè)唯 一 值(dj1dj2… djk-1)， 并 且 xi=xi'm oddj1dj2…djk-1，這意味著在[β,α]上至少有c=個(gè)值有可能是x(其中，“[ ]”表示取整)。假i如c足夠大(例如c=106)，則 xi在計(jì)算上是安全的，即保證了數(shù)據(jù)的隱私性。

定理 3 惡意的服務(wù)提供者在多項(xiàng)式時(shí)間里不能生成一個(gè)有效的查詢結(jié)果。

證明 惡意服務(wù)提供者要想在多項(xiàng)式時(shí)間里生成一個(gè)有效的查詢結(jié)果，必須滿足如下情形之一：

(3) 仿造數(shù)據(jù)所有者對(duì)一個(gè)新的Merkle哈希樹進(jìn)行簽名。

對(duì)于情形(1)，由Pedersen承諾方案在計(jì)算上是不可實(shí)現(xiàn)的；對(duì)于情形(2)，由于)(·F為單向哈希函數(shù)，是無(wú)沖突的，因此，在計(jì)算上也是不可實(shí)現(xiàn)的；對(duì)于情形(3)，由公鑰加密機(jī)制原理要仿造數(shù)字簽名在計(jì)算上也是不可實(shí)現(xiàn)的。這個(gè)定理保證了數(shù)據(jù)的完整性。

3.3 效率分析

采用本文方案所得計(jì)算復(fù)雜度與文獻(xiàn)[10]中各參與方的計(jì)算復(fù)雜度比較結(jié)果如表1所示，其中：本文方案中數(shù)據(jù)庫(kù)所有者的計(jì)算復(fù)雜度為o(nm)，文獻(xiàn)[10]中數(shù)據(jù)庫(kù)所有者的計(jì)算復(fù)雜度為o(nmk)；本文方案的服務(wù)提供者SP1的計(jì)算復(fù)雜度為o(k)，文獻(xiàn)[10]中服務(wù)提供者SP1的計(jì)算復(fù)雜度為o(k2)。顯然，由于本文方案使用Mignotte秘密共享方案外包數(shù)據(jù)庫(kù)并計(jì)算查詢結(jié)果，與文獻(xiàn)[10]中利用Shamir秘密共享方案相比，在數(shù)據(jù)庫(kù)外包和查詢計(jì)算等方面具有更高的效率。

表1 本文方案與文獻(xiàn)[10]中各參與方的計(jì)算復(fù)雜度Table1 Computational complexity of all involved parties in this paper and Ref.[10]

4 結(jié)論

(1) 提出了一種具有隱私保護(hù)的外包數(shù)據(jù)庫(kù)合計(jì)查詢方案。該方案利用Mignotte秘密共享方案進(jìn)行數(shù)據(jù)外包，服務(wù)提供者在不能獲得彼此外包數(shù)據(jù)的前提下協(xié)同計(jì)算查詢結(jié)果并將之響應(yīng)給用戶。用戶可以根據(jù)數(shù)據(jù)所有者對(duì)數(shù)據(jù)項(xiàng)的 Pedersen承諾和生成的Merkle哈希樹對(duì)結(jié)果進(jìn)行驗(yàn)證。

(2) 所提出的方案可以保護(hù)數(shù)據(jù)項(xiàng)和中間結(jié)果的隱私性和安全性，在數(shù)據(jù)庫(kù)外包和查詢計(jì)算等方面具有更高的效率。

(3) 在外包數(shù)據(jù)庫(kù)查詢方案中，結(jié)果驗(yàn)證是重要的組成部分，結(jié)果驗(yàn)證效率直接影響著整個(gè)方案的效率。將來(lái)的工作是對(duì)查詢結(jié)果驗(yàn)證方法進(jìn)行改進(jìn)，以降低計(jì)算復(fù)雜度，進(jìn)一步提高查詢方案的效率。

[1] Hacigümüs H, Mehrotra S, Iyer B. Providing database as a service[C]//Proceedings of the 18th International Conference on Data Engineering. San Jose, USA, 2002: 29-40.

[2] Agrawal D, Abbadi A E, Emekci F, et al. Database management as a service: Challenges and opportunities[C]//Proceedings of the 2009 IEEE International Conference on Data Engineering.Washington DC, USA, 2009: 1709-1716.

[3] Ge T, Zdonik Z. Answering aggregation queries in a secure system model[C]//Proceedings of the 33rd International Conference on Very Large Data Bases. Vienna, Austria, 2007:519-530.

[4] Hacigümüs H, Iyer B, Li C, et al. Executing SQL over encrypted data in the database-service-provider model[C]//Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data. Madison. Wisconsin, USA, 2002:216-227.

[5] Agrawal R, Kiernan J, Srikant R. Order preserving encryption for numeric data[C]//Proceedings of the International Conference on Management of Data. Paris, France, 2004: 563-574.

[6] Mykletun E, Tsudik G. Aggregation queries in the Database-As-a-Service Model[J]. Lecture Notes in Computer Science, 2006, 4127: 89-103.

[7] Yang Z, Zhong S, Wright R. Privacy-preserving queries on encrypted data[C]//Proceedings of the 11th European Symposium on Research in Computer Security. Hamburg,Germany, 2006: 479-495.

[8] Emekci F, Agrawal D, Abbadi A E, et al. Privacy preserving query processing using third parties[C]//Proceedings of the 22nd International Conference on Data Engineering. Washington DC,USA, 2006: 27-36.

[9] Ye Q, Wang H, Tartary C. Privacy-preserving distributed set intersection[C]//Proceedings of the 3rd International Conference on Availability, Security and Reliability. Barcelona, Spain, 2008:1332-1339.

[10] Thompson B, Haber S, Horne W G, et al. Privacy-preserving computation and verification of aggregate queries on outsourced databases[J]. Lecture Notes in Computer Science, 2009, 5672:185-201.

[11] Mignotte M. How to share a secret[J]. Lecture Notes in Computer Science, 1983, 149: 371-375.

[12] Iftene S. General secret sharing based on the Chinese Remainder Theorem with applications in E-Voting[J]. Electronic Notes in Theoretical Computer Science, 2007, 186(14): 67-84.

[13] Pedersen T P. Non-interactive and information-theoretic secure verifiable secret sharing[C]//Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology.Berlin: Springer, 1992: 129-140.

[14] Merkle R C. A certified digital signature[J]. Lecture Notes in Computer Science, 1990, 435: 218-238.