CRSHE：基于同態加密的新型密文檢索方案*

付 偉，李墨泚，趙華容，吳 勇

(1.海軍工程大學信息安全系,湖北 武漢 430033;2.海軍密碼管理中心,北京 100841)

1 引言

云存儲(Cloud Storage)[1]是在云計算(Cloud Computing)[2]概念上延伸和發展出來的一種新興網絡存儲技術。它采用網格技術、分布式文件系統、集群應用、虛擬化等功能，用軟件來控制網絡中大規模異構存儲設備，并向遠程用戶提供按需服務的海量數據存儲、訪問和處理功能[3]。云存儲大大節約了存儲硬件和軟件開銷，減少了維護人員投入，具有低成本、高利用率等突出優點。同時，專業的云存儲服務提供商具有普通用戶無法比擬的技術和管理水平，可以為用戶提供更好的冗余備份、災難恢復等數據安全服務。

為了防止隱私泄露，用戶通常選擇將數據加密后再上傳至云存儲平臺，由自己保管解密密鑰，例如政府文件、全民醫療健康數據、企業商業機密相關文件、個人隱私數據等。然而，經過加密處理后的數據會失去原始明文所具有的一些特性，如有序性、相似性等，導致傳統基于明文的檢索方案在加密云存儲系統中無法正常工作。為此，研究人員提出基于密文的安全檢索問題。技術思想主要分為兩類：第一類是基于索引文件的檢索方法[4 - 6]，第二類是基于匹配的檢索方法[7 - 10]。然而，這兩種方法或者需要維護復雜的索引結構，或者檢索效率較低，難以滿足云存儲環境下對海量密文數據的檢索需要。

同態加密是一種可以直接對密文數據進行處理的加密方法[11 - 14]，可以在有效保護用戶敏感數據隱私性的前提下直接對密文實施加法和乘法等同態操作，并在操作的同時保持該密文對應的明文順序。但是，同態加密方案需要極大的計算開銷。如何設計運算開銷較小、方便索引的同態密文檢索方案是當前研究的難點。

本文針對云存儲數據管理需求提出一種面向密文存儲與檢索的云存儲模型，并在基于整數的同態加密方案基礎上設計了一種新型加密方案，提出一種新型基于同態加密的密文檢索CRSHE(Ciphertext Retrieval Scheme based on Homomorphic Encryption)。

2 國內外研究現狀

隨著云存儲應用領域的不斷拓展，針對密文數據檢索的研究成為當前研究的熱點之一。目前，針對加密數據的檢索技術主要分為兩類：

第一類是基于索引文件的檢索方法，即為關鍵詞建立安全索引，通過檢索索引查詢關鍵詞是否存在，判斷加密數據中是否包含檢索關鍵詞。Boneh等[4]基于雙線性映射提出一種可檢索的公鑰加密方案SPKE(Searchable Public Key Encryption)，但每次檢索時服務器都需要對加密數據文件進行線性掃描，以獲得檢索結果，查詢效率較低。Goh[5]提出使用Bloom filters構造文件的索引，但存在一定的錯判率。為了獲取更高效的搜索性能，Chang等[6]為整個文件集合建立一個單一的加密Hash表索引，但是這種基于詞頻的方案查詢會大大增加服務器端的開銷。

第二類是基于匹配的檢索方法，即通過逐一掃描加密后的數據文件，從中尋找與檢索關鍵詞匹配的單詞，從而定位出所需要的文件。Song等[7]提出了一種可檢索的序列加密方法，其線性搜索方案實質上是一次一密的加密信息檢索算法，抗統計分析的能力不足，且逐次匹配密文信息使得這種檢索方法在大數據集、特別是多關鍵詞查詢時計算量巨大。Goh[5]提出一種基于安全索引的檢索方案，但其索引結構構建和維護開銷較大。此外，Lin 等[8]提出一種基于通配符(Wildcard-based)的云端加密數據的模糊關鍵詞檢索技術，部分解決了模糊密文檢索問題，但是需要語義庫的支持。Boneh等[9]提出一種基于公鑰加密的關鍵詞查找方案PEKS(Public-key Encryption with Keywork Search)，但是該方案需要將查詢對象和查詢關鍵詞逐個比對，不適合于數據量大、檢索范圍不確定的加密文本檢索。

此外，研究人員還提出基于可搜索加密的檢索方法，即通過設計特殊的加密機制，利用陷門信息對密文直接執行搜索操作。1978年，Rivest等[10]首次提出同態加密的概念，但是直到2009年才由IBM的Gentry從數學上提出了全同態加密的可行方法[11]。隨后他又和他人合作提出了兩個整數上的全同態加密方案DGHV[12]和CAFED[13]。然而這三種方案的效率非常低下，都需要增加上萬億倍的運算量。Byun等[14]提出一種基于雙線性對的檢索方案，需要對每個文件計算雙線性對，并不適合大量文件的云應用環境。Cash等[15]提出一種同時支持布爾查詢和海量數據的方案，但該方案不能保證陷門的不可關聯性。Chang等[16]在可搜索對稱加密的安全定義基礎上給出了一種基于模擬的安全性定義，但該定義不能抵御敵手進行適應性詢問后的攻擊。

在國內，蔡克等[17]提出了一種基于單斷言的安全密文區間檢索方案。該方案提供了一種唯密文條件下的區間密文檢索方法，安全性較好、效率較高。但是，其密文區間檢索方案限于唯密文的場景，對于服務器了解敏感數據相關背景或服務器了解部分索引與敏感數據的對應關系等場景均未涉及。宋偉等[18]基于B+樹構建了一種安全密文全文索引結構，并在此基礎上提出一種基于密文的全文檢索方案Mimir，可以有效地抵御已知明文攻擊、選擇明文攻擊和詞頻統計攻擊。Li等[19]提出一種改進的基于整數同態加密的密文檢索方案，可實現單關鍵字的密文檢索。該方案對基于整數的同態加密算法進行了簡化，服務器能夠以較小代價破解獲得密鑰，故安全性有待加強。

傳統密文檢索技術雖然能夠初步滿足查全率和查準率的需求，但是檢索效率普遍不高，也不能滿足多關鍵詞查詢和結果排序等要求。與上述方案相比，本文提出的基于全同態加密的密文檢索機制基于同態加密機制，并添加偽隨機噪聲，可以有效地抵御已知明文攻擊、選擇明文攻擊和詞頻統計攻擊，能夠保護使用者的數據隱私和檢索關鍵字安全，并能夠在多關鍵詞檢索時提升檢索效率，具有一定的應用前景。

3 CRSHE機制設計

CRSHE機制包括加密方案CRSHE_Enc、解密方案CRSHE_Dec、單關鍵字檢索方案CRSHE_Rtr和多關鍵詞檢索方案CRSHE_RMK4個部分。

3.1 模型與符號定義

通常情況下，云存儲服務提供方會忠實履行服務承諾，為用戶提供有質量保障的存儲服務；它不會對用戶上傳的密文數據實施唯密文攻擊破譯或者故意實施篡改、刪除等攻擊行為。然而，它卻會有意收集用戶的訪問行為、操作記錄、敏感信息等數據。

針對密文存儲與檢索需求，本文提出一種支持檢索與共享訪問功能分離的云存儲系統模型。該模型包括云存儲系統、數據擁有者、數據檢索者和數據共享者4個角色，如圖1所示。

Figure 1 A cloud storage model for encrypted data retrieval and sharing圖1 面向密文檢索與共享的云存儲模型

圖1中，云存儲系統為大量用戶管理海量的密文數據文件；數據擁有者將自己的數據加密后上傳至云存儲系統，他可以自己檢索或者下載數據，也可以將檢索權限和密文共享權限分別指派給自己的合作者，包括數據檢索者和數據共享者；數據檢索者只能通過關鍵詞在云存儲中檢索感興趣的密文，但是不能獲得明文；而數據共享者則只能對獲得的密文進行解密，但無法執行搜索操作。與現有其它模型相比，該模型實現了搜索和解密功能的分離，更有利于保護用戶的隱私數據。本文所使用的符號定義如表1所示。

Table 1 Symbol definition表1 本文所用符號定義表

3.2 基本函數

(1)密鑰生成函數：GenKey(π)→P，Q，g，x。

令π為系統參數集合，該函數隨機生成兩個安全大素數P、Q作為密鑰(Q>P)；然后尋找ZP的生成元g，并選擇秘密數x使得gx為有限半群〈ZP,*〉的一個冪等元。

(2)偽隨機函數：ψκ(π)→R。

令κ為用戶保管的、數據m對應的密鑰，在每次使用加密函數Encrypt之前，該函數生成一個長度為|R|位的偽隨機整數R。

(3)加密函數：Encrypt(m)→c。

給定安全大素數P、Q和隨機數R,m是長度為l的明文分組所對應的整數，據式(1)計算：

c=mgx+RP+RPQ

(1)

可得到m對應的密文c(注意Q≥P>m)。

(4)解密函數：Decrypt(c)→m。

給定安全大素數P和密文c,據式(2)計算:

m=cg-xmodP

(2)

可得到c對應的明文m。

3.3 數據加密方案CRSHE_Enc

(1)系統參數生成。使用GenKey()函數生成與m對應的大素數P、Q及秘密數x、g，使用函數ψκ(π)生成用于檢索的偽隨機整數R。

(2)明文分組。用戶首先將明文進行分組，分組長度為l，即：M=m1m2…mr，r=|M|/l。

(3)分組加密。分別對每個明文分組mi實施Encrypt()運算，得到對應的密文分組ci=migx+RP+RPQ，1≤i≤r。

(4)密文上傳。先將密文分組拼接起來形成完整密文C=c1c2…cr，然后將文件C和安全大素數Q一起發送給服務器保存。

3.4 密文解密方案CRSHE_Dec

(1)密文下載。用戶向云存儲服務器請求下載密文文件C；用戶收到C后，對密文消息進行分組，得到C=c1c2…cr。

(2)密文分組解密。針對每個密文分組ci，使用安全大素數P和解密算法Decrypt()獲得解密結果mi。

(3)明文重組。將所有明文分組按照分組順序拼接，得到原始明文M=m1m2…mr。

3.5 單關鍵字密文檢索方案CRSHE_Rtr

(1)檢索請求生成。針對安全大素數P和檢索關鍵詞k，用戶計算檢索關鍵詞對應的密文K= (kgx+RP+RPQ)modQ=(kgx+RP)modQ，然后將K作為搜索請求上傳至云存儲服務器。

(2)密文檢索過程。云存儲服務器從加密文件C中依次讀取密文分組ci(1≤i≤r)，計算密文分組累乘積И=Πci，并計算И/KmodK。若結果為0，則表示關鍵詞檢索命中，檢索計數器count加1；否則為未命中。

(3)排序并返回檢索結果。令И=И/K，再次計算И/KmodK。如果結果仍為0，則檢索計數器count加1；否則搜索結束。在對所有文檔執行搜索后，云存儲服務器依據count的大小對包含關鍵詞的文檔進行排序，并將count和對應文件的下載地址返回給檢索用戶，以反映不同文件的相關程度。

注意：檢索用戶并不能獲得文檔明文，只有數據擁有者將密鑰P及秘密數x、g共享給檢索用戶時，他才能夠正確解密并獲得原始明文。

3.6 多關鍵字密文檢索方案CRSHE_RMK

(1)檢索請求生成。針對安全大素數P和檢索關鍵詞Ki(1≤i≤t)，計算檢索用戶計算關鍵詞密文乘積K=Π(Kigx+RP+RPQ)modQ=Π(Kigx+RP)modQ，然后將K作為搜索請求上傳至云存儲服務器。

(2)密文檢索過程。云存儲服務器從加密文件C中依次讀取密文分組ci(1≤i≤r)，計算密文分組累乘積И=Πci，然后計算И/KmodK。若結果為0，則表示多關鍵字檢索命中，檢索計數器count置1；否則為未命中，count置0。

(3)返回檢索結果。在對所有文件執行搜索后，云存儲服務器將count值為1的文件下載地址返回給用戶。

4 CRSHE方案理論分析

4.1 正確性分析

定理1在CRSHE機制中，持有密鑰P、Q及秘密數x、g的用戶可恢復明文M。

證明對任意明文分組mi，由于P>mi，因此對應密文c的解密結果Decrypt(c) =cg-xmodP= (migx+RP+RPQ)g-xmodP=mi。顯然，將所有分組mi按順序拼接起來即可還原成明文M。證畢。

□

定理2CRSHE_Enc為全同態加密方案。

證明給定兩個分組mi和mj，其對應的密文分別是：ci=migx+RiP+RiPQ和cj=mjgx+RjP+RjPQ，以下分別證明CRSHE機制支持加法同態及乘法同態。

(1)因Encrypt(mi+mj)=(mi+mj)gx+RP+RPQ，另一方面，Encrypt(mi)+Encrypt(mj)=migx+RiP+RiPQ+mjgx+RjP+RjPQ=(mi+mj)gx+(Ri+Rj)P+(Ri+Rj)PQ，故Decrypt(Encrypt(mi+mj))=(mi+mj)gxg-x=mi+mj=Decrypt(Encrypt(mi)+Encrypt(mj))，因此該方案滿足加法同態。

(2)因Encrypt(mi*mj)=mimjgx+RP+RPQ，所以：Decrypt(Encrypt(mi*mj))=mimjgxg-xmodP=mimj；此外，Encrypt(mi)*Encrypt(mj)=(migx+RiP+RiPQ)*(mjgx+RjP+RjPQ)g-x=mimjg2x+ (miRjgx+mjRigx+miRjgxQ+mjRigxQ)P+(RiRj+2RiRjQ+RiRjQ2)P2，則Decrypt(Encrypt(mi) *Encrypt(mj))=mimjg2xg-xmodP。考慮到gx是有限半群〈ZP,*〉的冪等元，則g2xmodP=gxmodP，故Decrypt(Encrypt(mi*mj))=Decrypt(Encrypt(mi) *Encrypt(mj))，因此該方案同樣滿足乘法同態。

由于減法和除法可以由加法和乘法分別實現，因此該方案為全同態加密方案，證畢。

□

4.2 安全性分析

(1)密文數據安全性。

由于服務器只能從用戶得到C和Q，服務方只能獲得 (mgx+RP)modQ。一方面，密鑰P是對服務器保密的，且通過隨機數R施加噪聲干擾；另一方面，即使服務器通過多組mgx+RP成功猜測到P，但是由于其不知道具體的g及x，因此依然不能獲悉原始數據m。可見CRSHE機制通過雙重安全機制有效保護了用戶數據隱私。

(2)檢索關鍵詞安全性。

用戶向服務器提交的檢索請求是通過P、g及x的轉換之后的密文，在無法獲得P和g及x的前提下是無法獲得關鍵詞明文M的，保證了用戶檢索關鍵詞的安全性。同時，服務器在執行檢索的過程中只是對密文進行操作，全程無法獲悉用戶數據和關鍵詞的明文，實現了密文檢索的功能。

(3)保密參數安全性。

在生成系統保密參數時，必須考慮密鑰P要有足夠大的密鑰空間，以防止密鑰P、g、x被窮舉攻破。但是,P越大，帶來的運算開銷將越大。如何在效率和安全性之間達到較好的平衡是本機制需要重點解決的問題之一。

4.3 效率分析

CRSHE機制的檢索效率與關鍵字長度密切相關。對于固定長度的文件，在對明文M進行分組時，分組長度越大，則劃分的分組越少，檢索循環次數相應越少；反之，則劃分的分組越多，檢索時需要的循環次數也越多。同時，在分組時有可能正好將關鍵字劃分到不同的分組中，導致不能正確檢索到該關鍵字，因此檢索準確率并非100%，而是隨著劃分組數的增加而減小。如何設計合理的分組長度也是本方案的難點問題之一。

此外，由于CRSHE機制支持多關鍵詞聯合查詢，因此較其他方案可顯著提高檢索效率。

5 方案測試與實驗分析

5.1 實驗環境構建

為了檢驗方案的正確性與效率，搭建了一個由1個NameNode和15個DataNode組成的Hadoop云存儲實驗系統。服務端結點采用IBM X3650M2機架式服務器，具有4 GB DDR3內存和2個146 GB SAS硬盤，Ubuntu 10.0.2系統；客戶端采用普通PC機，配備1 GB內存和160 GB硬盤，Windows 7操作系統；所有結點連接在百兆局域網中。通過反復實驗對比，確定密鑰P和大素數Q的長度為512位,關鍵字長度和明文分組長度均設為32位。

5.2 檢索效率測試

通過建立不同關鍵詞數量的索引，對方案的檢索效率進行測試，并與經典線性密文檢索方案SSKE(Sequential Searching on Keyword Encrytion)[7]進行比較。以100篇純中文文本文檔為測試樣本，每個文檔平均為2 MB。在測試過程中將關鍵詞長度確定為2個中文字符，對應為32位的二進制數；數量從1個逐步增加到5個。在每種索引關鍵詞數量下分別進行50次檢索測試，取其平均時間為最終結果。

將SSKE方案在Hadoop測試平臺上進行了代碼實現，使用相同的安全參數。由于該方案不支持多關鍵詞索引，因此需要多次執行單關鍵詞索引，然后累加所需時間。測試結果如表2所示。

Table 2 Performance comparison between the two retrieval schemes表2 兩種不同方案的檢索效率對比

可見，兩種方案的單關鍵詞檢索效率相差不大，CRSHE稍快；但是隨著當索引數量增加，CRSHE返回結果所用時間增長較為緩慢，而SSKE方案由于不支持多關鍵詞索引，需要多次執行單關鍵詞索引，故其所需時間大致成線性增長。

5.3 檢索準確性測試

如上所述，在密文分組時有可能正好將關鍵字劃分到不同的分組中，導致檢索準確率會低于100%。仍以上述100篇文本文檔為測試樣本，對CRSHE機制的檢索準確性進行測試。每個數量隨機抽取10種不同的關鍵字組合，分別進行50次測試并記錄平均準確率，測試結果如表3所示。

Table 3 Test result of retrieval accuracy rate表3 CRSHE機制檢索準確性測試結果

可見，隨著關鍵詞數量增加，CRSHE機制的準確率有一定的下降，但綜合檢索準確率都在88%以上。

6 結束語

與傳統的數據存儲方式相比，云存儲具有低成本、可擴展、快速伸縮和利用率高等特征，使得云存儲得到了越來越多的關注和支持。但是，如果不能妥善解決云存儲中的安全問題，特別是基于密文的高效檢索問題，將會嚴重制約云存儲應用的可持續發展。本文針對這一緊迫問題，提出一種基于全同態加密的密文檢索機制CRSHE，通過兩重機制對明文加密，可以在不恢復加密明文信息的情況下實施近似精確的密文檢索，并實現了結果的排序。該方案不但保護了使用者的數據安全，同時全同態算法在多關鍵詞檢索時能較大地提升檢索性能，具有一定的應用前景。