于瑞琴

（鎮(zhèn)江高等專科學校電子信息系，江蘇 鎮(zhèn)江 212003）

可撤銷的公鑰加密方案的形式化分析

于瑞琴

（鎮(zhèn)江高等?？茖W校電子信息系，江蘇 鎮(zhèn)江 212003）

通常的密碼系統(tǒng)，IBE或者PKI都必須提供從系統(tǒng)中撤銷用戶私鑰的途徑，同樣PEKS也應該提供撤銷陷門的方式.本文研究了可高效撤銷的無需安全信道的帶關鍵字搜索公鑰加密方案的形式化定義及安全模型.基于BDH問題，可證明方案的安全性.

帶關鍵字公鑰搜索加密；可撤銷；雙線性對；無需安全信道

0 引言

為了實現(xiàn)加密電子郵件智能路由，即第三方不需要解密密文就可以檢測或者驗證密文中是否含有某些關鍵字.Boneh等人［1］在2004年提出了帶關鍵字搜索公鑰加密方案，該方案的缺點是在接收者和郵件服務者之間需要一個安全信道來傳送陷門，而這個開銷往往是很昂貴的.為了解決這一缺點，Baek等人［2］提出了無需安全信道的帶關鍵字搜索公鑰加密方案.2007年，Gu等人［3］提出了一個更有效的基于雙線性對的帶關鍵字搜索公鑰加密構造，然后他們進一步構造了隨機預言模型下的無需安全信道的帶關鍵字搜索公鑰加密方案.為了避免使用隨機預言機，最近Fang等人［4］構造了標準模型下的無需安全信道的帶關鍵字搜索公鑰加密方案.文獻［5-8］研究了改進的帶關鍵字搜索公鑰加密方案，其中文獻［5］提出了從任意的匿名IBE方案構造帶關鍵字搜索公鑰加密方案的一般化方法，反之亦然.

在IBE或者PKI系統(tǒng)中，如果用戶的私鑰泄露了，就必須提供從系統(tǒng)中撤銷用戶的途徑.同樣在帶關鍵字搜索公鑰加密中，接收者在發(fā)送出某關鍵字對應的陷門給服務者后，因為某種原因不想讓服務者繼續(xù)搜索相應關鍵字了，即想撤銷這一關鍵字陷門是很自然的.本文研究了可高效撤銷的無需安全信道的帶關鍵字搜索公鑰加密方案的形式化定義及安全模型.基于BDH問題，可證明方案的安全性.

1 背景知識

1.1 雙線性對

定義1 雙線性對（Bilinear pairings）［4］.

設G1、G2都是階為素數(shù)p的乘法交換群，g是G1的產(chǎn)生元，如果以下三個條件成立，則e：G1×G1→G2是一個可計算的雙線性對映射：（1）雙映射性：對所有a，b∈Z，有e（g a，gb）＝e（g，g）ab；（2）非退化性：e（g，g）≠1；（3）可計算性：對于P，Q∈G1，可計算e（P，Q）.

1.2 可忽略函數(shù)

1.3 復雜性假設

定義3 BDH假設：

2 可撤銷帶關鍵字搜索公鑰加密方案的形式化定義及安全模型

定義4 （R－SCF－PEKS）：可高效撤銷的帶關鍵字搜索的公鑰加密方案包含下面幾個算法，假設關鍵字域為KSw，時間段域為τ.

GloSetup（λ，n）：輸入安全參數(shù)λ，實際關鍵字陷門數(shù)n∈N，輸出公共參數(shù)GP.

Key Gensever（GP）：以公共參數(shù)GP為輸入，輸出服務者S的公鑰對（pks，sks）.

Key Genreciver（GP）：以公共參數(shù)GP為輸入，輸出接收者R的公私鑰對（pks，sk R），初始狀態(tài)st，空的撤銷列表RL.

KTrap door（GP，sk R，w）：由接收者運行，輸入公共參數(shù)GP，接收者的私鑰sk R，關鍵字w，狀態(tài)st.產(chǎn)生初始陷門d w和更新的狀態(tài)st.

UTrapdoor（GP，sk R，t，st，RL）：由接收者運行，輸入公共參數(shù)GP，接收者的私鑰sk R，更新陷門時間t∈τ，撤銷列表RL，狀態(tài)st.產(chǎn)生更新陷門ut.

Trap door（d w，ut）：輸入關鍵字的初始陷門d w，更新陷門ut，輸出在時間t的實時陷門T w，t.

PEKS（GP，pk R，w，t）：輸入公共參數(shù)GP，接收者的公鑰pk R，服務者的公鑰pk S，關鍵字w∈KSw，時間t∈τ.返回一個用關鍵字w和時間t加密的PEKS密文C.

Test（GP，sk S，C，T w，t）：輸入公共參數(shù)GP，服務者的私鑰sk S，在時間t的實時陷門T w，t，PEKS密文C＝PEKS（GP，pk R，pk S，w′，t）.如果w＝w′，輸出“正確”，否則輸出“錯誤”.

Revocation（GP，w，t，RL，st）：由接收者運行，輸入公共參數(shù)GP，將要撤銷的關鍵字w，撤銷時間t∈τ，撤銷列表RL，狀態(tài)st，輸出更新的撤銷列表RL.

接下來將給出基于游戲的安全性定義，稱為可撤銷的無需安全信道的抗選擇關鍵字攻擊不可區(qū)分性（IND－R－SCF－CKA）.

定義5 （IND－R－SCF－CKA游戲）：λ是安全參數(shù)，A是攻擊者.考慮下面兩個游戲：Gameserver：假設A是服務者.

1.系統(tǒng)建立：公共參數(shù)產(chǎn)生算法GloSetup（λ）和兩個密鑰產(chǎn)生算法Key Genreceiver（GP），Key Gensever（GP），被執(zhí)行，產(chǎn)生公共參數(shù)GP，初始狀態(tài)st，空的撤銷列表RL，接收者和服務者的公私鑰對（pk R，sk R），（pks，sks），接著模擬者B把（pk S，sk S）和pk R發(fā)送給攻擊者A.

2.查詢階段1：攻擊者A做了一系列的查詢：

初始陷門查詢〈w〉：A適應地詢問B他所選擇的關鍵字w，w∈KSw，所對應的初始陷門d w，B返回給A初始陷門d w＝KTrapdoor（GP，sk R，w）.

更新陷門查詢〈t〉：A適應地詢問B他所選擇的時間段t所對應的更新陷門，B返回給A更新陷門u t＝UTrapdoor（GP，sk R，t，st，RL）.

撤銷查詢〈w，t〉：A對他所選的關鍵字w和時間t做撤銷查詢，執(zhí)行Revocation（GP，w，t，RL，st）更新RL.

3.挑戰(zhàn)：一旦A決定查詢1階段結束，他輸出挑戰(zhàn)關鍵字對（w0，w1）和挑戰(zhàn)時間t＊.接收到挑戰(zhàn)關鍵字對后，B隨機地選擇β∈｛0，1｝，并且產(chǎn)生挑戰(zhàn)密文C＊＝PEKS（GP，pk R，pk S，wβ，t＊），發(fā)送給A.

4.查詢階段2：A做和階段1相同的查詢.

5.猜測：攻擊者輸出他的猜測β′，如果β＝β′，則攻擊者獲得勝利.

注意游戲必須遵循下面限制：

更新陷門查詢〈t〉和撤銷查詢〈w，t〉允許對大于等于先前的時間查詢，即攻擊者只允許對非遞減時間進行查詢.同時，如果對時間t查詢更新陷門查詢〈t〉，則不允許對時間t查詢撤銷查詢〈w，t〉.

如果對挑戰(zhàn)關鍵字w i，i＝0，1，做初始陷門查詢，則撤銷查詢〈w i，t〉的時間t必須滿足t≤t＊.

1）系統(tǒng)建立：公共參數(shù)產(chǎn)生算法GloSetup（λ）和兩個密鑰產(chǎn)生算法Key Genreceiver（GP），Key Gensever（GP）被執(zhí)行，產(chǎn)生公共參數(shù)GP，初始狀態(tài)st，空的撤銷列表RL，接收者和服務者的公私鑰對（pk R，sk R），（pk S，sk S），接著模擬者B把（pk R，sk R）和pk S發(fā)送給攻擊者A.

2）查詢階段1：攻擊者A做一系列的查詢：

初始陷門查詢〈w〉：因為A知道接收者的私鑰，他能夠自己計算他所選擇的關鍵字w，w∈KSw，所對應的初始陷門d w.

更新陷門查詢〈t〉：因為A知道接收者的私鑰，他能夠自己計算他所選擇的時間t，t∈τ，所對應的更新陷門ut.

撤銷查詢〈w，t〉：A對他所選的關鍵字w和時間t做撤銷查詢，執(zhí)行Revocation（GP，w，t，RL，st）更新RL.

3）挑戰(zhàn)：一旦A決定查詢1階段結束，他輸出挑戰(zhàn)關鍵字對（w0.w1）和挑戰(zhàn)時間t＊.接收到挑戰(zhàn)關鍵字對，B隨機地選擇β，其中β∈｛0，1｝，并且產(chǎn)生挑戰(zhàn)密文C＊＝PEKS（GP，pk R，pk S，wβ，t＊），發(fā)送給A.

4）查詢階段2：A做和階段1相同的查詢.

5）猜測：攻擊者輸出他的猜測β′，如果β＝β′，則攻擊者獲得勝利.

3 結論

本文給出了一個可高效撤銷的無需安全信道的帶關鍵字搜索公鑰加密方案的形式化定義及安全模型，基于BDH假設，可以證明可高效撤銷的無需安全信道的抗選擇關鍵字攻擊不可區(qū)分的安全性（IND-R-SCFCKA）.

［1］Boneh D，Crescenzo G Di，Ostrovsky R，et al.Public key encryption with keyword search［A］.In Proc.of EUROCRYPT 2004，LNCS 3027［G］.Heidelberg：Springer，2004：506-522

［2］Baek J，Safavi-Naini R，Susilo W.Public key encryption with keyword search revisited［A］.In Proc.of Applied Cryptography and Information Security 06（ACIS 2006），LNCS 5072［G］.Berlin：Springer-Verlag，2008：1 249-1 259

［3］Gu C，Zhu Y，Pan H.Efficient public key encryption with keyword search schemes from pairings［A］.In Proc.of Information Security and Cryptology：third SKLOIS conference，inscrypt 2007，LNCS 4990［G］.Heidelberg：Springer-Verlag，2007：372-383

［4］Fang L，Susilo W，Ge C，et al.A secure channel free public key encryption with keyword search scheme without random oracle［A］.In Proc.of cryptology and network security，8th International Conference，CANS 2009，LNCS 5888［G］.Heidelberg：Springer，2009：248-258

［5］Abdalla M，Bellare M，Catalano D，et al.Searchable encryption revisited：consistency properties，relation to anonymous IBE and extensions［A］.In Proc of CRYPTO 2005，LNCS 3621［G］.Berlin：Springer-Verlag，2005：205-222

［6］Rhee H S，Park J H，Susilo W，et al.Improved searchable public key encryption with designated tester［A］.In Proc.of the 4th international symposium on information，computer，and communications security（ASIACCS’09）［G］.New York：ACM，2009：376-379

［7］Rhee H S，Susilo W，Kim H-J.Secure searchable public key encryption scheme against keyword guessing attacks［J］.IEICE E-lectron Express，2009，6（5）：237-243

［8］Zhang R，Imai H.Generic combination of public key encryption with keyword search and public key encryption［A］.Proc.of Cryptology and Network Security，6th International Conference，CANS 2007，LNCS 4856［G］.Heidelberg：Springer-Verlag，2007：159-174

Revocable Public-Key Cryptosystems Formal Analysis

Yu Ruiqin
（Election Information Department，Zhenjiang College，Zhenjiang 212003，China）

Any setting，Public-key Infrastructure or Identity-Based.Must provide a means to revoke users from the system.Efficient revocation is a well-studied problem in the traditional Public-Key Infrastructure or Identity-Based Encryption.We propose revocable public key encryption with keyword search scheme of formalized definition and the security model in the paper.Based on bilinear dilinear diffie-hellman，the security of the scheme can be proved.

public key encryption with keyword search；revocation；bilinear pairings；secure channel free

王映苗】

1672-2027（2011）03-0075-03

TP309

A

2011-03-23

于瑞琴（1976-），女，山西孝義人，碩士，鎮(zhèn)江高等?？茖W校講師，主要從事網(wǎng)絡與信息安全，計算機應用研究.