電子郵件系統中指定服務器的關鍵字搜索加密方案

牛淑芬,楊平平,謝亞亞,王彩芬,杜小妮

(西北師范大學 a.計算機科學與工程學院; b.數學與統計學院,蘭州 730070)

0 概述

近年來,隨著云計算技術[1]的迅速發展,基于網上在線存儲的云存儲服務得到廣泛關注。將本地數據遷移到云端服務器可以節省本地數據管理開銷、降低系統開發及維護成本[2],但同時也產生了數據泄露、個人隱私信息無法得到有效保護等安全問題。此外,為了確保數據的機密性,數據擁有者在上傳數據至云端服務器前會對其進行加密,導致數據使用者難以在加密文件中快速查找信息。

為解決上述問題,研究人員提出可搜索加密 (Searchable Encryption,SE)技術[3-5]。可搜索加密體制分為對稱可搜索加密體制和公鑰可搜索加密體制[3]。文獻[4]提出對稱可搜索加密方案,隨后文獻[6]提出公鑰關鍵字搜索加密(Public Key Encryption with Keyword Search,PEKS)概念,并結合公鑰加密技術設計出基于雙線性對的構造方案。該方案以郵件路由為應用場景以便郵件服務器對郵件進行分發,數據發送者從待發送的電子郵件中通過檢索關鍵字與使用數據接收者公鑰對關鍵字和電子郵件進行加密,數據接收者生成陷門并向郵件存儲服務器發送相應陷門,郵件存儲服務器搜索與其匹配的關鍵字密文,并將包含關鍵字的郵件密文返回給數據接收者[3]。

在加密的電子郵件系統中,帶關鍵字搜索的公鑰加密方案是在不解密情況下搜索加密郵件的有效手段,但是其存在安全問題。文獻[7]指出PEKS方案和結合域關鍵字搜索的公鑰加密(Public Key Encryption with Conjunctive Field Keyword Search,PECKS)方案[8]中存在離線關鍵字猜測攻擊(Keyword Guessing Attack,KGA)風險。惡意敵手能在離線狀態下采用窮舉法搜索候選關鍵字[9],并分別對其進行驗證。研究人員通過實驗發現,該攻擊具有可行性。如果郵件服務器變得惡意,其可以通過離線啟動KGA從用戶郵件中恢復信息[10]。文獻[11]研究了基于身份的關鍵字搜索加密(Identity Based Encryption with Keyword Search,IBEKS)方案,并對IBEKS方案進行定義。該文獻指出,數據發送者使用基于身份的加密 (Identity-Based Encryption,IBE)方法對電子郵件進行加密,并使用IBEKS方案加密關鍵字,然后將加密的電子郵件和關鍵字上傳到郵件存儲服務器[12-13],數據接收者為檢索包含某個關鍵字的電子郵件,委托郵件服務器提供陷門搜索加密的關鍵字,郵件服務器將與加密關鍵字關聯的電子郵件返回給數據接收者作為搜索結果。但是由于IBEKS方案無法抵抗內部離線關鍵字猜測攻擊[14],同時還隱藏了外部敵手搜索模式,因此文獻[15]提出一種指定服務器的基于身份關鍵字搜索加密(designated Server Identity-Based Encryption with Keyword Search,dIBEKS)方案,然而文獻[16]指出該方案不能滿足關鍵字密文的不可區分性。

為提高dIBEKS方案的安全性,本文提出一種指定郵件服務器的基于身份認證關鍵字搜索加密(designated Server Identity-Based Authenticated Encryption with Keyword Search,dIBAEKS)方案。在未知數據發送者私鑰的情況下,攻擊者難以偽造數據發送者加密的關鍵字,從而無法進行離線關鍵字猜測攻擊,對該方案適應性選擇消息攻擊的關鍵字密文不可區分性、陷門不可區分性和離線猜測攻擊的安全性進行驗證。

1 基礎知識

1.1 雙線性對

令(G1,+)和(G2,×)為2個階均為大素數q的循環群,p是群G1的生成元。

定義1(雙線性對[17]) 循環群上線性映射e:G1×G1→G2具有以下性質:

2)非退化性。存在P,Q∈G1,滿足e(P,Q)≠1。

3)可計算性。對于任意P,Q∈G1,存在1個有效算法計算e(P,Q)。

1.2 困難性問題假設

本文方案采用雙線性Diffie-Hellman計算(Computational Bilinear Diffie-Hellman,CBDH)假設[18]。

AdvCBDH(R)=Pr[R(P,aP,bP)=e(P,P)ab]

(1)

其中,e(P,P)ab的概率優勢可以忽略。

2 系統模型和安全模型

2.1 系統模型

圖1為dIBAEKS方案的電子郵件系統模型。該模型主要包括數據發送者A、數據接收者B、指定郵件服務器S[19]以及可信任的密鑰生成中心(Private Key Generator,PKG)4個實體。其中:數據發送者A對數據文件進行加密,使用其私鑰skA為加密的數據文件生成關鍵字索引Cw,并將數據密文與關鍵字索引Cw共同上傳到指定郵件服務器S;數據接收者B用其私鑰skB生成陷門Tw,并將陷門Tw發送給指定郵件服務器S進行搜索服務請求;指定郵件服務器S為加密的電子郵件提供存儲服務并利用其私鑰sks完成數據接收者B的搜索請求;可信任的密鑰生成中心PKG主要負責生成主密鑰s和系統公共參數Params,并根據用戶身份信息生成用戶密鑰。

圖1 dIBAEKS方案的電子郵件系統模型Fig.1 Email system model of dIBAEKS scheme

dIBAEKS方案由以下5個概率多項式時間算法組成:

1)系統建立算法Setup(λ):給定1個安全參數λ,產生PKG的主密鑰s和系統公共參數Params。

2)密鑰生成算法KeyGen(Params,s,IDA,IDB,IDS):輸入系統公共參數Params、主密鑰s和身份信息(IDA、IDB、IDS),PKG生成各身份對應的密鑰(pkA,skA)、(pkB,skB)和(pkS,skS)。

3)關鍵字加密算法dIBAEKS(Params,w,skA,IDB,IDS):對于關鍵字w,數據發送者結合數據接收者的身份信息IDB和指定郵件服務器的身份信息IDS,計算生成密文Cw。

4)陷門生成函數dTrapdoor(Params,w′,IDA,IDS,skB):對于給定搜索的關鍵字w′,數據接收者使用自身私鑰skB、數據發送者身份信息IDA以及指定郵件存儲服務器身份信息IDS,生成相對應的搜索陷門Tw′,然后數據接收者將Tw′發送給指定郵件服務器進行搜索請求。

5)驗證算法dTest(Params,skS,Cw,Tw′):指定郵件服務器利用自身私鑰skS,與接收的Cw和Tw′進行驗證,如果驗證通過,則輸出“True”并返回給數據接收者Cw所對應的加密郵件;否則,輸出“False”。

2.2 安全模型

dIBAEKS方案的安全性由關鍵字密文不可區分性、陷門不可區分性以及抗離線關鍵字猜測攻擊構成。

2.2.1 關鍵字密文不可區分性

以敵手A1和挑戰者F的交互游戲1來定義dIBAEKS方案的關鍵字密文不可區分性。假設敵手A1是外部攻擊者。

1)系統初始化。挑戰者F執行Setup算法產生系統參數并發送給敵手A1。

2)詢問1。外部攻擊者A1向挑戰者F進行以下詢問:

(1)密鑰詢問。當敵手A1向挑戰者F進行密鑰詢問時,挑戰者F調用KeyGen算法并返回數據接收者私鑰skB和指定郵件服務器私鑰skS給敵手A1。

(2)陷門詢問。敵手A1將數據發送者身份信息IDA、數據接收者身份信息IDB和關鍵字w發送給挑戰者F,挑戰者F調用dTrapdoor算法返回給敵手A1搜索陷門Tw。

4)詢問2。敵手A1向挑戰者F進行密鑰詢問,除不能對指定郵件服務器身份信息IDS進行公鑰詢問和測試詢問以外,其他與詢問階段1一致。

5)猜測。敵手A1輸出猜測值b′∈{0,1},如果b′=b,則挑戰成功,敵手A1贏得游戲1的勝利。

定義游戲 1中敵手A1贏得游戲的優勢AdvA1(λ)=

2.2.2 陷門不可區分性

以敵手A2和挑戰者F的交互游戲2來定義dIBAEKS方案的陷門不可區分性。假設敵手A2是外部攻擊者。

1)系統初始化。挑戰者F執行Setup算法產生系統參數并發送給敵手A2。

2)詢問1。外部攻擊者A2向挑戰者F進行以下詢問:

(1)密鑰詢問。當敵手A2向挑戰者F進行密鑰詢問時,挑戰者F調用KeyGen算法并返回數據接收者的私鑰skB和指定郵件存儲服務器私鑰skS給敵手A2。

(2)陷門詢問。敵手A2將數據發送者身份信息IDA、數據接收者身份信息IDB和關鍵字w發送給挑戰者F,并對其進行陷門詢問。挑戰者F調用dTrapdoor算法返回給敵手A2搜索陷門Tw。

4)詢問2。敵手A2向挑戰者F進行密鑰詢問,除不能對指定郵件服務器身份信息IDS、接收者的身份信息IDB進行公鑰詢問和測試詢問以外,其他與詢問階段1一致。

5)猜測。敵手A2輸出猜測值b′∈{0,1},如果b′=b,則挑戰成功,敵手A2贏得游戲2的勝利。

定義游戲2中敵手A2,贏得游戲的優勢AdvA2(λ)=

2.2.3 離線猜測關鍵字攻擊

由于本文提出的dIBAEKS方案在滿足適應性選擇消息下的陷門不可區分性時,可抵御離線關鍵字猜測攻擊[15],因此dIBAEKS方案能夠抵御離線關鍵字猜測攻擊。

3 具體方案

dIBAEKS方案具體算法如下:

2)KeyGen算法。以主密鑰s和指定郵件服務器S的身份信息IDs∈{0,1}*為輸入,PKG生成指定郵件服務器S的私鑰skS=sH1(IDS),其中H1(IDS)為指定郵件服務器S的公鑰。類似地,PKG根據數據發送者A身份信息IDA∈{0,1}*和數據接收者B身份信息IDB∈{0,1}*,生成數據發送者A的私鑰skA=sH1(IDA)和數據接收者B的私鑰skB=sH1(IDB),其中,H1(IDA)和H1(IDB)分別為數據發送者A和數據接收者B的公鑰。

5)dTest算法。指定郵件服務器S利用自身私鑰skS,與接收的C1、C2、T1、T2、T3進行驗證,判斷C2·T3是否與e(C1+T1+T2,skS)相等。若兩者相等則輸出“True”,并將Cw所對應的加密郵件發送給數據接收者B,否則輸出“False”。

4 正確性、安全性證明與效率分析

4.1 正確性證明

本文方案的正確性證明如下:

C2T3=e(rH1(IDS),q1·Ppub)e((t+q2)Ppub,H1(IDS))=

e(rH1(IDS),q1·sp)e((t+q2)sp,H1(IDS))=

e(rpq1,sH1(IDS))e((t+q2)p,sH1(IDS))=

e(rpq1+(t+q2)p,sH1(IDS))=

e(rpq1+tp+q2p,sH1(IDS))=

e(C1+T1+T2,skS)

(2)

由于C2T3=e(C1+T1+T2,skS)等式成立,符合關鍵字w′等于w以及對數據接收者身份的驗證,因此證明了本文提出方案的正確性。

4.2 安全性證明

本節證明dIBAEKS方案能滿足在隨機預言模型適應性選擇消息攻擊下的關鍵字密文不可區分性和陷門不可區分性,進而證明該方案可抵御離線關鍵字猜測攻擊[11,16]。

4.2.1 關鍵字密文不可區分性的具體證明

定理1在計算雙線性Diffie-Hellman是困難問題的情況下,對于游戲1的攻擊者,dIBAEKS方案在隨機預言模型下滿足適應性選擇關鍵字密文攻擊時的不可區分性安全。

1)系統初始化。挑戰者F通過運行Setup算法產生系統參數Params={G1,G2,e,q,p,Ppub,H1,H2}并發送給敵手A1,設Ppub=ap。

2)詢問1。敵手A1向挑戰者F進行以下詢問:

5)猜測。敵手A1輸出猜測值μ′∈{0,1},如果μ′=μ,則挑戰成功,敵手A1贏得游戲1 的勝利。

4.2.2 陷門不可區分性的具體證明

定理2在計算雙線性Diffie-Hellman是困難問題的情況下,對于游戲2的攻擊者,dIBAEKS方案在隨機預言模型下滿足適應性選擇消息攻擊時的陷門不可區分性。

1)系統初始化。挑戰者F通過運行Setup算法產生系統參數Params={G1,G2,e,q,p,Ppub,H1,H2}并發送給敵手A2,設Ppub=ap。

2)詢問1。敵手A2向挑戰者F進行以下詢問:

(2)H2詢問。具體過程與定理1一致。

(4)陷門詢問。具體過程與定理1一致。

5)猜測。敵手A2輸出猜測值μ′∈{0,1},如果μ′=μ,則挑戰成功,敵手A2贏得游戲2 的勝利。

4.3 效率分析

本節通過理論對比和數值實驗對dIBAEKS方案進行效率分析。

4.3.1 理論對比

將采用dIBAEKS方案與dIBEKS方案的關鍵字加密算法、陷門生成算法以及驗證算法的計算效率進行對比,并以點乘運算(PM)、雙線性運算(PB)和哈希運算(PH)的數量作為評估指標,結果如表1所示。可以看出:在關鍵字加密算法中,dIBAEKS方案比dIBEKS方案少1個點乘運算和2個哈希運算;在陷門生成算法中,dIBAEKS方案比dIBEKS方案多1個雙線性運算和1個哈希運算;在驗證算法中,dIBAEKS方案比dIBEKS方案少3個雙線性運算和2個哈希運算。由上述可知,在關鍵字加密算法和驗證算法中,dIBAEKS方案的計算效率均優于dIBEKS方案,因此從總體來看,dIBAEKS方案的計算效率更高。

表1 不同算法下2種方案的計算效率對比Table 1 Comparison of calculation efficiency of two schemes under different algorithms

4.3.2 數值實驗分析

本文采用數值實驗對dIBAEKS方案與dIBEKS方案在關鍵字加密和驗證階段的計算效率進行對比分析。實驗環境如下:ASUS A455L型計算機,Inter?CoreTMi5-4210U處理器,4 GB內存,Win10操作系統,Linux虛擬機。使用C語言基于配對的密碼學(Pairing-Based Cryptography,PBC)庫[20],群G1、G2的長度為1 024 bit,利用A型橢圓曲線y2=x3+xmodq進行計算,且用戶身份和關鍵字隨機產生,實驗參數設置如表2所示。

表2 數值實驗參數設置Table 2 Parameter setting of numerical experiment

關鍵字數量決定dIBAEKS方案的執行時間。在數值實驗中,關鍵字數量分別取100、200、300、400、500、600、700、800、900和1 000,取50次運算結果的平均值作為最終實驗結果。圖2和圖3分別為2種方案在關鍵字加密和驗證階段的執行時間隨關鍵字數量的變化情況。由圖2和圖3可以看出,隨著當關鍵字數量的增加,dIBAEKS方案與dIBEKS方案的執行時間均延長;在關鍵字加密階段,dIBAEKS方案的執行時間增幅略低于dIBEKS方案,其計算效率略高;在驗證階段,dIBAEKS方案和dIBEKS方案執行時間的增幅分別為0.9%和1.3%,dIBAEKS方案的計算效率明顯高于dIBEKS方案。

圖2 2種方案在關鍵字加密階段執行時間隨關鍵字數量的變化Fig.2 The change of execution time with the number of keywords in the keyword encryption phase of two schemes

圖3 2種方案在驗證階段執行時間隨關鍵字數量的變化Fig.3 The change of execution time with the number of keywords in the verification phase of two schemes

5 結束語

本文提出一種指定服務器的身份認證郵件關鍵字加密方案,通過在指定服務器上進行陷門搜索,并由指定數據發送者發出關鍵字密文,可避免離線關鍵字猜測攻擊。理論分析和數值實驗結果表明,該方案具有較高的計算效率和安全性。下一步將在本文工作的基礎上,增加數據接收者對返回加密電子郵件的驗證,以更準確地分辨服務器返回結果的真實性。