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

楊 勇，徐秋亮

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

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

楊 勇，徐秋亮

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

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

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

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

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

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

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

1 基礎知識

1.1 對運算

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

(1)雙線型性：

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

1.2 困難性問題假設

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

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

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

2 算法組成

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

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

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

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

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

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

3 安全模型

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

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

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

Init：攻擊者給挑戰者一個要攻擊的目標ID?。

Setup：挑戰者根據自己的參數模擬公共參數Params，并把Params交給攻擊者。

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

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

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

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

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

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

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

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

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

Game 2：內部攻擊者KGC和挑戰者之間的游戲，攻擊者定義為 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輸入參數K，分別輸出mpk和msk，mpk由KGC公開，msk由KGC自己秘密保存。其中：

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

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

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

如果能夠用BDHP難解問題的參數模擬新的CL-PKE加密體制的系統參數，并且挑戰者可以回答攻擊者的相應詢問，把難解性問題BDHP歸約為辨別密文的困難性，則挑戰者模擬成功，新的CL-PKE加密體制符合安全模型的安全性要求。對方案的形式化證明是在攻擊者A和挑戰者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- )，男，博士生，主要從事密碼學、信息安全方面的研究.