Identity-Based Linkable Ring Signature from Lattice in Random Oracle Model

doi:10.3778/j.issn.1673-9418.2310057

Abstract

Abstract: As a simplified group signature, ring signature has no administrator and does not require cooperation among ring members. The signer only needs his private key and the public keys of other ring members to sign. Because of its natural anonymity, ring signature is widely used in scenarios such as anonymous voting, e-cash and vehicular ad-hoc network. As a variant of the ring signature concept, linkable ring signature can verify whether two signatures come from the same signer while maintaining anonymity, thus effectively solving malicious reporting in the reporting system and double spending in the blockchain system, further enriching the application scenarios of ring signature. This paper proposes an identity-based linkable ring signature scheme from lattice, which uses G-trapdoor generation technology to generate the system key, uses its improved trapdoor delegation technology and the preimage sampling algorithm to extract the user??s private key, and uses the rejection sampling technology under bimodal Gaussian to generate the signature. Through security analysis, the proposed scheme meets unconditional anonymity, unforgeability and linkability in random oracle model, and the security can be reduced to the hardness assumption of the small integer solution problem (short integer solution, SIS) on lattice. Compared with existing schemes, both signature generation time overhead and verification time overhead are reduced by about 50%. Finally, the e-voting protocol is designed by combining the scheme of this paper with a secret sharing algorithm based on XOR operation, which ensures the privacy and fairness of the e-voting system.

Key words: linkable ring signature, lattice, anonymity, G-trapdoor, rejection sampling

摘要： 作为一种简化的群签名，环签名没有管理员角色，不需要环成员之间合作；签名者仅需自己私钥和其他环成员公钥即可进行签名操作。因其天然的匿名性，环签名在匿名投票、电子货币和车联网等场景得到广泛应用。可链接环签名作为环签名概念的一种变体，在保持了匿名性的同时还可验证两个签名是否来自同一签名者，从而有效解决举报系统中的恶意举报及区块链系统中的双重花费等问题，进而丰富了环签名的应用场景。提出一种基于身份的格基可链接环签名方案，采用G-陷门生成技术生成系统密钥，使用其改进后的陷门委派技术和原像采样算法提取用户私钥，利用双峰高斯分布下的拒绝采样技术生成签名。经安全分析，所提方案在随机预言机模型下满足无条件匿名性、不可伪造性和可链接性，安全性可规约至格上的小整数解（SIS）问题，与现有的方案相比，签名生成时间开销和签名验证时间开销都减少约50%。最后将该方案和基于异或秘密共享算法结合，设计了电子投票协议，从而保证电子投票系统的隐私性和公正性。

关键词: 可链接环签名, 格, 匿名性, G-陷门, 拒绝采样

XIE Jia, WANG Lu, LIU Shizhao, GAO Juntao, WANG Baocang. Identity-Based Linkable Ring Signature from Lattice in Random Oracle Model[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(8): 2190-2202.

谢佳, 王露, 刘仕钊, 高军涛, 王保仓. 随机预言机模型下基于身份的格基可链接环签名[J]. 计算机科学与探索, 2024, 18(8): 2190-2202.

References

[1] RIVEST R L, SHAMIR A, TAUMAN Y. How to leak a secret[C]//Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Dec 9-13, 2001. Berlin, Heidelberg: Springer, 2001: 552-556.
[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] 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.
[4] DODIS Y, KIAYIAS A, NICOLOSI A, et al. Anonymous identification in ad hoc groups[C]//LNCS 3027: Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, May 2-6, 2004. Berlin, Heidelberg: Springer, 2004: 609-626.
[5] AU M H, CHOW S S M, SUSILO W, et al. Short linkable ring signatures revisited[C]//LNCS 4043: Proceedings of the 3rd European Conference on Public Key Infrastructure: Theory and Practice, Turin, Jun 19-20, 2006. Berlin, Heidelberg: Springer, 2006: 101-115.
[6] JEONG I R, KWON J O, LEE D H. Ring signature with weak linkability and its applications[J]. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(8): 1145-1148.
[7] AU M H, LIU J K, SUSILO W, et al. Secure ID-based linkable and revocable-iff-linked ring signature with constant-size construction[J]. Theoretical Computer Science, 2013, 469: 1-14.
[8] LIU J K, AU M H, SUSILO W, et al. Linkable ring signature with unconditional anonymity[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 26(1): 157-165.
[9] 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. Cham: Springer, 2018: 558-576.
[10] 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. Cham: Springer, 2018: 303-322.
[11] TORRES W A A, KUCHTA V, STEINFELD R, et al. Lattice ringCT v2.0 with multiple input and multiple output wallets[C]//LNCS 11547: Proceedings of 24th Australasian Conference on Information Security and Privacy, Christchurch, Jul 3-5, 2019. Cham: Springer, 2019: 156-175.
[12] LU X Y, AU M H, ZHANG Z F. Raptor: a practical lattice-based (linkable) ring signature[C]//LNCS 11464: Proceedings of 17th International Conference on Applied Cryptography and Network Security, Bogota, Jun 5-7, 2019. Cham: Springer, 2019: 110-130.
[13] 叶青, 王文博, 李莹莹, 等. 利用环上容错学习问题构造可链接环签名方案[J]. 计算机科学与探索, 2020, 14(7): 1164-1172.
YE Q, WANG W B, LI Y Y, et al. 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.
[14] 汤永利, 夏菲菲, 叶青, 等. 格上基于身份的可链接环签名[J]. 密码学报, 2021, 8(2): 232-247.
TANG Y L, XIA F F, YE Q, et al. Identity-based linkable ring signature on lattice[J]. Journal of Cryptologic Research, 2021, 8(2): 232-247.
[15] TANG Y L, XIA F F, YE Q, et al. Identity-based linkable ring signature on NTRU lattice[J]. Security and Communication Networks, 2021, 2021: 1-17.
[16] SHAMIR A. Identity-based cryptosystems and signature schemes[C]//LNCS 196: Proceedings of Workshop on the Theory and Application of Cryptographic Techniques, Santa Barbara, Aug 19-22, 1984. Berlin, Heidelberg: Springer, 1984: 47-53.
[17] GENTRY C, PEIKERT C, VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions[C]//Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, May 17-20, 2008.?New York: ACM, 2008: 197-206.
[18] MICCIANCIO D, PEIKERT C. Trapdoors for lattices: simpler, tighter, faster, smaller[C]//LNCS 7237: Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, Apr 15-19, 2012. Berlin, Heidelberg: Springer, 2012: 700-718.
[19] AJTAI M. Generating hard instances of lattice problems[C]//Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, May 22-24, 1996. New York: ACM, 1996: 99-108.
[20] MICCIANCIO D, REGEV O. Worst-case to average-case reductions based on Gaussian measures[J]. SIAM Journal on Computing, 2007, 37(1): 267-302.
[21] LYUBASHEVSKY V. Lattice signatures without trapdoors[C]//LNCS 7237: Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, Apr 15-19, 2012. Berlin, Heidelberg: Springer, 2012: 738-755.
[22] 夏高, 何成万. 一种基于异或运算的(k,n)门限秘密共享算法[J]. 计算机工程, 2021, 47(10): 111-115.
XIA G, HE C W. A (k,n)-threshold secret sharing algorithm based on XOR operation[J]. Computer Engineering, 2021, 47(10): 111-115.
[23] 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, Sofia, Apr 26-30, 2015. Cham: Springer, 2015: 253-280.
[24] 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.
[25] DUCAS L, DURMUS A, LEPOINT T, et al. Lattice signatures and bimodal Gaussians[C]//LNCS 8042: Proceedings of the 33rd Annual International Cryptology Conference, Santa Barbara, Aug 18-22, 2013. Berlin, Heidelberg: Springer, 2013: 40-56.
[26] BELLARE M, NEVEN G. Multi-signatures in the plain public-key model and a general forking lemma[C]//Proceedings of the 13th ACM Conference on Computer and Communications Security, Alexandria, Oct 30-Nov 3, 2006. New York: ACM, 2006: 390-399.