無證書的可搜索加密方案

李 雙

北京工商大學 數學與統計學院，北京 100048

1 引言

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

2 基礎知識

定義1設G1表示素數階加法群，P為G1的生成元。G2為素數階乘法群，且它們的階數相同，記為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設f為f:R→[ ]0,1 上的映射，滿足對任意的多項式g(s)和足夠大的s，有，則稱f為可忽略函數。

下述幾個密碼學困難問題，將構成無證書可搜索加密方案的安全基礎。

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

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

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

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

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

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

無證書的可搜索加密方案（CL-PEKS）是在基于身份的可搜索加密方案（Identity Based Public Key Encryption with Keyword Search，IBEKS）的基礎上結合無證書的加密技術提出來的，在不需要第三方證書認證的情況下，實現對加密數據的關鍵詞的可搜索。

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

3.1 CL-PEKS算法定義

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

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

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

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

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

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

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

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

這里：

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

3.2 攻擊游戲

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

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

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

攻擊過程敵手可以發起下列操作：

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

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

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

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

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

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

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

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

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

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

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

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

（2）敵手不能請求獲得挑戰者的私鑰；

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

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

敵手與挑戰者間進行如下游戲：

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

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

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

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

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

定義4對于兩種情形不可區分選擇密文攻擊（INDCCA2）的優勢函數為：

其中λ是系統安全參數。

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

4 算法構造

4.1 CL-PEKS算法構造

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

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

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

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

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

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

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

具體計算過程如下。

首先計算：

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

本文構造的CL-PEKS不僅實現了對于加密關鍵詞的可搜索性，由于引入無證書的技術，避免了基于身份的可搜索加密方案（IBEKS）中用戶私鑰完全暴露給KGC的風險。

4.2 CL-PEKS一致性分析

利用有限域橢圓曲線Weil pairing雙線性性質：

4.3 CL-PEKS復雜度分析

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

表1 CL-PEKS運算量統計表

這里將CL-PEKS4.1與CL-PKE[15]進行比較，可以看出CL-PEKS與CL-PKE的計算量基本相當，并且實現了無需證書的對加密關鍵詞的可搜索功能，省去了CA認證環節，避免了密鑰托管等問題。

5 結論

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