楊 勇，徐秋亮

(山東大學計算機科學與技術學院 濟南 250101)

標準模型下可證安全的一種新的CL-PKE加密方案

楊 勇，徐秋亮

(山東大學計算機科學與技術學院 濟南 250101)

該文在標準模型下構建了一個實用的無證書公鑰加密體制(CL-PKE)，相比于其他的CL-PKE加密體制，該體制在加密時沒有橢圓曲線上的對運算，而且所基于的難解性問題假設是自然的雙線性Diffie-Hellman(BDHP)問題。為提高安全性，該文的安全模型選用了標準模型下的選擇性身份(Selective-ID)模型，在提高效率的同時也增強了安全性。

算法; 雙線性Diffie-Hellman問題; 無證書公鑰加密; 公鑰密碼學; 標準模型

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

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

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

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

1 基礎知識

1.1 對運算

本文中，G1表示一個加群，G2表示一個有著同樣階的乘群，p表示G1的生成元，對運算表示為。對運算有以下一些性質。

(1)雙線型性：

(3)可計算性：對運算是可計算的。

1.2 困難性問題假設

本文使用橢圓曲線上的點構成的對運算的困難性問題假設BDHP(binlineary diffie-hellman problem)，定義如下。

式中 A是任意多項式時間的概率算法。

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

2 算法組成

CL-PKE加密體制有密鑰生成中心KGC、系統(tǒng)內用戶以及使用系統(tǒng)的外部參與者共3類參與者。最初，文獻[1]定義的CP-PKE加密體制由7個算法組成[1]，后來被簡化成為5個算法[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í)行，目的是為每一個系統(tǒng)內的用戶生成一個系統(tǒng)范圍內的部分私鑰。算法輸入Params和Master-key以及系統(tǒng)內任意用戶的身份ID；輸出相應用戶的部分私鑰DA。通常情況下，該用戶的部分私鑰DA通過安全的秘密信道交給用戶。

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

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

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

3 安全模型

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

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

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

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

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

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

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

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

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

Type1型攻擊者在Phase 1和Phase 2階段進行詢問時，有以下一些限制：

(1)不能詢問目標ID?的用戶私鑰Usk；

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

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

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

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

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

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

4.1 新的CL-PKE加密體制

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

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

在加密算法中，因為e(g,g)、e(g,h)兩個對運算可以提前預計算，所以只需要計算一次就可以被所有用戶共享，因而在加密時實際上不需要對運算。

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

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

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

5 結 束 語

本文選用自然的困難性假設BDHP構建了加密體制，同時為了獲得更好的安全性選用了安全性較高的標準模型，所以本文的基礎更加自然，安全性更可靠。如何在保證安全性的前提下提高效率是下一步的工作目標。

[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

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

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