標(biāo)準(zhǔn)模型下可證安全的一種新的CL-PKE加密方案

楊 勇，徐秋亮

(山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 濟(jì)南 250101)

標(biāo)準(zhǔn)模型下可證安全的一種新的CL-PKE加密方案

楊 勇，徐秋亮

(山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 濟(jì)南 250101)

該文在標(biāo)準(zhǔn)模型下構(gòu)建了一個(gè)實(shí)用的無(wú)證書公鑰加密體制(CL-PKE)，相比于其他的CL-PKE加密體制，該體制在加密時(shí)沒(méi)有橢圓曲線上的對(duì)運(yùn)算，而且所基于的難解性問(wèn)題假設(shè)是自然的雙線性Diffie-Hellman(BDHP)問(wèn)題。為提高安全性，該文的安全模型選用了標(biāo)準(zhǔn)模型下的選擇性身份(Selective-ID)模型，在提高效率的同時(shí)也增強(qiáng)了安全性。

算法; 雙線性Diffie-Hellman問(wèn)題; 無(wú)證書公鑰加密; 公鑰密碼學(xué); 標(biāo)準(zhǔn)模型

文獻(xiàn)[1]提出了CL-PKE(certificateless encryption scheme)無(wú)證書加密體制，該體制的目的在于增強(qiáng)基于身份的加密體制，使基于身份的加密體制可以阻止密鑰生成中心KGC的偽造攻擊。CL-PKE加密體制就集成了傳統(tǒng)PKE加密體制和基于身份加密體制的優(yōu)勢(shì)，具有阻止KGC偽造攻擊和無(wú)公鑰證書的特點(diǎn)。

最初的CL-PKE加密體制都是基于Random Oracle模型的[1-2]，之后有學(xué)者提出了基于標(biāo)準(zhǔn)模型的加密算法，但基于標(biāo)準(zhǔn)模型的加密算法大都有著復(fù)雜的運(yùn)算和經(jīng)過(guò)變形的困難性問(wèn)題假設(shè)[1-3]。在具體算法發(fā)展到一定程度后，有的學(xué)者又提出了基于各種模型的通用算法[2,4-5]，但有些通用算法在某些模型下被證明是錯(cuò)誤的[6]，因此，需要進(jìn)一步研究構(gòu)建基于一定模型的好的通用算法。

相對(duì)于本文來(lái)講，在[JCH07]方案中，雖然加密時(shí)沒(méi)有對(duì)運(yùn)算，但在檢驗(yàn)用戶公鑰時(shí)有兩個(gè)對(duì)運(yùn)算[7]，[BSN05]的方案雖然沒(méi)有橢圓曲線上的對(duì)運(yùn)算，效率較高，但要求在產(chǎn)生用戶公鑰前必須先產(chǎn)生一個(gè)部分用戶公鑰[6]，使得這個(gè)方案更像自生成證書方案，而不是基于身份的方案。另外有一些方案[AP03]和[BSN05]提出的CL-PKE用的是安全性較低的Random Oracle模型[1,6]。

最近有學(xué)者提出了一種更嚴(yán)格的模型，該模型下的KGC能夠在創(chuàng)建體制時(shí)在公共參數(shù)中留下只有其知道的后門[8]。而且已經(jīng)有很大一部分CL-PKE加密體制被證明在該模型下是不安全的[1]。所以構(gòu)造一個(gè)在這種模型下安全的加密體制是當(dāng)前研究的一個(gè)熱點(diǎn)[9]。本文在標(biāo)準(zhǔn)模型下構(gòu)建的體制在加密時(shí)沒(méi)有對(duì)運(yùn)算，而且保持了基于身份的特點(diǎn)[10]。

1 基礎(chǔ)知識(shí)

1.1 對(duì)運(yùn)算

本文中，G1表示一個(gè)加群，G2表示一個(gè)有著同樣階的乘群，p表示G1的生成元，對(duì)運(yùn)算表示為。對(duì)運(yùn)算有以下一些性質(zhì)。

(1)雙線型性：

(3)可計(jì)算性：對(duì)運(yùn)算是可計(jì)算的。

1.2 困難性問(wèn)題假設(shè)

本文使用橢圓曲線上的點(diǎn)構(gòu)成的對(duì)運(yùn)算的困難性問(wèn)題假設(shè)BDHP(binlineary diffie-hellman problem)，定義如下。

式中 A是任意多項(xiàng)式時(shí)間的概率算法。

定義 1 如果對(duì)于任何多項(xiàng)式時(shí)間的概率算法A，都至多有 的優(yōu)勢(shì)概率在群G1中解決BDHP困難性問(wèn)題假設(shè)，則BDHP困難性問(wèn)題假設(shè)在群G1中是安全的，表達(dá)為：

2 算法組成

CL-PKE加密體制有密鑰生成中心KGC、系統(tǒng)內(nèi)用戶以及使用系統(tǒng)的外部參與者共3類參與者。最初，文獻(xiàn)[1]定義的CP-PKE加密體制由7個(gè)算法組成[1]，后來(lái)被簡(jiǎn)化成為5個(gè)算法[7]，分別描述如下。

(1)Setup(K)= ( Params,Master-Key)：該算法由KGC執(zhí)行，目的是由KGC生成密碼體制的系統(tǒng)參數(shù)和主密鑰。算法輸入安全參數(shù) K ∈ 1n；輸出CL-PKE加密體制的系統(tǒng)參數(shù)Params和Master-key。

(2)Partial-Private-Key-Extract (Params,Private-key,ID)=DA：該算法由KGC執(zhí)行，目的是為每一個(gè)系統(tǒng)內(nèi)的用戶生成一個(gè)系統(tǒng)范圍內(nèi)的部分私鑰。算法輸入Params和Master-key以及系統(tǒng)內(nèi)任意用戶的身份ID；輸出相應(yīng)用戶的部分私鑰DA。通常情況下，該用戶的部分私鑰DA通過(guò)安全的秘密信道交給用戶。

(3)Set-User-Key (DA,S,Params)=(Upk,Usk)：該算法由系統(tǒng)內(nèi)用戶執(zhí)行，目的是系統(tǒng)內(nèi)用戶生成一個(gè)只有自己知道的用戶私鑰。算法輸入KGC交給用戶的部分密鑰DA和用戶均勻選擇的一個(gè)隨機(jī)數(shù)S ∈ Z?p；輸出用戶的公鑰Upk和私鑰Usk，其中Upk在系統(tǒng)內(nèi)公開(kāi)，Usk由用戶秘密保存。

(4)Encrypt(m,Params,ID,s)=C：該算法由系統(tǒng)外任意參與者執(zhí)行，目的是用相應(yīng)的系統(tǒng)內(nèi)用戶公鑰加密要保密的明文信息m。算法輸入要加密的信息m、公共參數(shù)Params、用戶ID、均勻選擇的隨機(jī)數(shù) S ∈和用戶公鑰Upk；輸出密文C。

(5)Decrypt(C,Usk,Params,ID)=m：該算法由相應(yīng)的系統(tǒng)內(nèi)用戶執(zhí)行，目的是用相應(yīng)的私鑰解密密文C。算法輸入密文C、用戶私鑰Usk、公共參數(shù)Params和用戶ID；輸出相應(yīng)的明文m。

3 安全模型

安全模型可以用一種由兩方參與的游戲模擬，一方為攻擊者，用A表示，另一方為挑戰(zhàn)者，用C表示。在游戲中，攻擊者可以向挑戰(zhàn)者發(fā)出各種不同的Oracle詢問(wèn)，挑戰(zhàn)者模擬回答相應(yīng)的詢問(wèn)。如果挑戰(zhàn)者能夠正確回答攻擊者的各種詢問(wèn)，挑戰(zhàn)者就成功模擬了安全模型；而且，如果攻擊者贏得了游戲，攻擊者就攻破了相應(yīng)的加密體制[11]。

以下首先對(duì)選擇性身份模型下CL-PKE的安全模型進(jìn)行定義，如在引言中所述，CL-PKE加密體制可能遭受到如傳統(tǒng)PKE的外部攻擊，以及如IBE的內(nèi)部密鑰生成中心KGC的攻擊，因此下面針對(duì)這兩種攻擊定義了兩種安全模型。

Game 1：外部攻擊者和挑戰(zhàn)者之間的游戲，攻擊者定義為Type1型。

Init：攻擊者給挑戰(zhàn)者一個(gè)要攻擊的目標(biāo)ID?。

Setup：挑戰(zhàn)者根據(jù)自己的參數(shù)模擬公共參數(shù)Params，并把Params交給攻擊者。

Phase 1：攻擊者可以向挑戰(zhàn)者進(jìn)行Extract Partial Private Key(提取用戶的部分密鑰)、Extract Private Key(提取用戶私鑰)、Request Public Key(詢問(wèn)用戶公鑰)、Replace Public Key(置換公鑰)、Decryption Query(解密詢問(wèn))多項(xiàng)式次詢問(wèn)。挑戰(zhàn)者分別進(jìn)行回答，當(dāng)攻擊者同意時(shí)，第一階段結(jié)束。該階段的目的是讓挑戰(zhàn)者用模擬得到的公共參數(shù)回答攻擊者的詢問(wèn)，證明用一定的問(wèn)題假設(shè)模擬的加密體制可以滿足攻擊者相應(yīng)的詢問(wèn)。而詢問(wèn)本身就隱含著相應(yīng)的攻擊，為下一步的安全性歸約做好了準(zhǔn)備。

Challenge：攻擊者提供兩條明文m1、m2，挑戰(zhàn)者均勻選擇其中一條加密為Cb，其中b在(1,2)中均勻選擇，并交給攻擊者，讓其辨別是那條明文的加密密文。該階段的目的是把相應(yīng)的困難性假設(shè)問(wèn)題歸約為辨別密文的困難性。

Phase 2：攻擊者繼續(xù)詢問(wèn)多項(xiàng)式次挑戰(zhàn)者在Phase 1中同樣的Oracle，并由攻擊者決定何時(shí)結(jié)束。該階段的目的和第一階段相似，只是為了使安全模型擁有更高的安全性。

Guess：攻擊者輸出猜測(cè)b′，如果b′=b，那么攻擊成功。這一階段攻擊者如果成功那么就辨別了密文，也就解決了相應(yīng)的難解性問(wèn)題。然而，實(shí)際上難解性問(wèn)題在當(dāng)前理論范圍內(nèi)不可解，所以攻擊者不可能辨別密文，因而攻擊者不可能成功，這就反證了加密體制的安全性。

Type1型攻擊者在Phase 1和Phase 2階段進(jìn)行詢問(wèn)時(shí)，有以下一些限制：

(1)不能詢問(wèn)目標(biāo)ID?的用戶私鑰Usk；

(2)不能詢問(wèn)由目標(biāo)ID?加密、要求辨別的加密密文(ID?, mb)；

(3)提交詢問(wèn)密文前，不能置換目標(biāo)ID?的用戶公鑰；

(4)如果詢問(wèn)的加密密文的相應(yīng)公鑰已經(jīng)被替換過(guò)，必須向挑戰(zhàn)者提供相應(yīng)用戶私鑰中的秘密值。

Game 2：內(nèi)部攻擊者KGC和挑戰(zhàn)者之間的游戲，攻擊者定義為 T ype2型。該安全模型與Game 1相似。

定義 2 如果任何一個(gè)多項(xiàng)式時(shí)間攻擊者都不能在不可忽略的時(shí)間內(nèi)贏得Game 1(或Game 2)，則無(wú)證書加密體制(CL-PKE)是 T ype1(或 T ype2)型安全的，CL-PKE加密體制就是IND-CCA安全的。

4 新的CL-PKE加密體制和證明

4.1 新的CL-PKE加密體制

本文介紹的加密體制由5個(gè)算法組成，分別定義如下。

Setup：KGC輸入?yún)?shù)K，分別輸出mpk和msk，mpk由KGC公開(kāi)，msk由KGC自己秘密保存。其中：

在加密算法中，因?yàn)閑(g,g)、e(g,h)兩個(gè)對(duì)運(yùn)算可以提前預(yù)計(jì)算，所以只需要計(jì)算一次就可以被所有用戶共享，因而在加密時(shí)實(shí)際上不需要對(duì)運(yùn)算。

Decrypt：用戶輸入密文C和自己的私鑰，解密如下：

4.2 新的CL-PKE的形式化證明

如果能夠用BDHP難解問(wèn)題的參數(shù)模擬新的CL-PKE加密體制的系統(tǒng)參數(shù)，并且挑戰(zhàn)者可以回答攻擊者的相應(yīng)詢問(wèn)，把難解性問(wèn)題BDHP歸約為辨別密文的困難性，則挑戰(zhàn)者模擬成功，新的CL-PKE加密體制符合安全模型的安全性要求。對(duì)方案的形式化證明是在攻擊者A和挑戰(zhàn)者C之間進(jìn)行的。

5 結(jié) 束 語(yǔ)

本文選用自然的困難性假設(shè)BDHP構(gòu)建了加密體制，同時(shí)為了獲得更好的安全性選用了安全性較高的標(biāo)準(zhǔn)模型，所以本文的基礎(chǔ)更加自然，安全性更可靠。如何在保證安全性的前提下提高效率是下一步的工作目標(biāo)。

[1]Al-RIYAMI S S, PATERSON K. Certificateless public key cryptography[C]//Advances in Cryptology Asiacrypt 2003.Taibei: Springe Verlagr, 2003: 452-473.

[2]GENTRY C. Practical identity-based encryption without random oracle[C]//Advances in Cryptology Eurocrypt 2006.Saint Petersburg: Springe Verlag, 2006: 445-464.

[3]AU M H, CHEN J, LIU J K, et al. Malicious KGC attack in certificateless cryptography[C]//ACM Symposium on Information, Computer and Communications Security 2006.Taibei: ACM Press, 2007.

[4]HUANG Q, WONG D S. Generic certificateless encryption in the standard model[C]//Advances in Information and Computer Security, IWSEC 2007. Nara: Springe Verlag,2007: 278-291.

[5]DENT A W, LIBERT B, PATERSON K G. Certificateless encryption schemes strongly secure in the standard model[C]//11th International Conference on Public Key Cryptography. Barcelona: Springe Verlag , 2007.

[6]ONG H, CHOI K Y, HWANG J Y, et al. Certificateless public key encryption in the selective-ID security model(Without Random Oracles)[C]//Pairing-Based Cryptography-Pairing 2007. Tokyo: Springe Verlag , 2007:60-82.

[7]BAEK J, SAFAVI, NAINI R, SUSILO W. Certificateless public key encryption without pairing[C]//Information Security. Singapore : Springe Verlag , 2005:. 134-148.

[8]CHENG Zhao-hui, CHEN Li-qun, LING Li, et al. General and efficient certificateless public key encryption constructions[C]//Pairing-Based Cryptography-Pairing 2007. Tokyo: Springe Verlag , 2007: 83-107.

[9]WATERS B. Efficient identity-based encryption without random oracles[C]//Advances in Cryptology EUROCRYPT 2005. Aarhus: Springe Verlag, 2005: 114-127.

[10]DENT A W. A survey of certificateless encryption schemes and security models[J]. International Journal of Information Security, 2008,7(5): 349-377.

[11]CHENG Z, COMLEY R. Efficient certificateless public key encryption[R/OL]. [2009-03-14]. http://eprint.iacr.org/2005/012/

編 輯 黃 莘

New Provable Security CL-PKE Encryption Scheme in the Standard Model

YANG Yong and XU Qiu-liang

(Department of Computer Science and Technology, Shandong University Jinan 250010)

A certificateless public key encryption (CL-PKE)algorithm is presented. The proposed CL-PKE algorithm is based on the nature BDHP difficulty assumption and therefore avoids paring computation on elliptic curves, which is the most expensive operation in the encryption algorithm. In CL-PKE algorithm, the selective-ID model is applied instead of the random oracle model. The security and efficiency of the algorithm can be improved compared with some other CL-PKE schemes.

algorithm; BDHP; CL-PKE; public key cryptography; standard model

TP309.7

A

10.3969/j.issn.1001-0548.2010.06.021

2009- 05- 05;

2010- 09- 14

山東省自然科學(xué)基金(Y2007G37、2007G10001012)；

楊 勇(1980- )，男，博士生，主要從事密碼學(xué)、信息安全方面的研究.