基于身份的無對密文等值測試公鑰加密方案*

丁賓賓,曹素珍,丁曉暉,竇鳳鴿,馬佳佳

(西北師范大學計算機科學與工程學院，甘肅 蘭州 730070)

1 引言

云存儲技術[1]的普及幫助用戶降低了存儲成本,同時打破了地理位置和時間的限制，實現了用戶之間的數據共享。考慮到數據的敏感性，數據需要被加密后存儲在云端，傳統的數據加密技術[2]雖有效地保護了用戶隱私，但加密操作會破壞數據的自然結構，使得云服務器檢索密文數據變得困難。

2004年，Boneh等人[3]首次提出了帶關鍵字檢索的公鑰可搜索加密PEKS(Public key Encryption with Key word Search)方案，該方案允許用戶提供關鍵字陷門去查找云端包含特定關鍵字的密文。基于公鑰基礎設施PKI(Public Key Infrastructure)的可搜索加密方案，需要證書頒發機構發布和管理用戶證書，當用戶量較大時存在復雜的證書管理問題。基于身份密碼體制[4]的公鑰可搜索加密方案雖有效地解決了證書管理問題，但同時又帶來了密鑰托管的難題。2014年，Peng等人[5]提出了基于無證書密碼體制的公鑰可搜索加密方案，該方案中的私鑰由用戶選取的秘密值和密鑰生成中心KGC(Key Generation Center)產生的部分私鑰組成，解決了密鑰托管的問題。在查找云端密文時，傳統的PEKS方案要求待檢索的密文必須由同一公鑰加密而來，而云端多用戶環境下密文通常是由不同用戶使用不同的公鑰加密產生的，第三方不能直接對使用了不同公鑰加密的密文進行比較。比如在公司電子郵件系統中，每封電子郵件都帶有關鍵字密文標簽(普通、緊急和機密等)，這些關鍵字密文標簽都是由不同發送者使用不同接收者的公鑰加密得來的，若要對這些郵件按標簽進行分類管理，則傳統的PEKS方案已無法滿足此類應用需求。

針對這一局限，Yang等人[6]在CT-RSA(Cryptographers’ Track at the RSA)會議上首次提出了具有密文等值測試功能的公鑰加密PKEET(Public Key Encryption with Equality Test)方案，給定密文C1=Enc(M1,PK1)和C2=Enc(M2,PK2)，該方案通過Test(C1,C2)算法判斷M1=M2是否成立，實現了對不同公鑰加密所得密文間的比較。不足的是，PKEET未提供授權機制，任何人獲得密文后都可以執行等值測試操作，對用戶隱私安全構成了威脅。隨后，Tang等人[7-11]在PKEET方案基礎上進行拓展，提出了支持授權的密文等值測試加密方案。2016年，Ma[12]提出了基于身份的密文等值測試加密方案。在該方案中，用戶不用提前確認彼此的公鑰，而是基于對方公開的身份信息生成公鑰，解決了復雜的證書管理問題。2017年，吳黎兵等人[13]指出現有的密文等值測試加密方案多數基于單服務器構建，存在惡意服務器關鍵字猜測攻擊KGA(Keyword Guessing Attacks)[14]的風險，為此設計了一個基于身份的雙服務器密文等值測試公鑰加密方案，并對方案的計算開銷和通信開銷進行了評估，確保其能夠在資源受限的移動設備上運行。

現有的具有等值測試功能的公鑰加密方案多數借助于雙線性對實現，計算量大、效率偏低。本文設計了一個基于身份的無對密文等值測試公鑰加密PF-IBEET(Pairing-Free Identity-Based Encryption with Equality Test)方案。該方案利用直線實現加密、解密、授權和等值測試過程，擺脫了雙線性對的限制，提高了計算效率。同時，該方案是基于身份密碼體制構建的，解決了基于PKI體系構建的密文等值測試方案中所存在的證書管理問題。最后通過仿真實驗將本文方案與具有密文等值測試功能的方案進行了性能分析和比較，結果表明，所提方案具有良好的計算性能表現。

2 PF-IBEET方案模型

2.1 PF-IBEET方案系統模型

PF-IBEET方案包括密鑰生成中心(KGC)、用戶和云服務器3類實體，系統模型如圖1所示。

(1)密鑰生成中心KGC：負責生成系統參數paramas和系統主密鑰s，并為用戶和云服務器提供私鑰SK。

(2)用戶：生成密文并上傳到云端，同時上傳一個陷門給云服務器，用于執行等值測試操作。

(3)云服務器：存儲用戶上傳的密文，同時接收用戶的測試請求，對授權的密文執行等值測試操作。

Figure 1 System model

2.2 PF-IBEET方案形式化定義

PF-IBEET方案包括以下6個算法：

(1)Setup(1k):KGC輸入安全參數k，輸出系統參數paramas和系統主密鑰s，公開系統參數paramas，自身保留主密鑰s。

(2)密鑰提取算法：①用戶密鑰提取：KGC輸入主密鑰s和身份IDi，返回密鑰對(PKi,SKi)；②云服務器密鑰提取：KGC輸入系統參數paramas，返回云服務器的密鑰對(PKc,SKc)。

(3)加密算法：用戶運行該算法，輸入系統參數paramas、公鑰PKi和明文Mi，得到密文Ci。

(4)解密算法：用戶運行該算法，輸入系統參數paramas、私鑰SKi和密文Ci，得到明文Mi。

(5)授權算法：用戶運行該算法，輸出陷門Tdi。

(6)測試算法：云服務器運行該算法，輸入任意2個密文/陷門對(Ci,Tdi)和(Cj,Tdj)，判斷Ci和Cj是否對應同一明文。若是，返回1，否則返回0。

2.3 PF-IBEET方案安全模型

PF-IBEET方案的安全模型考慮以下2種類型的敵手：

(1)Type-I。該類型的敵手A1可以獲得陷門，但不能從密文恢復出明文。

(2)Type-II。給定2段明文M0和M1，敵手A2在未獲得陷門的情況下，不能判斷出密文是對其中哪段明文進行的加密。

針對上述2種類型的敵手，下面將通過挑戰者β與敵手A1和A2之間的游戲來給出本文方案的安全模型。

游戲1:

(1)Setup(1k)：β輸入安全參數k，生成系統參數paramas并將其發送給A1，自身保留主密鑰s。

(2)查詢階段1。

A1進行以下查詢：

①Hash查詢：A1向β提交所要查詢的身份IDi,β返回對應身份的哈希值。

②密鑰提取查詢：A1向β提交所要查詢的身份IDi,β運行密鑰提取算法，返回密鑰對(PKi,SKi)給A1。

③解密查詢：A1向β提交IDi的密文Ci,β運行解密算法，返回明文Mi給A1。

④授權查詢：A1向β提交所要查詢的身份IDi,β運行授權算法，返回陷門Tdi給A1。

(3)挑戰階段。

A1結束查詢階段1查詢后，β隨機選擇明文M∈{0,1}*，輸入用戶ID*的公鑰和明文M，運行加密算法，輸出挑戰密文C*給A1。

(4)查詢階段2。

該階段與查詢階段1類似，但存在以下限制：

①ID*不允許出現在密鑰提取查詢中；

②(ID*,C*)不允許出現在解密查詢中。

(5)猜測階段。

A1猜測C*對應的明文M*，若M*=M，則贏得游戲1，獲勝的優勢如式(1)所示：

(1)

定義1對任意的Type-I敵手A1，若贏得游戲1的優勢可忽略，則方案是OW-ID-CCA安全的。

游戲2:

(1)Setup(1k)：β輸入安全參數k，生成系統參數paramas并將其發送給A2，自身保留主密鑰s。

(2)查詢階段1。

A2進行以下查詢：

①Hash查詢：A2向β提交所要查詢的身份IDi,β返回對應身份的哈希值。

②密鑰提取查詢：A2向β提交所要查詢的身份IDi,β運行密鑰提取算法，返回密鑰對(PKi,SKi)給A2。

③解密查詢：A2向β提交IDi的密文Ci,β運行解密算法，返回明文Mi給A2。

④授權查詢：A2向β提交所要查詢的身份IDi,β運行授權算法，返回對應的陷門Tdi給A2。

(3)挑戰階段。

A2結束查詢階段1查詢后，選擇2段明文M0,M1∈{0,1}*給β，β隨機選擇b∈{0,1}，輸入用戶ID*的公鑰和明文Mb，運行加密算法，輸出挑戰密文Cb給A2。

(4)查詢階段2。

該階段與查詢階段1類似，但存在以下限制：

①ID*不允許出現在密鑰提取查詢中；

②(ID*,C*)不允許出現在解密查詢中；

③ID*不允許出現在授權查詢中。

(5)猜測階段。

A2輸出猜測值b*∈{0,1}，若b*=b，則在游戲2中獲勝，獲勝的優勢如式(2)所示：

(2)

定義2對任意的Type-II敵手A2，若贏得游戲2的優勢可忽略，則方案是IND-ID-CCA安全的。

3 PF-IBEET方案

3.1 PF-IBEET具體方案

PF-IBEET具體方案如下所示：

(5)授權算法：用戶運行該算法，輸入私鑰SKi=(xi,yi)、系統參數paramas和云服務器公鑰PKc，輸出陷門Tdi=xi。

(6)測試算法：假設用戶A的密文為Ci=(Ci,0,Ci,1,Ci,2,Ci,3)，A運行授權算法生成陷門Tdi=xi；用戶B的密文為Cj=(Cj,0,Cj,1,Cj,2,Cj,3)，B運行授權算法生成陷門Tdj=xj。

云服務器運行Test(Ci,Tdi,Cj,Tdj)算法得到如下結果：

xi,1‖xi,2‖yi,1‖yi,2=

Ci,3⊕H2(Ci,0,H1((Ci,0)Tdi),Ci,2)

xj,1‖xj,2‖yj,1‖yj,2=

Cj,3⊕H2(Cj,0,H1((Cj,0)Tdj),Cj,2)

點P1,i(xi,1,yi,1)和P2,i(xi,2,yi,2)確定直線方程fi(x)，點P1,j(xj,1,yj,1)和P2,j(xj,2,yj,2)確定直線方程fj(x)，驗證直線方程fi(x)=fj(x)是否成立。若成立輸出1，否則輸出0。

3.2 正確性

(1)加/解密一致性。

①Ci,0=gr;

②Y=gy;

③Ci,2=M⊕H1(Yr)。

Ci,2⊕H1((gr)y)=

Ci,2⊕H1(Yr)=

M⊕H1(Yr)⊕H1(Yr)=M

(2)授權/測試算法。

①對于任意2段密文Ci和Cj，如果Dec(Ci,SKi)=Dec(Cj,SKj)≠⊥，給定陷門Tdi和Tdj，則測試算法Test(Ci,Tdi,Cj,Tdj)=1成立；

②對于任意2段密文Ci和Cj，如果Dec(Ci,SKi)≠Dec(Cj,SKj)≠⊥，給定陷門Tdi和Tdj，則測試算法Test(Ci,Tdi,Cj,Tdj)=1可忽略。

4 安全性分析

定理1PF-IBEET方案在隨機預言模型下基于CDH困難假設達到了OW-ID-CCA安全。

證明對于Type-I敵手A1，構造一個多項式時間算法λ來解決CDH困難問題，給定三元組〈g,ga,gb〉，λ的目標是計算gab。在λ和A1的交互過程中，λ記錄A1的所有查詢和得到的回復。具體過程如下所示：

(1)Setup(1k)：對λ輸入安全參數k，返回系統參數paramas={G,g,q,H1,H2,H3,H4,H5,H6,H7}給A1，其中Hi(i=1,2,3,4,5,6,7)是λ控制的隨機預言機。

(2)查詢階段1。

A1進行多項式次查詢：

①Hash查詢：

②密鑰提取查詢：A1向λ提交所要查詢的身份IDi，λ返回SKi并發送給A1。

③解密查詢：A1向λ提交IDi的密文Ci,λ運行解密算法，返回明文Mi給A1。

④授權查詢：當A1查詢用戶IDi的陷門時，λ運行授權算法，返回陷門Tdi=xi給A1。

(3)挑戰階段。

A1結束查詢階段1查詢后，λ隨機選擇明文M∈{0,1}*，輸入ID*的公鑰PK=(gx,ga)和M并運行加密算法計算：Ci,0=gb，Ci,1=H1(gxb)，Ci,2=M⊕H1(gab)，Ci,3=(x1‖y1‖x2‖y2)⊕H2(Ci,0,Ci,1,Ci,2)，λ將挑戰密文C*=(Ci,0,Ci,1,Ci,2,Ci,3)發送給A1。

(4)查詢階段2。

該階段與查詢階段1類似，但存在以下限制：

①ID*不允許出現在密鑰提取查詢中；

②(ID*,C*)不允許出現在解密查詢中。

(5)猜測階段。

A1猜測輸出M*，若M*=M，λ輸出1，否則輸出0。

在上述模擬交互中，如果最終返回1，說明λ有能力計算出M←Ci,2⊕H1(gab)。即λ能夠解決CDH困難問題，這與CDH假設相矛盾，因此PF-IBEET方案是OW-ID-CCA安全的。

□

定理 2PF-IBEET方案在隨機預言模型下基于DDH困難假設達到了IND-ID-CCA安全性。

證明對于Type-II敵手A2，構造一個多項式時間算法λ來解決DDH困難問題，給定的四元組〈g,ga,gb,gc〉，λ的目標是計算gab=gc是否成立。在λ和A2交互的過程中，λ記錄A2的所有查詢和得到的回復。具體過程如下所示：

(1)Setup(1k)：對λ輸入安全參數k，返回系統參數paramas={G,g,q,H1,H2,H3,H4,H5,H6,H7}給A2，其中Hi(i=1,2,3,4,5,6,7)是λ控制的隨機預言機。

(2)查詢階段1。

A2進行多項式次查詢：

①Hash查詢：

②密鑰提取查詢：A2向λ提交所要查詢的身份IDi，λ返回SKi發送給A2。

③解密查詢：A2向λ提交IDi的密文Ci,λ運行解密算法，返回明文Mi給A2。

④授權查詢：當A2查詢用戶IDi的陷門時，λ運行授權算法，返回陷門Tdi=xi給A2。

(3)挑戰階段。

A2結束查詢階段1查詢后，λ隨機選擇明文M0,M1∈{0,1}*和隨機數n∈{0,1}，輸入ID*的公鑰PK=(gx,ga)和Mi運行加密算法計算：Ci,0=gb，Ci,1=H1(gxb)，Ci,2=Mi⊕H1(gc)，Ci,3=(x1‖y1‖x2‖y2)⊕H2(Ci,0,Ci,1,Ci,2)，λ將挑戰密文C*=(Ci,0,Ci,1,Ci,2,Ci,3)發送給A2。

(4)查詢階段2。

該階段與查詢階段1類似，但存在以下限制：

①ID*不允許出現在密鑰提取查詢中；

②(ID*,C*)不允許出現在解密查詢中；

③ID*不允許出現在授權查詢中。

(5)猜測階段。

A2輸出猜測值n*，若n*=n，λ輸出1，否則輸出0。

5 性能分析

本節從計算開銷和通信開銷2個方面對本文方案和文獻[12,15,16]方案進行了性能分析和比較。

為了對各方案進行性能評估，在實驗環境為Lenovo筆記本(AMD Ryzen 5 4600U with Radeon Graphics @2.10 GHz,16 GB內存,Linux操作系統)的平臺上進行了仿真模擬實驗，采用C語言編程，加密函數庫由PBC[17]提供。表1為基本運算耗費時間，其中TH為HashToPoint時間，Th為普通哈希運算時間，TE為指數運算時間，TM為點乘時間，TP為雙線性對運算時間。表2為各方案在加密、解密和測試階段的計算開銷對比。

Table 1 Time spent on basic operations

從表1可以看出，雙線性對運算時間最長，然后依次是HashToPoint運算、指數運算、點乘運算和普通哈希運算。從表2可以看出，在加密階段，本文方案和文獻[16]方案比文獻[12]和文獻[15]方案少了2個雙線性對運算，計算開銷較小；在解密階段，文獻[12]和文獻[15]方案比本文方案多出了2個雙線性對運算，同時本文方案比文獻[16]方案少了2個指數運算，本文方案計算開銷最小；在測試階段，文獻[12]方案有4個雙線性對運算，文獻[15]方案有2個雙線性對運算，文獻[16]和本文方案指數運算個數相同，但本文方案多出了3個普通哈希運算，由于普通哈希運算計算開銷較小，因此在該階段本文方案和文獻[16]方案計算開銷基本相同。從總耗時來看，本文方案的計算開銷要低于其他方案的，具有良好的性能表現。

表3為各方案在通信開銷方面的對比，|G|表示為G群中元素的比特長度，|Zq|表示Zq群中數的比特長度。在密鑰生成階段，本文方案與文獻[12]方案具有相同的公鑰長度，為G群中元素比特長度的2倍；在加密階段，文獻[12]方案和文獻[15]方案密文長度相同，同時本文方案的密文長度小于文獻[16]方案的密文長度；在陷門生成階段，各方案的通信開銷幾乎相同。

Table 3 Comparison of communication costs of each scheme

6 結束語

本文PF-IBEET方案通過直線實現消息加解密和密文等值測試過程，擺脫了雙線性對的限制，提高了方案計算效率。同時，本文PF-IBEET方案基于身份密碼體制構建，解決了基于傳統PKI體系的密文等值測試方案中所存在的復雜證書管理問題。不足的是本文PF-IBEET方案存在密鑰托管和密鑰撤銷的缺陷。針對該問題，未來將直線密文等值測試與無證書密碼體制相結合，利用無證書的優勢解決密鑰托管的問題。

Table 2 Comparison of calculation costs of each scheme