梁哲華 佟國(guó)香

（上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院 上海 200093）

1 引言

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

本文針對(duì)Deng 等提出的多用戶注冊(cè)方案，在陷門設(shè)計(jì)方面進(jìn)行了安全性分析，改進(jìn)了陷門設(shè)計(jì)算法和驗(yàn)證算法，提出一種陷門不可區(qū)分的多用戶注冊(cè)可搜索加密方案，并基于判定性子群假設(shè)和DBDH 假設(shè)，證明了敵手攻擊無(wú)法有效區(qū)分構(gòu)造的陷門。實(shí)驗(yàn)結(jié)果表明，提出的改進(jìn)方案效率高，陷門空間小。

2 預(yù)備知識(shí)

2.1 合數(shù)階雙線性群

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

1）雙線性：

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

2）非退化性：

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

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

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

2.2 判定性子群假設(shè)

構(gòu)造一個(gè)群生成器G ，定義如下分布：

其中D為一個(gè)公共的元組，如果有敵手A在某一多項(xiàng)式時(shí)間內(nèi)產(chǎn)生，且機(jī)率不限，則這一敵手能夠辨別T0和T1的概率如式（1）所示。

式（1）中λ的相關(guān)性是可忽略的。

2.3 DBDH假設(shè)

以素?cái)?shù)q 為階，構(gòu)造出兩個(gè)循環(huán)群G1和G2，e:G1×G1→G2為其中的雙線性映射。使用g 設(shè)置成群G1初始生成元，則有以下公式表示敵手區(qū)分e(g,g)abc和e(g,g)r的優(yōu)勢(shì)：

其中隨機(jī)選取a,b,c,r?Zp。

假如對(duì)任意概率多項(xiàng)式時(shí)間內(nèi)敵手A其優(yōu)勢(shì)可忽略，則DBDH假設(shè)成立。

2.4 SCF-PEKS基本概念

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

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

1）Setup（λ）。輸入可靠參數(shù)λ，構(gòu)造出全局參數(shù)gp。

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

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

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

6）Test（gp，C，skS，Tw）。將gp，關(guān)鍵字密文C，陷門Tw，服務(wù)器私鑰輸入，服務(wù)器將根據(jù)自身私鑰進(jìn)行查找匹配。若存在對(duì)應(yīng)值輸出1，否則輸出0。

3 可搜索加密方案分析

本節(jié)對(duì)文獻(xiàn)［15］中以合數(shù)階雙線性對(duì)為理論基礎(chǔ)，構(gòu)造出的服務(wù)于信息登記用戶公鑰可搜索加密方案進(jìn)行分析，考慮方案安全性與陷門相關(guān)性較強(qiáng)，故主要分析Trapdoor算法。

4 陷門不可區(qū)分可搜索加密方案

4.1 方案設(shè)計(jì)

本文方案具體構(gòu)造如下：

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

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

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

4.2 安全性證明

本節(jié)在抗選擇關(guān)鍵字攻擊等安全性依賴于判定性子群假設(shè)和DBDH 假設(shè)前提下［15］，對(duì)關(guān)鍵字陷門不可區(qū)分性進(jìn)行證明。

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

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

Game1：假設(shè)A為內(nèi)部攻擊者（服務(wù)器）。

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

2）Queryphase1：對(duì)任意關(guān)鍵詞w，敵手A 向B詢問(wèn)關(guān)鍵字陷門，B 運(yùn)行陷門生成算法Tw=Trapdoor（GP，skR，w），并將結(jié)果返回給敵手A。

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

4）Queryphase2：敵手A繼續(xù)對(duì)關(guān)鍵詞進(jìn)行陷門詢問(wèn)，但不能選擇w0和w1。

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

A攻破Game1的優(yōu)勢(shì)為

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

1）Setup：給定安全參數(shù)λ，運(yùn)行GlobalSetup（λ）算法生成系統(tǒng)參數(shù)gp，隨后運(yùn)行三個(gè)密鑰生成算法，得到用戶密鑰中心、服務(wù)器、接受者的公私鑰對(duì)（pkK，skK），（pkS，skS）和skR，模擬者B 將pkS和pkK發(fā)送給敵手A。

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

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

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

A攻破Game2的優(yōu)勢(shì)為

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

假設(shè)2 密鑰注冊(cè)中心不能成為敵手，其必是安全且忠誠(chéng)的。

引理1 若DBDH為困難性的理論假設(shè)，則攻擊者敵手A 無(wú)論處于何種概率，當(dāng)其使用的算法時(shí)間復(fù)雜度處于多項(xiàng)式級(jí)別，那么其可以辨別陷門內(nèi)關(guān)鍵詞的攻擊優(yōu)勢(shì)可視為0。

敵手和挑戰(zhàn)者的攻擊游戲如下：

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

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

4.3 性能分析

接下來(lái)列舉出一些經(jīng)典的可搜索加密方案，在各個(gè)方案之間，相互比較陷門尺寸大小、算法復(fù)雜度和陷門是否可以區(qū)分等，其中以 |G|、|GT|、|ZP|各指代G、GT、ZP中組成成員的空間尺寸，P指代雙線性對(duì)相關(guān)的運(yùn)算，E 代表為模冪情況下的運(yùn)算，H 指代hash 函數(shù)類型的計(jì)算，S-M 表示標(biāo)準(zhǔn)模型，表1為各方案對(duì)比結(jié)果。

表1 各方案對(duì)比數(shù)據(jù)表

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

5 結(jié)語(yǔ)

1）對(duì)于合數(shù)階的雙線性群理論基礎(chǔ)上提出的可注冊(cè)用戶公鑰可搜索加密方案進(jìn)行了陷門安全性研究，改進(jìn)了現(xiàn)有方案防御外部敵手使用選擇關(guān)鍵詞攻擊時(shí)的不足。

2）提出了合數(shù)階雙線性群理論基礎(chǔ)上，改進(jìn)安全性的多用戶的可搜索加密方案。方案性能對(duì)比表明，其陷門、密文尺寸良好、算法復(fù)雜度低、可多用戶使用。在無(wú)需安全信道傳輸?shù)幕A(chǔ)上可保證密文關(guān)鍵字的陷門不可區(qū)分性，可抗選擇關(guān)鍵字攻擊。

3）后續(xù)將在本文的基礎(chǔ)上擴(kuò)展應(yīng)用范圍，研究多關(guān)鍵字情況下的無(wú)安全信道可搜索加密方案。