可撤銷(xiāo)的公鑰加密方案的形式化分析

于瑞琴

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

可撤銷(xiāo)的公鑰加密方案的形式化分析

于瑞琴

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

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

帶關(guān)鍵字公鑰搜索加密；可撤銷(xiāo)；雙線性對(duì)；無(wú)需安全信道

0 引言

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

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

1 背景知識(shí)

1.1 雙線性對(duì)

定義1 雙線性對(duì)（Bilinear pairings）［4］.

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

1.2 可忽略函數(shù)

1.3 復(fù)雜性假設(shè)

定義3 BDH假設(shè)：

2 可撤銷(xiāo)帶關(guān)鍵字搜索公鑰加密方案的形式化定義及安全模型

定義4 （R－SCF－PEKS）：可高效撤銷(xiāo)的帶關(guān)鍵字搜索的公鑰加密方案包含下面幾個(gè)算法，假設(shè)關(guān)鍵字域?yàn)镵Sw，時(shí)間段域?yàn)棣?

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

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

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

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

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

Trap door（d w，ut）：輸入關(guān)鍵字的初始陷門(mén)d w，更新陷門(mén)ut，輸出在時(shí)間t的實(shí)時(shí)陷門(mén)T w，t.

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

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

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

接下來(lái)將給出基于游戲的安全性定義，稱(chēng)為可撤銷(xiāo)的無(wú)需安全信道的抗選擇關(guān)鍵字攻擊不可區(qū)分性（IND－R－SCF－CKA）.

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

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

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

初始陷門(mén)查詢〈w〉：A適應(yīng)地詢問(wèn)B他所選擇的關(guān)鍵字w，w∈KSw，所對(duì)應(yīng)的初始陷門(mén)d w，B返回給A初始陷門(mén)d w＝KTrapdoor（GP，sk R，w）.

更新陷門(mén)查詢〈t〉：A適應(yīng)地詢問(wèn)B他所選擇的時(shí)間段t所對(duì)應(yīng)的更新陷門(mén)，B返回給A更新陷門(mén)u t＝UTrapdoor（GP，sk R，t，st，RL）.

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

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

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

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

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

更新陷門(mén)查詢〈t〉和撤銷(xiāo)查詢〈w，t〉允許對(duì)大于等于先前的時(shí)間查詢，即攻擊者只允許對(duì)非遞減時(shí)間進(jìn)行查詢.同時(shí)，如果對(duì)時(shí)間t查詢更新陷門(mén)查詢〈t〉，則不允許對(duì)時(shí)間t查詢撤銷(xiāo)查詢〈w，t〉.

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

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

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

初始陷門(mén)查詢〈w〉：因?yàn)锳知道接收者的私鑰，他能夠自己計(jì)算他所選擇的關(guān)鍵字w，w∈KSw，所對(duì)應(yīng)的初始陷門(mén)d w.

更新陷門(mén)查詢〈t〉：因?yàn)锳知道接收者的私鑰，他能夠自己計(jì)算他所選擇的時(shí)間t，t∈τ，所對(duì)應(yīng)的更新陷門(mén)ut.

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

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

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

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

3 結(jié)論

本文給出了一個(gè)可高效撤銷(xiāo)的無(wú)需安全信道的帶關(guān)鍵字搜索公鑰加密方案的形式化定義及安全模型，基于BDH假設(shè)，可以證明可高效撤銷(xiāo)的無(wú)需安全信道的抗選擇關(guān)鍵字攻擊不可區(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)江高等專(zhuān)科學(xué)校講師，主要從事網(wǎng)絡(luò)與信息安全，計(jì)算機(jī)應(yīng)用研究.