赵琉涛，钟林，刘吉东，王彩群，吴丹

三接收方公钥密码系统

赵琉涛1，钟林2，刘吉东2，王彩群1，吴丹3

（1. 北京市计算中心，北京 100094； 2. 北京北科融智云计算科技有限公司，北京 100094；3.国家计算机网络应急技术处理协调中心，北京 100089）

提出一种三接收方公钥加密方案，该方案中发送方对消息进行加密，而三接收方均能够使用各自的私钥对消息进行解密。基于双线性映射，构造出两个安全性不同的三接收方公钥加密方案。形式化证明如果间隙双线性Diffie-Hellman问题和计算性Diffie-Hellman问题是困难的，则所提的两个方案分别具有选择明文攻击安全和适应性选择密文攻击安全。所提方案仅增加了一项指数运算和一项哈希运算，就实现了3个独立的接收方，因此该方案效率较高。分析表明，该方案能够提高TLS协议的安全性并应用于分级监管公钥密码系统。

三接收方；公钥加密；双线性映射；间隙双线性Diffie-Hellman问题；计算性Diffie-Hellman问题

1 引言

1976年，Diffie-Hellman首次提出公钥密码学，开创了现代密码学的新领域。随后，Rivest、Shamir和Adleman提出第一个实用的RSA公钥密码方案。在公钥加密可证明安全方面，Naor和Dolev等提出可证明安全但低效的公钥加密方案；随后，在随机预言机模型下，Boneh和Franklin提出高效的身份基公钥加密。

公钥加密方案不断发展，从可证明安全到高效性。但是当今社会的发展产生许多新的应用场景，如区块链、5G、物联网。这些新的应用场景需要功能更加丰富的公钥加密方案。上述公钥加密方案均围绕安全性和效率的视角开展，缺乏从多接收方的视角发展，而该方向是至关重要的。

考虑以下两个典型的应用场景。

①Alice需要将同一段数据加密发送给Bob和Carol，则Alice需要使用Bob与Carol的公钥对该段数据加密，并使用零知识证明协议证明这两段密文包含的消息是相等的。因此，Bob和Carol能够确保收到了与对方相同的消息。但是，如果Alice需要将同一段数据发送给Bob、Carol和Dave，则Alice需要使用两次零知识证明协议。该过程将导致用户需要进行计算复杂度较高的零知识证明和较长的数据发送与存储，因此效率较低。

②在一个典型的监管密码系统中，发送方Alice加密消息并发送给接收方Bob。如果管理员需要查看Bob的密文数据，则Alice还需要使用管理员的公钥将消息加密发送给管理员并附带一段零知识证明数据，从而导致效率较低。

针对上述两个典型的应用场景，已有研究提出类似的解决方案。Diament等[1]提出一种双接收方公钥密码方案，该方案使用了两个群上的双线性映射[2-3]。类似于将Diffie-Hellman 密钥交换协议扩展为ElGamal加密方案[4-5]，Diament将三方一轮Diffie-Hellman密钥交换协议[6]扩展为双接收方公钥加密方案。因此，对于上述两个典型应用场景，如果Alice将数据加密发送给Bob和Carol，或发送方Alice将数据发送给接收方Bob和管理员，则不需要使用零知识证明协议[7-8]。因此，该方案极大地降低了计算复杂度和数据长度，从而使协议运行效率较高。但是，如果Alice需要将数据发送给3个接收方或公钥加密系统中有两个管理员，则需要在Diament方案的基础上再使用一次零知识证明协议才能够满足期望的功能。但是，零知识证明协议将极大降低Diament方案的效率，使Diament方案实用性较差。如果使用门限密码系统[9-10]，则系统效率较低，且需要多个接收方合作才能够对密文进行解密。

针对应用场景二，如果使用分级加密方案[11-12]，则能够在一定程度上满足场景二的需求。在分级加密方案中，管理员分发密钥给下级用户。发送方使用下级用户的公钥对消息加密，则接收方和管理员均能够解密。但是，该方案的缺点在于管理员拥有了下级用户的私钥，下级用户数据的安全性不仅取决于算法的安全性，还取决于管理员对私钥的保密性和管理员的诚实性。如果管理员不够诚实可靠，则下级用户的消息是不安全的。此外，管理员拥有大量的下级用户私钥，且管理员的根密钥非常重要，容易导致攻击者对管理员进行各种攻击，如拒绝服务攻击[13-14]或对根密钥进行攻击。

因此，本文提出一种高效的三接收方公钥密码方案。该方案中，存在3个独立的接收方。发送方使用3个独立的接收方的公钥对消息进行加密，则3个接收方均能够使用各自的私钥对消息解密。该过程不需要零知识证明协议对消息的一致性进行证明，因为该过程中消息加密生成的密文具有多功能性，使三接收方的私钥均能够解密密文。本文方案是对Diament方案的进一步扩展，而几乎不降低效率。本文提出的方案仅需要在Diament方案的基础上额外添加一项指数运算和一项哈希运算，因此该方案效率较高。

2 研究现状

Diament[1]等提出一个双接收方公钥密码系统。该系统中的两个独立接收方能够使用各自的私钥对发送方生成的密文进行高效解密。如果其中一个接收方为管理员，则该公钥加密方案具有较好的监管应用。Diament等使用REACT转换[15]，在缺口双线性Diffie-Hellman假设下[16]，将方案从选择明文攻击安全增强到适应性选择密文攻击安全。但基于Groth-Sahai证明系统[17]构造高效的双接收方密码系统需要约100个群元素。随后，Chow等[18]对Diament提出的双接收方公钥加密方案进一步形式化，定义了双接收方公钥加密方案的可靠性（soundness）以确保两个独立的接收方能够解密获得相同的明文信息。该可靠性使双接受公钥加密方案成为一个强大的密码学原语，如允许完美不可延展性和明文可识别性。

同时，双接收方密码系统能够解决安全难题（security puzzles），Zhang等[19]构造基于身份基加密方案对该安全难题进行了类似的解决。Baek[20]和Zhang[21]等研究了安全的结合公钥加密方案与关键词搜索公钥加密方案。Rogaway[22]研究在保护密文长度的情况下，安全地结合选择明文攻击安全和选择密文攻击安全的公钥加密。最后，Wu等[23]研究了自组织广播加密方案，方案中任意发送方能够加密消息并发送给一个自组织群，且群中接收方能够独立解密而不需要可信第三方。但该方案仅考虑了选择明文攻击安全。

3 预备知识

3.1 双线性映射

本文方案需要使用双线性映射，以下对双线性映射进行简要介绍。

3.2 困难问题

本文方案的安全性依赖于以下4个相关的复杂性假设，该假设使用群上的离散对数困难问题。

4 方案设计

4.1 选择明文安全的三接收方公钥加密方案

（4）解密：用户2、用户3、用户4使用各自的私钥对密文进行解密。

公式推导如下。

公式推导过程如下。

公式推导过程如下。

4.2 适应性选择密文安全的三接收方公钥加密方案Enc2

（2）密钥生成：密钥生成过程与选择明文安全的三接收方公钥加密方案中的密钥生成过程相同。

（4）解密。用户2、用户3、用户4使用各自的私钥对密文进行解密。

5 安全模型与形式化证明

如果攻击者从用户3和用户4角度对本文提出的两个方案进行攻击，则文献[1]已经证明公钥加密方案满足选择明文攻击安全，公钥加密方案满足适应性选择密文攻击安全。但是，本文提出的三接收方公钥密码系统中，攻击者还可能从用户2角度对方案进行攻击。因此，本节将证明如下定理。

定理1 从用户2角度，如果计算性Diffie- Hellman问题是困难的，则在随机预言机模型下，本文提出的公钥加密方案满足选择明文攻击安全。

定理2 从用户2角度，如果计算性Diffie- Hellman问题是困难的，则在随机预言机模型下，本文提出的公钥加密方案满足适应性选择密文攻击安全。

文献[15]提出REACT方案，将选择明文攻击安全的公钥加密方案转换为适应性选择密文攻击安全。本文提出的方案正是基于文献[15]的REACT转换对方案进行安全性提升的，即转换为适应性选择密文攻击安全。因此，如果本文提出的公钥加密方案从用户2角度满足选择明文攻击安全，则根据文献[15]，本文提出的公钥加密方案从用户2角度满足选择密文攻击安全。因此，本文仅对定理1进行安全性证明，而定理2的安全性证明参见文献[15]。

5.1 安全模型

5.2 形式化证明

（1）不可区分性仿真：上述说明仿真过程的正确性。仿真过程的随机性包括密钥生成过程中的随机数、对哈希询问的响应值和挑战值的生成，分别是

（2）仿真成功概率：在仿真过程中，不存在中断过程，仿真成功概率为1。

6 方案对比

如表1所示，将本文提出的方案与文献[1]中的方案进行对比。表1中，第2至4列展示了方案的私钥、公钥和密文的长度；第5至8列分别展示了加密算法复杂度、各个接收方的解密计算复杂度、接收方个数和算法基于的复杂性假设。

其中，E是指数运算，P是双线性映射，H是哈希运算。如表1所示，本文在文献[1]的基础上添加了1个接收方，而用户的私钥和公钥长度均不变，本文CPA安全方案和CCA2安全方案的密文长度仅增加。在加密计算复杂度方面，本文CPA安全方案和CCA2安全方案均只增加了一项指数运算和一项哈希运算，而没有增加映射运算。此外，指数运算和哈希函数的运算效率较高。在解密计算复杂度方面，用户3和用户4的解密复杂度与文献[1]中两个用户的解密复杂度相等，而用户2的解密复杂度仅增加了一项指数运算和一项哈希运算，该过程效率也较高。文献[1]的方案基于DBDH复杂性假设，而本文额外增加了CDH复杂性假设。由于CDH复杂性假设是当前密码算法中最经典的困难问题，因此该假设的引入不会导致算法安全性降低。

表1 方案性能对比

此外，将本文方案与文献[1]中的方案进行实验测试。实验设备信息：内核x86_64 操作系统Linux 4.17.6-1-ARCH，运算芯片Intel i5-7200U 2.50 GHz，内存8 GB。实验选择SHA256作为哈希函数的具体实现和使用超奇异椭圆曲线；有限域为512 bit，离散对数安全范围为1 024 bit，椭圆曲线群的阶为160 bit。如表2所示，横向表示算法的加密时间和各个接收方的解密时间，纵向表示本文和文献[1]提出的CPA/CCA2安全的方案。

实验结果表明，本文提出的CPA安全方案加密时间相比文献[1]中的CPA安全方案加密所需时间仅增加约0.54 ms；该方案中额外添加的一个接收方的解密时间仅比其他接收方的解密时间增加约0.54 ms。类似地，本文提出的CCA2安全方案加密时间相比文献[1]中的CCA2安全方案加密所需时间仅增加约0.55 ms；本文方案中额外添加的一个接收方的解密时间仅比其他接收方的解密时间增加约0.54 ms。因此，本文提出的密码方案在添加一个接收方的情况下，计算时间仅增加约0.54 ms，效率较高。

表2 方案测试对比

7 应用分析

文献[1]提出使用双接收方的方案能够应用于缓解TLS协议[24-26]的安全性问题，而本文提出的三接收方方案也能够类似运用于缓解TLS协议的安全性问题。此外，如果将本文方案中的用户2看作高级管理员，用户3看作一般管理员，用户4看作消息接收方，则本文提出的方案能够扩展为分级管理的公钥加密方案。如果要求发送方每次在消息加密过程中必须使用高级管理员（即用户2）和部分使用一般管理员（即用户3），则用户2能够监管所有接收方的消息，用户3能够监管部分密文消息。

8 结束语

本文提出了三接收方公钥加密方案，该方案具有3个接收方；同时给出了具有选择明文攻击安全的公钥加密方案和具有选择适应性选择密文攻击安全的公钥加密方案；形式化证明了如果DBDH问题和CHD问题是困难的，则本文提出的两个三接收方公钥加密方案具有选择明文攻击安全和适应性选择密文攻击安全。对比表明，本文提出的方案与文献[1]中的方案具有相同的私钥和公钥长度，而密文仅增加位、加密和解密计算复杂度仅增加一项指数运算和一项哈希运算，因此该方案效率较高。

[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− ），男，北京人，北京市计算中心研究员，主要研究方向为信息安全、区块链、高性能计算。

钟林（1987− ），男，四川内江人，博士，北京北科融智云计算科技有限公司工程师，主要研究方向为公钥密码学、区块链技术。

刘吉东（1976− ），男，山东长岛人，北京北科融智云计算科技有限公司工程师，主要研究方向为区块链技术及软件工程实施。

王彩群（1989− ），女，河南商丘人，北京市计算中心高级工程师，主要研究方向为机器学习、区块链、计算材料。

吴丹（1985− ），女，北京人，国家计算机网络应急技术处理协调中心助理研究员，主要研究方向为网络安全。

论文引用格式：赵琉涛, 钟林, 刘吉东, 等. 三接收方公钥密码系统[J]. 网络与信息安全学报, 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年北京市科学技术研究院财政专项