Page 280 - 《软件学报》2021年第10期

3252 Journal of Software 软件学报 Vol.32, No.10, October 2021

求逆运算的复杂性远大于高斯采用和矩阵向量乘法运算(陷门生成、原像抽样和带陷门的求逆算法的复杂度是
影响格密码实用性的重要原因),因此,方案 M的计算效率较高.
从表 5 和表 7 可以看出:当发送 N 个消息到 N 个接收方的情况下,由于 LWJ13 和 ZXX18 的密文量和计算
量呈 N 倍增加,而本文方案 M密文量与计算量不变,因此,方案 M的密文量只近似为 LWJ13 和 ZXX18 方案的
3/N,计算效率更胜于 LWJ13 和 ZXX18 方案.

5 结 论

随机数重用在构造多接收方密码方案时可以有效地节约系统开销,但容易导致方案的安全问题.研究如何
进行安全的随机数重用,是一个非常有意义的研究课题.随机数全重用和随机数无重用可以看成是随机数部分
重用的两种情况:当重用的随机数个数为 0 时,随机数重用退化成随机数无重用;当重用的随机数个数为方案中
所有随机数时,随机数重用演化成随机数全重用.本文将随机数重用的概念丰富到另一种更常见的情况——随
机数部分重用,研究了安全重用部分随机数的相关理论,将该理论应用到基于格的多接收方签密中,首次构造了
一个基于格的可证明安全的 PRRU-MM-MR 签密方案.与直接构造方式相比,该方案的计算开销得到一定的节
约,密文量节约了近 25%.本文的工作为构造多接收方签密方案提供了一种通用方法,即:先构造或选定一个可
再生的标准签密方案;然后再借鉴定义 5 的方法,基于标准签密方案构造相应的部分随机数重用的多接收方签
密方案.另外,本文的方法不仅限于签密,也可适用于签名或者加密的情况.

References:
[1] Hastad J. Solving simultaneous modular equations of low degree. SIAM Journal on Computing, 1988,17(2):336341.
[2] Baudron O, Pointcheval D, Stern J. Extended notions of security for multicast public key cryptosystems. In: Proc. of the Int’l
Colloquium on Automata, Languages, and Programming. Berlin, Heidelberg: Springer-Verlag, 2000. 499511.
[3] Bellare M, Boldyreva A, Micali S. Public-key encryption in a multi-user setting: Security proofs and improvements. In: Proc. of the
Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg: Springer-Verlag, 2000. 259274.
[4] Kurosawa K. Multi-recipient public-key encryption with shortened ciphertext. In: Proc. of the Int’l Workshop on Public Key
Cryptography. Berlin, Heidelberg: Springer-Verlag, 2002. 4863.
[5] ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. on Information Theory,
1985,31(4):469472.
[6] Cramer R, Shoup V. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: Proc. of the
Annual Int’l Cryptology Conf. Berlin, Heidelberg: Springer-Verlag, 1998. 1325.
[7] Bellare M, Boldyreva A, Staddon J. Randomness re-use in multi-recipient encryption schemeas. In: Proc. of the Int’l Workshop on
Public Key Cryptography. Berlin, Heidelberg: Springer-Verlag, 2003. 8599.
[8] Bellare M, Boldyreva A, Kurosawa K, et al. Multirecipient encryption schemes: How to save on bandwidth and computation
without sacrificing security. IEEE Trans. on Information Theory, 2007,53(11):39273943.
[9] Wei P, Zheng Y, Wang W. Multi-recipient encryption in heterogeneous setting. In: Proc. of the Int’l Conf. on Information Security
Practice and Experience. Cham: Springer-Verlag, 2014. 462480.
[10] Hajiabadi M, Kapron BM. Reproducible circularly secure bit encryption: Applications and realizations. Journal of Cryptology,
2017,30(4):11871237.
[11] Zhang J, Ou P. Privacy-preserving multi-receiver certificateless broadcast encryption scheme with de-duplication. Sensors, 2019,
19(15):3370.
[12] Cheng H, Li X, Qian H, et al. CCA secure multi-recipient KEM from LPN. In: Proc. of the Int’l Conf. on Information and
Communications Security. Cham: Springer-Verlag, 2018. 513529.
[13] Zheng Y. Digital signcryption or how to achieve cost (signature &encryption) ≪ cost (signature)+ cost (encryption). In: Proc. of
the Annual Int’l Cryptology Conference. Berlin, Heidelberg: Springer-Verlag, 1997. 165179.
[14] Han Y, Gui X. Adaptive secure multicast in wireless networks. Int’l Journal of Communication Systems, 2009,22(9):12131239.