基于合數階雙線性群的多用戶陷門不可區分可搜索加密方案?

梁哲華 佟國香

（上海理工大學光電信息與計算機工程學院 上海 200093）

1 引言

云存儲服務的不斷發展完善極大便利了人們的存儲需求，傳統的數據加密已無法滿足云存儲服務的效率需要，文獻［1～2］對信息時代及云服務的安全需求進行了詳盡的闡述。由于可搜索加密技術可以為云存儲服務提供針對密文數據進行檢索的方案，而成為近年來的研究熱點。Song 等［3］首先提出一種用于檢索加密數據文檔的算法，將明文分割成多個關鍵詞進行依次加密，但效率較低且容易暴露搜索信息。Boneh等［4］結合公鑰密碼提出一種PEKS 技術可以實現高效可搜索加密，該方案通過驗證郵件密文和陷門是否一致，提高了檢索效率。Waters 等［5］在此基礎上提出帶關鍵字的搜索公鑰加密技術，并應用于檢索加密日志。Golle等［6］進一步進行擴展，提出了查詢加密數據連接關鍵字的方案。Fang 等［7］提出一種無需使用隨機預言機而可以抗關鍵字猜測攻擊的可搜索加密算法。此外，針對PEKS方案存在消息傳遞依賴于預先構造傳輸信道的不足，Baek等［8］針對使用公鑰的可搜索加密去除傳輸過程中的信道，構造出一種方案SCF-PEKS，但該方案依賴于隨機預言機，安全性假設過強。Emura 等［9］根據匿名基于身份加密（Identity-Based Encryption，IBE）機制劃分密文結構，與SCF-PEKS 方案結合構造出更高效的無安全信道方案。徐磊等［10］構建了基于合數階的PEKS 方案，由于其方案的提出是基于靜態假設，而缺乏現實安全性。Li 等［11］在IBE 機制基礎上提出了一種無安全信道的高效可搜索加密算法。Deng 等［12］設計出一種可抵抗外部關鍵字攻擊的可搜索加密實現算法，具有良好的陷門尺寸。Emura 等［13］提出了一種基于隱向量加密、標簽加密和一次性簽名的多關鍵字SCF-PEKS通用構造方法。WU等［14］提出了一種無通道、無證書、可搜索的公鑰認證加密方案，并證明了使用內部關鍵字情況下，該方案在增強的安全模型中可以有效抵抗猜測攻擊。Deng 等［15］根據去除安全的消息傳輸通道的可搜索加密方案展開補充，建立了多用戶注冊機制方案，并滿足抗選擇關鍵字攻擊安全，然而該方案不能滿足陷門不可區分性，存在一定的安全缺陷。

本文針對Deng 等提出的多用戶注冊方案，在陷門設計方面進行了安全性分析，改進了陷門設計算法和驗證算法，提出一種陷門不可區分的多用戶注冊可搜索加密方案，并基于判定性子群假設和DBDH 假設，證明了敵手攻擊無法有效區分構造的陷門。實驗結果表明，提出的改進方案效率高，陷門空間小。

2 預備知識

2.1 合數階雙線性群

將安全參數λ輸入雙線性群的生成算法G中，可以得到階為N=p1p2p3的兩個群G和GT，其中p1、p2、p3為互不相同的素數。設雙線性映射為e:G×G→GT，其可以滿足下列性質：

1）雙線性：

?g,? ?G,a,b?ZN,e(ga,gb)=e(g,g)ab；

2）非退化性：

?g?G使得GT中e(g,g)有n階；

3）可計算性：映射e:G×G→GT可以被有效計算。

假設在群G和GT上，以及與其相關的雙線性映射e:G×G→GT在多項式時間內是可計算的，令Gp1，Gp2，Gp3分別表示G中階分別是p1，p2，p3的子群，對于i≠j，則有e(?i,?j)為GT中的一個單位元，其中?i?Gpi，?j?Gpj。且該群中每一個子群Gp1，Gp2和Gp3兩兩之間正交。

2.2 判定性子群假設

構造一個群生成器G ，定義如下分布：

其中D為一個公共的元組，如果有敵手A在某一多項式時間內產生，且機率不限，則這一敵手能夠辨別T0和T1的概率如式（1）所示。

式（1）中λ的相關性是可忽略的。

2.3 DBDH假設

以素數q 為階，構造出兩個循環群G1和G2，e:G1×G1→G2為其中的雙線性映射。使用g 設置成群G1初始生成元，則有以下公式表示敵手區分e(g,g)abc和e(g,g)r的優勢：

其中隨機選取a,b,c,r?Zp。

假如對任意概率多項式時間內敵手A其優勢可忽略，則DBDH假設成立。

2.4 SCF-PEKS基本概念

SCF-PEKS 在PEKS 的基礎上提出，彌補了PEKS 的安全性不足。主要包含三方參與者：發送者、服務器、接收者。發送者將關鍵詞加密并發送給云服務器，接收者對于將要查詢的目標關鍵詞生成陷門并發送給服務器。服務器接收兩方的信息對其進行匹配，執行搜索操作，將匹配的關聯文檔發送給接收者。在這一過程中，公私鑰對由服務器保管，發送者在加密過程中同時用到服務器和接收者的公鑰，接收者發送陷門的過程中不需要專用信道，可通過公開信道發送。服務器在收到陷門后，根據私鑰進行檢測和匹配。其模型定義如下。

定義1 不依賴可靠消息傳遞通道的公鑰可搜索加密方案（SCF-PEKS）由下列子算法步驟構成：

1）Setup（λ）。輸入可靠參數λ，構造出全局參數gp。

2）KeyGenS（gp）。將全局參數gp 作輸入，生成用于服務器使用的公鑰及私鑰組合（pks，sks）。

3）KeyGenR（gp）。輸入gp，輸出接收者密鑰對（pkR，skR）。

5）Trapdoor（gp，skR，w）。將全局參數gp，接收者私鑰skR，要搜索的關鍵字w 作為輸入，輸出陷門Tw。

6）Test（gp，C，skS，Tw）。將gp，關鍵字密文C，陷門Tw，服務器私鑰輸入，服務器將根據自身私鑰進行查找匹配。若存在對應值輸出1，否則輸出0。

3 可搜索加密方案分析

本節對文獻［15］中以合數階雙線性對為理論基礎，構造出的服務于信息登記用戶公鑰可搜索加密方案進行分析，考慮方案安全性與陷門相關性較強，故主要分析Trapdoor算法。

4 陷門不可區分可搜索加密方案

4.1 方案設計

本文方案具體構造如下：

1）GlobalSetup（λ）。以λ為 安 全 參 數，(N,G,GT,e)為雙線性映射的參數，N=p1p2p3為G和GT的階，且g 為G 的生成元。e 是G×G→GT的雙線性映射。選取一個抗碰撞的哈希函數H:{0,1}*→ZN。設關鍵詞空間為KSw={0,1}*，可得全局參數為GP=｛N，G，GT，e，H，KSw｝。

2）KeyGenKGC（GP）。用戶注冊中心生成公私鑰對，首先隨機選取β=ZN，g1,u?Gp1，計算X=e(g1,g1)β，Y=uβ，得到公私鑰分別為公鑰pkK={g1,X,Y,u}，私鑰skK=β。

由上式（4）、（5）證明可知，服務器通過自身私鑰可以計算出t 值，從而得以驗證密文和陷門是否相互匹配。通過前面的證明步驟可以發現，使用優化的算法步驟加強了基礎方案的計算過程，通過構造安全高效的算法冪次，能夠讓關鍵字陷門在被受到外部敵手嘗試破解的環境下，仍難以獲取陷門信息，無法對陷門進行區分，攻擊者破解冪次值后方可計算關鍵字，而這一數值需得知服務器私鑰才能獲取，從而保證了在多用戶注冊情況下密文檢索的安全性。

4.2 安全性證明

本節在抗選擇關鍵字攻擊等安全性依賴于判定性子群假設和DBDH 假設前提下［15］，對關鍵字陷門不可區分性進行證明。

定義2 選擇關鍵字攻擊（indistinguishability of SCF-PEKS against chosen keyword attack，IND-SCF-CKA）游戲。

以λ為安全參數，建立起關于敵手A 和模擬者B之間的攻擊游戲模型。

Game1：假設A為內部攻擊者（服務器）。

1）Setup：運行初始化算法GlobalSetup（λ），生成系統參數GP，隨后運行三個密鑰生成算法，得到用戶密鑰中心、計算中心、接受者這三種角色的密鑰組合（pkK，skK），（pkS，skS）以及skR，隨后模擬者B把（pkS，skS）和pkK傳輸給攻擊者敵手A。

2）Queryphase1：對任意關鍵詞w，敵手A 向B詢問關鍵字陷門，B 運行陷門生成算法Tw=Trapdoor（GP，skR，w），并將結果返回給敵手A。

3）Challenge：A 向B 發 送 挑 戰 關 鍵 詞 對（w0,w1），其中w0,w1都不能出現在Queryphase1中，B 隨機選取b?(0,1)，計算C*=SCF-PEKS（GP，pkS，pkK，wb），并將其作為挑戰密文發送給A。

4）Queryphase2：敵手A繼續對關鍵詞進行陷門詢問，但不能選擇w0和w1。

5）Guess：A 將猜測b′輸出，若b′=b，則敵手A獲得勝利，否則A失敗。

A攻破Game1的優勢為

Game2：假設A為外部攻擊者，則模擬攻擊游戲如下。

1）Setup：給定安全參數λ，運行GlobalSetup（λ）算法生成系統參數gp，隨后運行三個密鑰生成算法，得到用戶密鑰中心、服務器、接受者的公私鑰對（pkK，skK），（pkS，skS）和skR，模擬者B 將pkS和pkK發送給敵手A。

2）Queryphase1：A 自適應的選擇接收者的密鑰x?Z*N，在密鑰生成中心執行用戶密鑰生成操作，得到skR。

3）Challenge：敵手A 發送關鍵詞對（w0,w1），B隨機選取b?(0,1)，計算C* =SCF-PEKS（GP，pkS，pkK，wb），并將其作為挑戰密文發送給A。

4）Guess：A 將猜測b′輸出，若b′=b，則敵手A獲得勝利，否則A失敗。

A攻破Game2的優勢為

假設1 敵手的隨機詢問wi(i=1,2,…,q)每次都是不同的，且給定的R3可以完美的將陷門隨機化。

假設2 密鑰注冊中心不能成為敵手，其必是安全且忠誠的。

引理1 若DBDH為困難性的理論假設，則攻擊者敵手A 無論處于何種概率，當其使用的算法時間復雜度處于多項式級別，那么其可以辨別陷門內關鍵詞的攻擊優勢可視為0。

敵手和挑戰者的攻擊游戲如下：

4）Guess：敵手A 在獲取陷門后進行猜測，輸出猜 測b′ 。 若b′=b，則 有t=H(e(T1,Q)α)=H(e(g1,g1)abc)，T=e(g1,g1)abc，則T*w是正確的結果，返回“Yes”；否則T為GT中的任意組成成員，返回“No”。

若攻擊敵手A 可以辨別出關鍵詞陷門，則挑戰者B 能夠破解出DBDH 假設。綜合以上證明，本算法方案中針對不同關鍵詞構造的陷門對外部敵手不可區分，針對關鍵字能夠有效防御外部發起的猜測攻擊。同樣的，本方案可抗選擇關鍵字攻擊，滿足IND-SCF-CKA安全。

4.3 性能分析

接下來列舉出一些經典的可搜索加密方案，在各個方案之間，相互比較陷門尺寸大小、算法復雜度和陷門是否可以區分等，其中以 |G|、|GT|、|ZP|各指代G、GT、ZP中組成成員的空間尺寸，P指代雙線性對相關的運算，E 代表為模冪情況下的運算，H 指代hash 函數類型的計算，S-M 表示標準模型，表1為各方案對比結果。

表1 各方案對比數據表

從表1 可以看出，本文和文獻［11］、［15］方案陷門尺寸差距較小，密文尺寸接近，表現較為良好，而文獻［11］、［15］不滿足陷門不可區分性，雖然文獻［7］可滿足，但在驗證復雜度、密文結果獲取的復雜性程度、陷門以及密文的空間大小性能上都不如本文方案。綜合比較，本文中所提出的加密方案在陷門和驗證中的算法復雜度更優、陷門和密文安全性高，尺寸良好，在滿足多用戶注冊的同時，提高了可搜索加密方案的安全可靠程度。

5 結語

1）對于合數階的雙線性群理論基礎上提出的可注冊用戶公鑰可搜索加密方案進行了陷門安全性研究，改進了現有方案防御外部敵手使用選擇關鍵詞攻擊時的不足。

2）提出了合數階雙線性群理論基礎上，改進安全性的多用戶的可搜索加密方案。方案性能對比表明，其陷門、密文尺寸良好、算法復雜度低、可多用戶使用。在無需安全信道傳輸的基礎上可保證密文關鍵字的陷門不可區分性，可抗選擇關鍵字攻擊。

3）后續將在本文的基礎上擴展應用范圍，研究多關鍵字情況下的無安全信道可搜索加密方案。