利用环上容错学习问题构造可链接环签名方案

doi:10.3778/j.issn.1673-9418.1904022

摘要/Abstract

摘要：

针对格上可链接环签名方案中存在密钥较大、效率较低的问题，基于环上容错学习（RLWE）难题，依据“同态承诺→∑-协议→Fiat-Shamir转化”的技术路线，重新构造一个格上可链接环签名方案。首先构造一个基于RLWE难题的多项式环上的同态承诺方案，然后基于承诺方案设计一个∑-协议，并利用Fiat-Shamir转化方法将该∑-协议转化为可链接环签名方案，最后基于该可链接环签名方案提出一个简易的数字货币模型。安全分析表明，由于所提方案基于RLWE困难问题构建，方案的安全性可规约至格上困难问题，抵抗量子计算机攻击。效率分析表明，与以往格上可链接环签名方案相比，由于方案中环元素取自小多项式，所提方案具有更短的密钥尺寸和更高的计算效率，且方案描述更简单。

关键词: 承诺方案, 零知识证明, 环上容错学习问题（RLWE）, 可链接环签名

Abstract:

In order to solve the problem of large key size and low efficiency in the linkable ring signature scheme on lattice, this paper reconstructs the linkable ring signature scheme from lattice based on the ring learning with errors (RLWE) problem, according to the technical route of “homomorphic commitment→∑-protocol→Fiat-Shamir transformation”. This paper first constructs a homomorphic commitment scheme over a polynomial ring based on the RLWE problem, and then designs a ∑-protocol based on the commitment scheme, and transforms the ∑-protocol into a linkable ring signature scheme using the Fiat-Shamir transformation methods. Finally, this paper proposes a simple digital currency model based on the linkable ring signature scheme. Security analysis shows since the proposed scheme is constructed based on the problem of RLWE, its security can reduce to the lattice-based difficult problem and resist the quantum computer attack. Efficiency analysis shows compared with the previous linkable ring signature schemes on lattice, since the ring elements in the scheme are taken from small polynomials, the proposed scheme has shorter key size and higher computational efficiency, and the description of the scheme is simpler.

Key words: commitment scheme, zero-knowledge proof, ring learning with errors (RLWE) , linkable ring signature

叶青，王文博，李莹莹，秦攀科，赵宗渠，王永军. 利用环上容错学习问题构造可链接环签名方案[J]. 计算机科学与探索, 2020, 14(7): 1164-1172.

YE Qing, WANG Wenbo, LI Yingying, QIN Panke, ZHAO Zongqu, WANG Yongjun. Using Ring Learning with Errors Problem to Construct Linkable Ring Signature Scheme[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(7): 1164-1172.

参考文献

[1] Rivest R L, Shamir A, Tauman Y. How to leak a secret[C]//LNCS 2248: Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, Australia, Dec 9-13, 2001. Berlin, Heidelberg: Springer, 2001: 552-565.
[2] Liu J K, Wei V K, Wong D S. Linkable spontaneous anonymous group signature for Ad Hoc groups[C]//LNCS 3108: Proceedings of the 9th Australasian Conference on Information Security and Privacy, Sydney, Jul 13-15, 2004. Berlin, Heidelberg: Springer, 2004: 325-335.
[3] Liu J K, Au M H, Huang X, et al. New insight to preserve online survey accuracy and privacy in big data era[C]//LNCS 8713: Proceedings of the 19th European Symposium on Research in Computer Security, Poland, Sep 7-11, 2014. Berlin, Heidelberg: Springer, 2014: 182-199.
[4] Tsang P P, Wei V K. Short linkable ring signatures for E-Voting, E-Cash and attestation[C]//LNCS 3439: Proceedings of the 1st International Conference on Information Security Practice and Experience, Singapore, Apr 11-14, 2005. Berlin, Heidelberg: Springer, 2005: 48-60.
[5] Noether S. Ring signature confidential transactions for monero[EB/OL]. [2019-12-19]. https://eprint.iacr.org/2015/1098.pdf.
[6] Au M H, Liu J K, Susilo W, et al. Certificate based (linkable) ring signature[C]//LNCS 4464: Proceedings of the 3rd International Conference on Information Security Practice and Experience, Hong Kong, China, May 7-9, 2007. Berlin, Heidelberg: Springer, 2007: 79-92.
[7] Liu J K, Au M H, Susilo W, et al. Linkable ring signature with unconditional anonymity[J]. IEEE Transactions on Know-ledge and Data Engineering, 2014, 26(1): 157-165.
[8] 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.
[9] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120-126.
[10] Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Review, 1999, 41(2): 303-332.
[11] Tian M M, Huang L S, Yang W. Efficient lattice-based ring signature scheme[J]. Chinese Journal of Computers, 2012, 35(4): 712-718. 田苗苗, 黄刘生, 杨威. 高效的基于格的环签名方案[J]. 计算机学报, 2012, 35(4): 712-718.
[12] Yang R, Au M H, Lai J, et al. Lattice-based techniques for accountable anonymity: composition of abstract stern??s protocols and weak PRF with efficient protocols from LWR[EB/OL]. [2019-12-19]. https://eprint.iacr.org/2017/781.pdf.
[13] Ajtai M. Generating hard instances of lattice problems[C]// Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, May 22-24, 1996. New York: ACM, 1996: 99-108.
[14] Zhang H, Zhang F G, Tian H B, et al. Anonymous post-quantum cryptocash[C]//LNCS 10957: Proceedings of the 22nd International Conference on Financial Cryptography and Data Security, Nieuwpoort, Feb 26-Mar 2, 2018. Berlin, Heidelberg: Springer, 2018: 461-479.
[15] Groth J, Kohlweiss M. One-out-of-many proofs: or how to leak a secret and spend a coin[C]//LNCS 9057: Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Bulgaria, Apr 26-30, 2015. Berlin, Heidelberg: Springer, 2015: 253-280.
[16] Baum C, Lin H, Oechsner S. Towards practical lattice-based one-time linkable ring signatures[C]//LNCS 11149: Proceedings of the 20th International Conference on Information and Communications Security, Lille, Oct 29-31, 2018. Berlin, Heidelberg: Springer, 2018: 303-322.
[17] Torres W A A, Steinfeld R, Sakzad A, et al. Post-quantum one-time linkable ring signature and application to ring confidential transactions in blockchain (lattice RingCT v1.0)[C]//LNCS 10946: Proceedings of the 23rd Australasian Conference on Information Security and Privacy, Wollongong, Jul 11-13, 2018. Berlin, Heidelberg: Springer, 2018: 558-576.
[18] Ducas L, Durmus A, Lepoint T, et al. Lattice signatures and bimodal Gaussians[C]//LNCS 8042: Proceedings of the 33rd Annual Cryptology Conference, Santa Barbara, Aug 18-22, 2013. Berlin, Heidelberg: Springer, 2013: 40-56.
[19] Micciancio D. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions[J]. Computational Complexity, 2007, 16(4): 365-411.
[20] Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings[C]//LNCS 6110: Proceedings of the 2010 Advances in Cryptology. Berlin, Heidelberg: Springer, 2010: 43.
[21] Liu J K, Wong D S. Linkable ring signatures: security models and new schemes[C]//LNCS 3481: Proceedings of the 2005 International Conference on Computational Science and Its Applications, Singapore, May 9-12, 2005. Berlin, Heidelberg: Springer, 2005: 614-623.
[22] Pedersen T P. Non-interactive and information-theoretic secure verifiable secret sharing[C]//LNCS 576: Proceedings of the 11th Annual International Cryptology Conference, Santa Barbara, Aug 11-15, 1991. Berlin, Heidelberg: Springer, 1991: 129-140.
[23] Langlois A, Stehlé D. Worst-case average-case reductions for module lattices[J]. Designs, Codes and Cryptography, 2015, 75(3): 565-599.
[24] Fiat A, Shamir A. How to prove yourself: practical solutions to identification and signature problems[C]//LNCS 263: Proceedings of the 1986 Annual International Cryptology Conference on the Theory and Application of Cryptographic Techniques, Santa Barbara, Aug 11-15, 1986. Berlin, Heidelberg: Springer, 1986: 186-194.
[25] Saberhagen N V. CryptoNote v2.0[EB/OL]. (2013-10-17). [2019-12-19]. https://cryptonote.org/whitepaper.pdf.