三接收方公鑰密碼系統(tǒng)

趙琉濤，鐘林，劉吉東，王彩群，吳丹

三接收方公鑰密碼系統(tǒng)

趙琉濤1，鐘林2，劉吉東2，王彩群1，吳丹3

（1. 北京市計算中心，北京 100094； 2. 北京北科融智云計算科技有限公司，北京 100094；3.國家計算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100089）

提出一種三接收方公鑰加密方案，該方案中發(fā)送方對消息進(jìn)行加密，而三接收方均能夠使用各自的私鑰對消息進(jìn)行解密?；陔p線性映射，構(gòu)造出兩個安全性不同的三接收方公鑰加密方案。形式化證明如果間隙雙線性Diffie-Hellman問題和計算性Diffie-Hellman問題是困難的，則所提的兩個方案分別具有選擇明文攻擊安全和適應(yīng)性選擇密文攻擊安全。所提方案僅增加了一項指數(shù)運(yùn)算和一項哈希運(yùn)算，就實現(xiàn)了3個獨(dú)立的接收方，因此該方案效率較高。分析表明，該方案能夠提高TLS協(xié)議的安全性并應(yīng)用于分級監(jiān)管公鑰密碼系統(tǒng)。

三接收方；公鑰加密；雙線性映射；間隙雙線性Diffie-Hellman問題；計算性Diffie-Hellman問題

1 引言

1976年，Diffie-Hellman首次提出公鑰密碼學(xué)，開創(chuàng)了現(xiàn)代密碼學(xué)的新領(lǐng)域。隨后，Rivest、Shamir和Adleman提出第一個實用的RSA公鑰密碼方案。在公鑰加密可證明安全方面，Naor和Dolev等提出可證明安全但低效的公鑰加密方案；隨后，在隨機(jī)預(yù)言機(jī)模型下，Boneh和Franklin提出高效的身份基公鑰加密。

公鑰加密方案不斷發(fā)展，從可證明安全到高效性。但是當(dāng)今社會的發(fā)展產(chǎn)生許多新的應(yīng)用場景，如區(qū)塊鏈、5G、物聯(lián)網(wǎng)。這些新的應(yīng)用場景需要功能更加豐富的公鑰加密方案。上述公鑰加密方案均圍繞安全性和效率的視角開展，缺乏從多接收方的視角發(fā)展，而該方向是至關(guān)重要的。

考慮以下兩個典型的應(yīng)用場景。

①Alice需要將同一段數(shù)據(jù)加密發(fā)送給Bob和Carol，則Alice需要使用Bob與Carol的公鑰對該段數(shù)據(jù)加密，并使用零知識證明協(xié)議證明這兩段密文包含的消息是相等的。因此，Bob和Carol能夠確保收到了與對方相同的消息。但是，如果Alice需要將同一段數(shù)據(jù)發(fā)送給Bob、Carol和Dave，則Alice需要使用兩次零知識證明協(xié)議。該過程將導(dǎo)致用戶需要進(jìn)行計算復(fù)雜度較高的零知識證明和較長的數(shù)據(jù)發(fā)送與存儲，因此效率較低。

②在一個典型的監(jiān)管密碼系統(tǒng)中，發(fā)送方Alice加密消息并發(fā)送給接收方Bob。如果管理員需要查看Bob的密文數(shù)據(jù)，則Alice還需要使用管理員的公鑰將消息加密發(fā)送給管理員并附帶一段零知識證明數(shù)據(jù)，從而導(dǎo)致效率較低。

針對上述兩個典型的應(yīng)用場景，已有研究提出類似的解決方案。Diament等[1]提出一種雙接收方公鑰密碼方案，該方案使用了兩個群上的雙線性映射[2-3]。類似于將Diffie-Hellman 密鑰交換協(xié)議擴(kuò)展為ElGamal加密方案[4-5]，Diament將三方一輪Diffie-Hellman密鑰交換協(xié)議[6]擴(kuò)展為雙接收方公鑰加密方案。因此，對于上述兩個典型應(yīng)用場景，如果Alice將數(shù)據(jù)加密發(fā)送給Bob和Carol，或發(fā)送方Alice將數(shù)據(jù)發(fā)送給接收方Bob和管理員，則不需要使用零知識證明協(xié)議[7-8]。因此，該方案極大地降低了計算復(fù)雜度和數(shù)據(jù)長度，從而使協(xié)議運(yùn)行效率較高。但是，如果Alice需要將數(shù)據(jù)發(fā)送給3個接收方或公鑰加密系統(tǒng)中有兩個管理員，則需要在Diament方案的基礎(chǔ)上再使用一次零知識證明協(xié)議才能夠滿足期望的功能。但是，零知識證明協(xié)議將極大降低Diament方案的效率，使Diament方案實用性較差。如果使用門限密碼系統(tǒng)[9-10]，則系統(tǒng)效率較低，且需要多個接收方合作才能夠?qū)γ芪倪M(jìn)行解密。

針對應(yīng)用場景二，如果使用分級加密方案[11-12]，則能夠在一定程度上滿足場景二的需求。在分級加密方案中，管理員分發(fā)密鑰給下級用戶。發(fā)送方使用下級用戶的公鑰對消息加密，則接收方和管理員均能夠解密。但是，該方案的缺點(diǎn)在于管理員擁有了下級用戶的私鑰，下級用戶數(shù)據(jù)的安全性不僅取決于算法的安全性，還取決于管理員對私鑰的保密性和管理員的誠實性。如果管理員不夠誠實可靠，則下級用戶的消息是不安全的。此外，管理員擁有大量的下級用戶私鑰，且管理員的根密鑰非常重要，容易導(dǎo)致攻擊者對管理員進(jìn)行各種攻擊，如拒絕服務(wù)攻擊[13-14]或?qū)Ω荑€進(jìn)行攻擊。

因此，本文提出一種高效的三接收方公鑰密碼方案。該方案中，存在3個獨(dú)立的接收方。發(fā)送方使用3個獨(dú)立的接收方的公鑰對消息進(jìn)行加密，則3個接收方均能夠使用各自的私鑰對消息解密。該過程不需要零知識證明協(xié)議對消息的一致性進(jìn)行證明，因為該過程中消息加密生成的密文具有多功能性，使三接收方的私鑰均能夠解密密文。本文方案是對Diament方案的進(jìn)一步擴(kuò)展，而幾乎不降低效率。本文提出的方案僅需要在Diament方案的基礎(chǔ)上額外添加一項指數(shù)運(yùn)算和一項哈希運(yùn)算，因此該方案效率較高。

2 研究現(xiàn)狀

Diament[1]等提出一個雙接收方公鑰密碼系統(tǒng)。該系統(tǒng)中的兩個獨(dú)立接收方能夠使用各自的私鑰對發(fā)送方生成的密文進(jìn)行高效解密。如果其中一個接收方為管理員，則該公鑰加密方案具有較好的監(jiān)管應(yīng)用。Diament等使用REACT轉(zhuǎn)換[15]，在缺口雙線性Diffie-Hellman假設(shè)下[16]，將方案從選擇明文攻擊安全增強(qiáng)到適應(yīng)性選擇密文攻擊安全。但基于Groth-Sahai證明系統(tǒng)[17]構(gòu)造高效的雙接收方密碼系統(tǒng)需要約100個群元素。隨后，Chow等[18]對Diament提出的雙接收方公鑰加密方案進(jìn)一步形式化，定義了雙接收方公鑰加密方案的可靠性（soundness）以確保兩個獨(dú)立的接收方能夠解密獲得相同的明文信息。該可靠性使雙接受公鑰加密方案成為一個強(qiáng)大的密碼學(xué)原語，如允許完美不可延展性和明文可識別性。

同時，雙接收方密碼系統(tǒng)能夠解決安全難題（security puzzles），Zhang等[19]構(gòu)造基于身份基加密方案對該安全難題進(jìn)行了類似的解決。Baek[20]和Zhang[21]等研究了安全的結(jié)合公鑰加密方案與關(guān)鍵詞搜索公鑰加密方案。Rogaway[22]研究在保護(hù)密文長度的情況下，安全地結(jié)合選擇明文攻擊安全和選擇密文攻擊安全的公鑰加密。最后，Wu等[23]研究了自組織廣播加密方案，方案中任意發(fā)送方能夠加密消息并發(fā)送給一個自組織群，且群中接收方能夠獨(dú)立解密而不需要可信第三方。但該方案僅考慮了選擇明文攻擊安全。

3 預(yù)備知識

3.1 雙線性映射

本文方案需要使用雙線性映射，以下對雙線性映射進(jìn)行簡要介紹。

3.2 困難問題

本文方案的安全性依賴于以下4個相關(guān)的復(fù)雜性假設(shè)，該假設(shè)使用群上的離散對數(shù)困難問題。

4 方案設(shè)計

4.1 選擇明文安全的三接收方公鑰加密方案

（4）解密：用戶2、用戶3、用戶4使用各自的私鑰對密文進(jìn)行解密。

公式推導(dǎo)如下。

公式推導(dǎo)過程如下。

公式推導(dǎo)過程如下。

4.2 適應(yīng)性選擇密文安全的三接收方公鑰加密方案Enc2

（2）密鑰生成：密鑰生成過程與選擇明文安全的三接收方公鑰加密方案中的密鑰生成過程相同。

（4）解密。用戶2、用戶3、用戶4使用各自的私鑰對密文進(jìn)行解密。

5 安全模型與形式化證明

如果攻擊者從用戶3和用戶4角度對本文提出的兩個方案進(jìn)行攻擊，則文獻(xiàn)[1]已經(jīng)證明公鑰加密方案滿足選擇明文攻擊安全，公鑰加密方案滿足適應(yīng)性選擇密文攻擊安全。但是，本文提出的三接收方公鑰密碼系統(tǒng)中，攻擊者還可能從用戶2角度對方案進(jìn)行攻擊。因此，本節(jié)將證明如下定理。

定理1 從用戶2角度，如果計算性Diffie- Hellman問題是困難的，則在隨機(jī)預(yù)言機(jī)模型下，本文提出的公鑰加密方案滿足選擇明文攻擊安全。

定理2 從用戶2角度，如果計算性Diffie- Hellman問題是困難的，則在隨機(jī)預(yù)言機(jī)模型下，本文提出的公鑰加密方案滿足適應(yīng)性選擇密文攻擊安全。

文獻(xiàn)[15]提出REACT方案，將選擇明文攻擊安全的公鑰加密方案轉(zhuǎn)換為適應(yīng)性選擇密文攻擊安全。本文提出的方案正是基于文獻(xiàn)[15]的REACT轉(zhuǎn)換對方案進(jìn)行安全性提升的，即轉(zhuǎn)換為適應(yīng)性選擇密文攻擊安全。因此，如果本文提出的公鑰加密方案從用戶2角度滿足選擇明文攻擊安全，則根據(jù)文獻(xiàn)[15]，本文提出的公鑰加密方案從用戶2角度滿足選擇密文攻擊安全。因此，本文僅對定理1進(jìn)行安全性證明，而定理2的安全性證明參見文獻(xiàn)[15]。

5.1 安全模型

5.2 形式化證明

（1）不可區(qū)分性仿真：上述說明仿真過程的正確性。仿真過程的隨機(jī)性包括密鑰生成過程中的隨機(jī)數(shù)、對哈希詢問的響應(yīng)值和挑戰(zhàn)值的生成，分別是

（2）仿真成功概率：在仿真過程中，不存在中斷過程，仿真成功概率為1。

6 方案對比

如表1所示，將本文提出的方案與文獻(xiàn)[1]中的方案進(jìn)行對比。表1中，第2至4列展示了方案的私鑰、公鑰和密文的長度；第5至8列分別展示了加密算法復(fù)雜度、各個接收方的解密計算復(fù)雜度、接收方個數(shù)和算法基于的復(fù)雜性假設(shè)。

其中，E是指數(shù)運(yùn)算，P是雙線性映射，H是哈希運(yùn)算。如表1所示，本文在文獻(xiàn)[1]的基礎(chǔ)上添加了1個接收方，而用戶的私鑰和公鑰長度均不變，本文CPA安全方案和CCA2安全方案的密文長度僅增加。在加密計算復(fù)雜度方面，本文CPA安全方案和CCA2安全方案均只增加了一項指數(shù)運(yùn)算和一項哈希運(yùn)算，而沒有增加映射運(yùn)算。此外，指數(shù)運(yùn)算和哈希函數(shù)的運(yùn)算效率較高。在解密計算復(fù)雜度方面，用戶3和用戶4的解密復(fù)雜度與文獻(xiàn)[1]中兩個用戶的解密復(fù)雜度相等，而用戶2的解密復(fù)雜度僅增加了一項指數(shù)運(yùn)算和一項哈希運(yùn)算，該過程效率也較高。文獻(xiàn)[1]的方案基于DBDH復(fù)雜性假設(shè)，而本文額外增加了CDH復(fù)雜性假設(shè)。由于CDH復(fù)雜性假設(shè)是當(dāng)前密碼算法中最經(jīng)典的困難問題，因此該假設(shè)的引入不會導(dǎo)致算法安全性降低。

表1 方案性能對比

此外，將本文方案與文獻(xiàn)[1]中的方案進(jìn)行實驗測試。實驗設(shè)備信息：內(nèi)核x86_64 操作系統(tǒng)Linux 4.17.6-1-ARCH，運(yùn)算芯片Intel i5-7200U 2.50 GHz，內(nèi)存8 GB。實驗選擇SHA256作為哈希函數(shù)的具體實現(xiàn)和使用超奇異橢圓曲線；有限域為512 bit，離散對數(shù)安全范圍為1 024 bit，橢圓曲線群的階為160 bit。如表2所示，橫向表示算法的加密時間和各個接收方的解密時間，縱向表示本文和文獻(xiàn)[1]提出的CPA/CCA2安全的方案。

實驗結(jié)果表明，本文提出的CPA安全方案加密時間相比文獻(xiàn)[1]中的CPA安全方案加密所需時間僅增加約0.54 ms；該方案中額外添加的一個接收方的解密時間僅比其他接收方的解密時間增加約0.54 ms。類似地，本文提出的CCA2安全方案加密時間相比文獻(xiàn)[1]中的CCA2安全方案加密所需時間僅增加約0.55 ms；本文方案中額外添加的一個接收方的解密時間僅比其他接收方的解密時間增加約0.54 ms。因此，本文提出的密碼方案在添加一個接收方的情況下，計算時間僅增加約0.54 ms，效率較高。

表2 方案測試對比

7 應(yīng)用分析

文獻(xiàn)[1]提出使用雙接收方的方案能夠應(yīng)用于緩解TLS協(xié)議[24-26]的安全性問題，而本文提出的三接收方方案也能夠類似運(yùn)用于緩解TLS協(xié)議的安全性問題。此外，如果將本文方案中的用戶2看作高級管理員，用戶3看作一般管理員，用戶4看作消息接收方，則本文提出的方案能夠擴(kuò)展為分級管理的公鑰加密方案。如果要求發(fā)送方每次在消息加密過程中必須使用高級管理員（即用戶2）和部分使用一般管理員（即用戶3），則用戶2能夠監(jiān)管所有接收方的消息，用戶3能夠監(jiān)管部分密文消息。

8 結(jié)束語

本文提出了三接收方公鑰加密方案，該方案具有3個接收方；同時給出了具有選擇明文攻擊安全的公鑰加密方案和具有選擇適應(yīng)性選擇密文攻擊安全的公鑰加密方案；形式化證明了如果DBDH問題和CHD問題是困難的，則本文提出的兩個三接收方公鑰加密方案具有選擇明文攻擊安全和適應(yīng)性選擇密文攻擊安全。對比表明，本文提出的方案與文獻(xiàn)[1]中的方案具有相同的私鑰和公鑰長度，而密文僅增加位、加密和解密計算復(fù)雜度僅增加一項指數(shù)運(yùn)算和一項哈希運(yùn)算，因此該方案效率較高。

[1] DIAMENT T, LEE H K, KEROMYTIS A D, et al. The dual receiver cryptosystem and its applications[C]//Proceedings of the 11th ACM Conference on Computer and Communications Security. 2004: 330-343.

[2] BONEH D, BOYEN X. Short signatures without random oracles and the SDH assumption in bilinear groups[J]. Journal of Cryptology, 2008, 21(2): 149-177.

[3] BONEH D, LYNN B, SHACHAM H. Short signatures from the Weil pairing[C]//International Conference on the Theory and Application of Cryptology and Information Security. 2001: 514-532.

[4] ELGAMAL T. A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Transactions on Information Theory, 1985, 31(4): 469-472.

[5] TSIOUNIS Y, YUNG M. On the security of ElGamal based encryption[C]//International Workshop on Public Key Cryptography. 1998: 117-134.

[6] JOUX A. A one round protocol for tripartite Diffie–Hellman[C]// International algorithmic number theory symposium. 2000: 385-393.

[7] DAMG?RD I. On Σ-protocols[J]. Lecture Notes, University of Aarhus, Department for Computer Science, 2002.

[8] RACKOFF C, SIMON D R. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack[C]//Annual International Cryptology Conference. 1991: 433-444.

[9] DESMEDT Y G. Threshold cryptography[J]. European Transactions on Telecommunications, 1994, 5(4): 449-458.

[10] BAUM C, DAMG?RD I, OECHSNER S, et al. Efficient commitments and zero-knowledge protocols from ring-sis with applications to lattice-based threshold cryptosystems[J]. IACR Cryptology ePrint Archive, 2016, 2016: 997.

[11] WEBER J W. Hierarchical encryption key system for securing digital media: U.S. Patent 7,480,385[P]. 2009-1-20.

[12] BONEH D, BOYEN X, GOH E J. Hierarchical identity based encryption with constant size ciphertext[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2005: 440-456.

[13] SCHUBA C L, KRSUL I V, KUHN M G, et al. Analysis of a denial of service attack on TCP[C]//Proceedings of 1997 IEEE Symposium on Security and Privacy. 1997: 208-223.

[14] CARL G, KESIDIS G, BROOKS R R, et al. Denial-of-service attack-detection techniques[J]. IEEE Internet Computing, 2006, 10(1): 82-89.

[15] OKAMOTO T, POINTCHEVAL D. REACT: rapid enhanced- security asymmetric cryptosystem transform[C]//Cryptographers’ Track at the RSA Conference. 2001: 159-174.

[16] OKAMOTO T, POINTCHEVAL D. The gap-problems: a new class of problems for the security of cryptographic schemes[C]//International Workshop on Public key Cryptography. 2001: 104-118.

[17] GROTH J, SAHAI A. Efficient non-interactive proof systems for bilinear groups[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2008: 415-432.

[18] CHOW S S M, FRANKLIN M, ZHANG H. Practical dual-receiver encryption[C]//Cryptographers’ Track at the RSA Conference. 2014: 85-105.

[19] ZHANG R, HANAOKA G, IMAI H. A generic construction of useful client puzzles[C]//Proceedings of the 4th International Symposium on Information, Computer, and Communications Security. 2009: 70-79.

[20] BAEK J, SAFAVI-NAINI R, SUSILO W. On the integration of public key data encryption and public key encryption with keyword search[C]//International Conference on Information Security. 2006: 217-232.

[21] ZHANG R, IMAI H. Generic combination of public key encryption with keyword search and public key encryption[C]//International Conference on Cryptology and Network Security. 2007: 159-174.

[22] ROGAWAY P. Efficient instantiations of tweakable block ciphers and refinements to modes OCB and PMAC[C]//International Conference on the Theory and Application of Cryptology and Information Security. 2004: 16-31.

[23] WU Q, QIN B, ZHANG L, et al. Ad hoc broadcast encryption[C]//2010 ACM Conference on Computer and Communications Security. 2010: 741-743.

[24] DIERKS T, ALLEN C. The TLS protocol version 1.0[S]. 1999.

[25] KRAWCZYK H, PATERSON K G, WEE H. On the security of the TLS protocol: a systematic analysis[C]//Annual Cryptology Conference. 2013: 429-448.

[26] MAVROGIANNOPOULOS N, VERCAUTEREN F, VELICHKOV V, et al. A cross-protocol attack on the TLS protocol[C]//2012 ACM Conference on Computer and Communications Security. 2012: 62-72.

Triple receiver public key encryption cryptosystem

ZHAO Liutao1, ZHONG Lin2, LIU Jidong2, WANG Caiqun1, WU Dan3

1. Beijing Computing Center,Beijing 100094, China2. Beijing Beike Rongzhi Cloud Computing Science and Technology Ltd., Beijing 100094, China3. National Internet Emergency Center, Beijing 100089, China

A triple receiver public key cryptosystem was proposed. In the cryptosystem, a sender encrypted a message and sent to three receivers, while the three receivers were able to decrypt the message with their own private keys. Based on bilinear map, two triple receiver public key encryption schemes with different security were constructed. If the gap bilinear Diffie-Hellman (GBDH) problem and the computational Diffie-Hellman (CDH) problem were proved formally to be intractable, then the two schemes proposed were semantically secure against chosen-plaintext attacks and against adaptive chosen ciphertext attacks respectively. The proposed scheme only added an exponential operation and a hash operation, and constructed three independent receivers which had a high efficiency. Analyses show that proposed scheme can improve the security of TLS protocol and apply to hierarchical public key cryptosystems.

triple receiver, public key encryption, bilinear map, gap bilinear Diffie-Hellman problem, computational Diffie-Hellman problem

Finance Special Project of Beijing Academy of Science and Technology in 2020

TP393

A

10.11959/j.issn.2096?109x.2020080

趙琉濤（1979? ），男，北京人，北京市計算中心研究員，主要研究方向為信息安全、區(qū)塊鏈、高性能計算。

鐘林（1987? ），男，四川內(nèi)江人，博士，北京北科融智云計算科技有限公司工程師，主要研究方向為公鑰密碼學(xué)、區(qū)塊鏈技術(shù)。

劉吉東（1976? ），男，山東長島人，北京北科融智云計算科技有限公司工程師，主要研究方向為區(qū)塊鏈技術(shù)及軟件工程實施。

王彩群（1989? ），女，河南商丘人，北京市計算中心高級工程師，主要研究方向為機(jī)器學(xué)習(xí)、區(qū)塊鏈、計算材料。

吳丹（1985? ），女，北京人，國家計算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心助理研究員，主要研究方向為網(wǎng)絡(luò)安全。

論文引用格式：趙琉濤, 鐘林, 劉吉東, 等. 三接收方公鑰密碼系統(tǒng)[J]. 網(wǎng)絡(luò)與信息安全學(xué)報, 2020, 6(6): 128-136.

ZHAO L T, ZHONG L, LIU J D, et al. Triple receiver public key encryption cryptosystem[J]. Chinese Journal of Network and Information Security, 2020, 6(6): 128-136.

2020?03?20；

2020?05?06

吳丹，wdan1985@126.com

2020年北京市科學(xué)技術(shù)研究院財政專項