無證書的可搜索加密方案

李 雙

北京工商大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，北京 100048

1 引言

在大數(shù)據(jù)的今天，為了實現(xiàn)數(shù)據(jù)的安全性，海量的數(shù)據(jù)大多加密存儲于第三方服務(wù)器上，對于這些加密數(shù)據(jù)的有效檢索是一個越來越被人們重視的現(xiàn)實問題。Boneh 等在2004 年利用匿名的基于身份加密方案構(gòu)造出來第一個公鑰可搜索加密方案[1]（Public Key Encryption with Keyword Search，PEKS）。2005年，Abdalla等對可搜索公鑰加密方案的一致性進(jìn)行了重新定義[2]。經(jīng)過多年的發(fā)展，2010年，Kamara和Lauter對構(gòu)建安全云存儲所需的密碼原型（包括可搜索公鑰加密方案）進(jìn)行了綜述[3]。2012年，Long等提出在全文檢索下構(gòu)建PEKS的方案[4]。2013年，Tseng等提出iPEKS[5]，使得搜索時間是不同關(guān)鍵詞的總數(shù)的線性關(guān)系，而且已搜索得到關(guān)鍵詞越多，搜索的效率越高。Hou 等利用“格”構(gòu)做新的PEKS 算法[6]。2014 年，李等基于屬性加密提出的可搜索加密方案[7]，可實現(xiàn)多用戶共享查詢。2015 年，Xu 等在云存儲環(huán)境下利用PEKS 構(gòu)建數(shù)據(jù)檢索系統(tǒng)[8]，采用雙系統(tǒng)加密技術(shù)減少方案的安全性問題。2017年，Liu等提出雙重陷門的基于身份的可搜索加密方案[9]。Shen等把訪問控制引入可搜索加密方案[10]。2019年，Jiang等給出關(guān)鍵詞可搜索基于身份的廣播加密方案[11]，該方案用于數(shù)據(jù)庫系統(tǒng)可以防范內(nèi)部攻擊。同年，Li等提出指定服務(wù)器基于身份的用于加密郵件的可搜索認(rèn)證加密方案[12]。Yin等給出基于密文策略的可搜索加密方案[13]。

2 基礎(chǔ)知識

定義1設(shè)G1表示素數(shù)階加法群，P為G1的生成元。G2為素數(shù)階乘法群，且它們的階數(shù)相同，記為q。如果映射e:G1×G1→G2滿足：

（1）雙線性（Bilinear）

對于任意Q,W∈G1和a,b∈Zp，都有：

對任意Q,W,Z∈G1，有：

（2）非退化性（Non-degenerate）

存在Q,W∈G1，使得e(Q,W)≠1G2。這里 1G2代表G2群的單位。

（3）可計算性（Computable）

存在有效的多項式時間算法對任意的Q,W∈G1，可計算e(x,y)的值，則稱映射e:G1×G1→G2是雙線性映射。

定義2設(shè)f為f:R→[ ]0,1 上的映射，滿足對任意的多項式g(s)和足夠大的s，有，則稱f為可忽略函數(shù)。

下述幾個密碼學(xué)困難問題，將構(gòu)成無證書可搜索加密方案的安全基礎(chǔ)。

計算雙線性Diffie-Hellman問題（BDH）：

給定(P,Pa,Pb,Pc)，其中a,b,c∈Zp隨機(jī)選取且未知,任意算法A計算e(g,g)abc∈G2的優(yōu)勢為?，如果：

判定雙線性Diffie-Hellman問題（DBDH）：

給定(P,Pa,Pb,Pc,Q)，其中a,b,c∈Zp隨機(jī)選取且未知，Q∈G2,P∈G1，任意算法A判斷是否Q=e(g,g)abc的優(yōu)勢為?，如果：

目前尚未有解決計算雙線性Diffie-Hellman 問題BDH的有效算法，普遍認(rèn)為BDH是一個困難問題，即計算和判斷雙線性Diffie-Hellman問題的優(yōu)勢是可忽略函數(shù)。通篇假設(shè)雙線性Diffie-Hellmen問題（BDH）是難解的。

3 無證書可搜索加密方案的定義

無證書的可搜索加密方案（CL-PEKS）是在基于身份的可搜索加密方案（Identity Based Public Key Encryption with Keyword Search，IBEKS）的基礎(chǔ)上結(jié)合無證書的加密技術(shù)提出來的，在不需要第三方證書認(rèn)證的情況下，實現(xiàn)對加密數(shù)據(jù)的關(guān)鍵詞的可搜索。

在CL-PEKS 體系中，用戶的初始私鑰存在密鑰生成中心KGC，每個用戶根據(jù)協(xié)議自己計算完整私鑰，避免了KGC擁有用戶完整私鑰的風(fēng)險。

3.1 CL-PEKS算法定義

定義3無證書的可搜索加密算法CL-PEKS由系統(tǒng)初始化(Setup)、密鑰生成(KeyGen)、密鑰擴(kuò)展(KeyExt)、關(guān)鍵詞加密(PEKS)、陷門生成(Trapdoor)、驗證(Test)多項式時間隨機(jī)算法組成。

系統(tǒng)初始化(Setup)：輸入系統(tǒng)初始參數(shù)λ；輸出系統(tǒng)公共參數(shù)Pub和系統(tǒng)主私鑰Msk。Setup 由KGC 來完成，假設(shè)系統(tǒng)參數(shù)是公開的，可被認(rèn)證，系統(tǒng)主私鑰由KGC秘密保存。

密鑰生成(KeyGen)：輸入用戶身份Id和系統(tǒng)主私鑰Msk；輸出用戶的初始私鑰IniPrivId。KeyGen由KGC執(zhí)行，并將IniPrivId保密傳送給用戶Id。

密鑰擴(kuò)展(KeyExt)：輸入用戶初始私鑰IniPrivId和用戶隨機(jī)選取的秘密值tId；輸出用戶公鑰PubId和用戶完整的私鑰PrivId，并且將公鑰PubId以安全的方式發(fā)布出去。KeyExt在用戶端執(zhí)行。

關(guān)鍵詞加密(PEKS)：輸入系統(tǒng)公共參數(shù)Pub和接收方的公鑰PubId與身份Id，關(guān)鍵詞w；輸出查詢關(guān)鍵詞的密文C。

陷門生成(Trapdoor)：輸入用戶身份Id，用戶完整私鑰PrivId和查詢關(guān)鍵詞w；輸出查詢關(guān)鍵詞w∈{0,1}*的陷門值Tw。

驗證(Test)：輸入系統(tǒng)公共參數(shù)Pub和用戶公鑰PubId，任何一個查詢關(guān)鍵詞w′的密文C=PEKS(Pub,PubId,Id,w′)和關(guān)鍵詞w的陷門值Tw=Trapdoor(Id,PrivId,w)；輸出判斷值b。如果b=1，此時判斷C是陷門值Tw對應(yīng)查詢關(guān)鍵詞w的密文；b=0，此時判斷C不是陷門值Tw對應(yīng)查詢關(guān)鍵詞w的密文。

對所有的λ∈N，任意關(guān)鍵詞，取遍明文空間w∈{0,1}*，全部用戶身份Id，取遍用戶身份空間，都有：

這里：

在CL-PEKS 中每個用戶的秘密值tId和完整私鑰PrivId由用戶獨立生成并在本地保管，因此避免了IBEKS中的密鑰托管問題。

3.2 攻擊游戲

下面討論無證書可搜索加密方案中的攻擊類型，主要涉及兩類攻擊[14]。

第一種情形：無證書的可搜索加密方案中不存在數(shù)字證書，在這種情況下假設(shè)敵手可以替換任意用戶的公鑰，并相應(yīng)地修改公鑰目錄，由于沒有證書授權(quán)CA，上述惡意攻擊行為將不會被發(fā)現(xiàn)。但敵手無法獲取系統(tǒng)主私鑰Msk。此過程稱為第一種情形攻擊。

第二種情形：有一個基本原則敵手在整個攻擊過程中不允許替換用戶公鑰，在此原則下，假設(shè)敵手可獲知KGC 的主密鑰Msk，并可得到用戶的全部私鑰。此過程稱為第二種情形攻擊。

攻擊過程敵手可以發(fā)起下列操作：

（1）敵手請求指定用戶初始密鑰：挑戰(zhàn)者執(zhí)行算法KeyGen(Msk,Id),輸出用戶的初始私鑰IniPrivId發(fā)送給敵手，此處用戶身份是敵手選定身份Id。

（2）敵手請求指定用戶完整私鑰：挑戰(zhàn)者執(zhí)行算法KeyExt(IniPrivId,tId)，得到完整私鑰PrivId發(fā)送敵手。如果用戶Id的公鑰被替換過，則游戲結(jié)束。

（3）敵手請求指定用戶公鑰：挑戰(zhàn)者運行KeyExt(IniPrivId,tId)，得到用戶Id的公鑰PubId回應(yīng)敵手。同時挑戰(zhàn)者在本地保存敵手請求過的公鑰PubId-list[(PubId,tId)]表。

（4）敵手替換指定用戶公鑰：用新的公鑰Pub′Id替換用戶Id的公鑰PubId。

（5）敵手請求關(guān)鍵詞w的陷門：如果用戶Id的公鑰PubId被替換過或者PubId沒有出現(xiàn)在PubId-list中，則游戲終止；否則挑戰(zhàn)者執(zhí)行KeyExt(IniPrivId,tId)，得到用戶Id的完整私鑰PrivId，生成關(guān)鍵詞w的陷門Tw。

針對第一種情形攻擊的幾點約束：

（1）敵手任何時刻都不能獲得挑戰(zhàn)者的私鑰；

（2）敵手不可請求某些用戶的私鑰，如果這些用戶的公鑰已經(jīng)被替換過；

（3）敵手在挑戰(zhàn)階段之前不能替換挑戰(zhàn)者的公鑰，在某些時期不能請求獲得挑戰(zhàn)者的初始私鑰；

（4）在第二階段敵手不能請求使用挑戰(zhàn)者私鑰生成的關(guān)鍵詞陷門。

針對第二種情形攻擊的幾點約束：

（1）敵手任何時刻都不能替換公鑰；

（2）敵手不能請求獲得挑戰(zhàn)者的私鑰；

（3）在第二階段敵手不能請求使用挑戰(zhàn)者私鑰生成的關(guān)鍵詞陷門。

上述約束條件貫穿整個攻擊過程。

敵手與挑戰(zhàn)者間進(jìn)行如下游戲：

初始化階段：挑戰(zhàn)者輸入系統(tǒng)參數(shù)λ，執(zhí)行算法Setup(1λ)輸出系統(tǒng)公共參數(shù)Pub并發(fā)送給敵手，如果敵手是第一種情形，挑戰(zhàn)者將系統(tǒng)主私鑰Msk秘密保存；如果敵手是第二種情形，挑戰(zhàn)者將系統(tǒng)主私鑰Msk發(fā)送給敵手。

第一階段：敵手可以向挑戰(zhàn)者作一系列q1,q2,…,qn次請求，可以獲得指定用戶的初始私鑰、全部私鑰、公鑰、替換公鑰、生成關(guān)鍵詞陷門的請求。如果攻擊是第二種情形，不允許敵手替換指定用戶公鑰。

挑戰(zhàn)階段：當(dāng)敵手決定第一階段終止，敵手發(fā)送挑戰(zhàn)者身份IdCh，關(guān)鍵詞w0,w1，請求得到關(guān)鍵詞w0,w1的密文。要求挑戰(zhàn)者IdCh不可以是已經(jīng)被敵手請求得到其私鑰的用戶身份。如果攻擊屬于第一種情形，挑戰(zhàn)者不能是已被替換公鑰或者已被請求得到其初始私鑰的用戶身份。滿足條件挑戰(zhàn)者隨機(jī)選取b∈{ }0,1 ，執(zhí)行算法C*=PEKS(PubIdChIdCh,wb)并發(fā)送關(guān)鍵詞密文給敵手。

第二階段：敵手繼續(xù)向挑戰(zhàn)者做一系列新的請求qn+1,…,ql。特別地，敵手不允許請求挑戰(zhàn)者IdCh的私鑰，如果屬于第一種情形攻擊，當(dāng)挑戰(zhàn)者IdCh的公鑰在第一階段已被替換，此時不允許敵手請求獲得挑戰(zhàn)者IdCh的初始私鑰，敵手只允許請求獲得第一階段沒有請求過的關(guān)鍵詞w的陷門。對于第二種攻擊情形，不允許敵手替換指定用戶公鑰。

猜測階段：敵手輸出猜測結(jié)果b′∈{ }0,1 。如果b′=b，則敵手贏得比賽。

定義4對于兩種情形不可區(qū)分選擇密文攻擊（INDCCA2）的優(yōu)勢函數(shù)為：

其中λ是系統(tǒng)安全參數(shù)。

定義5對任意多項式時間攻擊敵手破譯CL-PEKS的優(yōu)勢是可忽略函數(shù)，則稱CL-PEKS是選擇關(guān)鍵詞密文攻擊語義上安全的。

4 算法構(gòu)造

4.1 CL-PEKS算法構(gòu)造

構(gòu)造的無證書的可搜索加密方案CL-PEKS，采用了Terada的無證書公鑰密碼算法（CL-PKE）[15]中無證書的技術(shù)。設(shè)，其中q是群的階數(shù)為素數(shù)。e:G1×G1→G2是一個雙線性映射，選取有限域上橢圓曲線的Weil pairing 或者Tate分別是哈希函數(shù)，這里 0 ＜k＜n都是整數(shù)，CL-PEKS 由以下多項式時間算法構(gòu)成：

系統(tǒng)初始化：這一步在密鑰生成中心KGC 執(zhí)行。輸入系統(tǒng)初始化參數(shù)λ，隨機(jī)選取s∈；輸出系統(tǒng)隨機(jī)選取的橢圓曲線上加法群G1,G1=P，P是G1生成元，系統(tǒng)的主公鑰Pub=sP和主私鑰Msk=s。

密鑰生成：KGC運行算法KeyGen。輸入系統(tǒng)主私鑰用戶身份Id；輸出用戶的初始私鑰PrivIdL=sQ。

密鑰擴(kuò)展：用戶Id在本地運行算法KeyExt。輸入用戶初始私鑰PrivIdL，隨機(jī)選取tId∈并于用戶本地秘密保存；輸出用戶公鑰PubId=tIdP，用戶完整私鑰PrivId←(sQ,tId)。這步由用戶來完成，完整私鑰存儲于用戶本地，用戶公鑰PubId通過安全方式發(fā)送給KGC，由KGC發(fā)布出去。

關(guān)鍵詞加密：KGC運行算法PEKS。輸入系統(tǒng)公共參數(shù)Pub，用戶身份Id，公鑰PubId和查詢關(guān)鍵詞w；輸出查詢關(guān)鍵詞的密文C。預(yù)處理需要計算gr=查詢關(guān)鍵詞密文是一個四元組，C=rP,rQ,lP,(H4(t)||σ)⊕H2(rP,gr,lP)的計算式中“⊕”表示直和，其中σ∈{0 ,1}k是隨機(jī)數(shù)，H1(w),H4(t)分別是對應(yīng)的哈希函數(shù)，“||”表示連接。

陷門生成：查詢用戶運行Trapdoor。輸入用戶私鑰的秘密部分PrivId和查詢關(guān)鍵詞w；輸出查詢關(guān)鍵詞的陷門Tw=tIdH1(w) 。

驗證：服務(wù)器運行算法Test。輸入查詢關(guān)鍵詞密文C和關(guān)鍵詞w的陷門值Tw，輸出判斷值b。

具體計算過程如下。

首先計算：

V⊕H2(U,g′,W)，計算結(jié)果的前n-k比特是A，后k比特是B。由A和B可計算l=H3(A,B)，接下來驗證等式W=lP和A=H4(e(Tw,U))是否成立，輸出“1”表示“關(guān)鍵詞密文和關(guān)鍵詞陷門對應(yīng)同一查詢關(guān)鍵詞”；輸出“0”表示“關(guān)鍵詞密文和關(guān)鍵詞陷門對應(yīng)不同查詢關(guān)鍵詞”。此過程服務(wù)器無法獲知查詢關(guān)鍵詞的明文。

本文構(gòu)造的CL-PEKS不僅實現(xiàn)了對于加密關(guān)鍵詞的可搜索性，由于引入無證書的技術(shù)，避免了基于身份的可搜索加密方案（IBEKS）中用戶私鑰完全暴露給KGC的風(fēng)險。

4.2 CL-PEKS一致性分析

利用有限域橢圓曲線Weil pairing雙線性性質(zhì)：

4.3 CL-PEKS復(fù)雜度分析

這里分別比較無證書公鑰密碼算法CL-PKE[15]、基于身份的可搜索加密方案CL-IBEK4.1、關(guān)鍵詞可搜索公鑰加密方案PEKS[1]，如表1，三種密碼方案在進(jìn)行加密/（Crypt/PEKS）、解密/驗證（Decrypt/Test）、陷門（Trapdoor）的計算過程中涉及的雙線性對運算（P）、橢圓曲線群中的純量乘法（M）、指數(shù)運算（E）、哈希函數(shù)（H）四種運算次數(shù)；以及公鑰（Pub）、消息/關(guān)鍵詞明文（M/w）、消息/關(guān)鍵詞密文（Ciph）、關(guān)鍵詞密文（Tw）的二進(jìn)制表示比特數(shù)。這里假設(shè)哈希函數(shù)H2的輸出二進(jìn)制表示的比特數(shù)為n,g表示G1中點的二進(jìn)制表示的比特數(shù)。

表1 CL-PEKS運算量統(tǒng)計表

這里將CL-PEKS4.1與CL-PKE[15]進(jìn)行比較，可以看出CL-PEKS與CL-PKE的計算量基本相當(dāng)，并且實現(xiàn)了無需證書的對加密關(guān)鍵詞的可搜索功能，省去了CA認(rèn)證環(huán)節(jié)，避免了密鑰托管等問題。

5 結(jié)論

給出CL-PEKS 的定義、算法構(gòu)造以及算法的計算一致性和算法復(fù)雜度分析。算法的安全性基于BDH和GDH 等密碼學(xué)難題。因此，提出的CL-PEKS 方案具有對加密關(guān)鍵詞的檢索功能，解決了IBEKS方案中的密鑰托管問題。CL-PEKS方案還僅僅只是一個基礎(chǔ)的原型方案，隨后還會繼續(xù)深入探索該模型在隨機(jī)預(yù)言機(jī)模型下的安全性等問題。