Efficient Linkable Ring Signature Scheme

doi:10.19678/j.issn.1000-3428.0069288

Abstract

Abstract:

A linkable ring signature, which is a special type of ring signature, can aid in verifying whether two signatures have been signed by the same user, without compromising anonymity. This feature enables it to play an important role in blockchains. However, most of the currently available linkable ring signature schemes are inefficient, and some of them are at risk of being forged owing to the signature labels. This study constructs a new lattice-based linkable ring signature scheme using rejection sampling, in which a formal security proof of the unforgeability of linkable ring signatures is provided in a random oracle model. Unlike existing schemes with a multi-round Hash function to hide user identity, this scheme places the user′s identity characteristics into verification public keys. In other words, the real signer first expands the private key according to certain rules to form an effective ring signature private key and then uses rejection sampling technology to make the linkable ring signature indistinguishable. Consequently, the number of matrix vector multiplication operations in the scheme is reduced, improving its efficiency and shortening the signature size. Furthermore, the private keys of this scheme are jointly generated by the key generation center and users, and the label is multiplied by the private key and the public matrix. This scheme solves the problem faced by some existing schemes, i.e., legitimate users can maliciously forge labels when signing, while ensuring the anonymity of ring signatures. In addition, the linkability can be proven using a random oracle model. The results show that this scheme has advantages in terms of computational efficiency and signature size.

Key words: lattice-based cryptography, linkable ring signature, rejection sampling, random oracle model, Small Integer Solution (SIS)

摘要：

可链接环签名作为一种特殊性质的环签名，能够在保持匿名性的同时验证两个签名是否为同一用户所签。这种良好的性质让它在区块链中发挥着重要作用。然而，现有的可链接环签名方案大都效率不高，且部分方案中所使用的标签存在被伪造的风险。利用拒绝抽样技术构建一个新的基于格的可链接环签名方案，并且给出了随机预言模型下可链接环签名具有不可伪造性的形式化安全证明。不同于现有的利用多轮哈希函数来隐藏用户身份的方案，该方案将用户身份特征隐藏到验证公钥中，即真实的环签名者先将私钥按一定规则扩充形成有效的环签名私钥，再利用拒绝抽样技术使得生成的可链接环签名具有不可区分性，减少整个方案的矩阵向量乘法运算次数，从而提高方案效率，缩短签名尺寸。该方案的私钥由秘钥生成中心与用户共同生成，标签由私钥与公共矩阵相乘，在保证环签名匿名性的同时解决了部分现有方案中合法用户在签名时可以恶意伪造标签的问题。此外，给出了随机预言模型下可链接性的安全证明。实验结果表明，该方案在运算效率和签名尺寸方面均具有优势。

关键词: 格密码, 可链接环签名, 拒绝抽样, 随机预言模型, 小整数解

ZHAO Jiangdong, CHEN Hu, WANG Xiaoyi. Efficient Linkable Ring Signature Scheme[J]. Computer Engineering, 2025, 51(10): 203-212.

赵姜冬, 陈虎, 王晓毅. 高效的可链接环签名方案[J]. 计算机工程, 2025, 51(10): 203-212.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0069288

https://www.ecice06.com/EN/Y2025/V51/I10/203

Figures/Tables 8

Fig.1 Comparison of signature lengths

Fig.2 Comparison of signature generation time consumption

Fig.3 Comparison of signature lengths between the proposed scheme and the scheme in reference [9]

Fig.4 Comparison of signature generation time between the proposed scheme and the scheme in reference [9]

References 26

1	RIVEST R L, SHAMIR A, TAUMAN Y. How to leak a secret[C]//Proceeding of International Conference on the Theory and Application of Cryptology and Information Security. Berlin, Germany: Springer, 2001: 552-565.
2	LIU J K, WEI V K, WONG D S. Linkable spontaneous anonymous group signature for ad hoc groups[C]//Proceedings of Australasian Conference on Information Security and Privacy. Berlin, Germany: Springer, 2004: 325-335.
3	AU M H, CHOW S S M, SUSILO W, et al. Short linkable ring signatures revisited[C]//Proceedings of European Public Key Infrastructure Workshop. Berlin, Germany: Springer, 2006: 101-115.
4	HON Y T , LIU J K , HO A M , et al. Efficient linkable and/or threshold ring signature without random oracles. The Computer Journal, 2013, 56 (4): 407- 421. doi: 10.1093/comjnl/bxs115
5	GU K , DONG X , WANG L . Efficient traceable ring signature scheme without pairings. Advances in Mathematics of Communications, 2020, 14 (2): 256- 263.
6	DENG L Z , SHI H Y , GAO Y . Certificateless linkable ring signature scheme. IEEE Access, 2020, 8, 54641- 54651. doi: 10.1109/ACCESS.2020.2981360
7	王伊婷, 万武南, 张仕斌, 等. 基于SM9算法的可链接环签名方案. 计算机应用, 2024, 44 (2): 3709- 3716.
	WANG Y T , WAN W N , ZHANG S B , et al. Linkable ring signature scheme based on SM9 algorithm. Journal of Computer Applications, 2024, 44 (2): 3709- 3716.
8	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]//Proceedings of Australasian Conference on Information Security and Privacy. Berlin, Germany: Springer, 2018: 558-576.
9	BAUM C, LIN H, OECHSNER S. Towards practical lattice-based one-time linkable ring signatures[C]//Proceedings of International Conference on Information and Communications Security. Berlin, Germany: Springer, 2018: 303-322.
10	汤永利, 夏菲菲, 叶青, 等. 格上基于身份的可链接环签名. 密码学报, 2021, 8 (2): 232- 247.
	TANG Y L , XIA F F , YE Q , et al. Identity-based linkable ring signature on lattice. Journal of Cryptologic Research, 2021, 8 (2): 232- 247.
11	曹成堂, 游林, 胡耿然. 一种新的格上基于身份的可链接环签名方案. 密码学报, 2022, 9 (6): 969- 981.
	CAO C T , YOU L , HU G R . A new identity-based linkable ring signature scheme on lattices. Journal of Cryptologic Research, 2022, 9 (6): 969- 981.
12	贾小英, 何德彪, 许芷岩, 等. 高效的基于身份的环签名体制. 密码学报, 2017, 4 (4): 392- 404.
	JIA X Y , HE D B , XU Z Y , et al. An efficient identity-based ring signature scheme over a lattice. Journal of Cryptologic Research, 2017, 4 (4): 392- 404.
13	YE Q, ZHAO N N, WANG X J, et al. Linkable ring signature scheme from NTRU lattice[C]//Proceedings of the 8th International Conference on Artificial Intelligence and Security. Berlin, Germany: Springer, 2022: 40-53.
14	LANGLOIS A , STEHLÉ D . Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 2015, 75 (3): 565- 599. doi: 10.1007/s10623-014-9938-4
15	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. New York, USA: ACM Press, 2008: 197-206.
16	AJTAI M. Generating hard instances of the short basis problem[C]//Proceedings of the 26th Conference on Automata, Languages and Programming. [S. l. ]: AAAI Press, 2002: 1-9.
17	LYUBASHEVSKY V. Lattice signatures without trapdoors[C]//Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer, 2012: 738-755.
18	JIANG Z L, LIANG Y D, LIU Z C, et al. Lattice-based proxy signature scheme with reject sampling method[C]//Proceedings of International Conference on Security, Pattern Analysis, and Cybernetics (SPAC). Washington D.C., USA: IEEE Press, 2017: 558-563.
19	LI C Y , TIAN Y , CHEN X B , et al. An efficient anti-quantum lattice-based blind signature for blockchain-enabled systems. Information Sciences, 2021, 546, 253- 264. doi: 10.1016/j.ins.2020.08.032
20	ZHANG P Y , JIANG H , ZHENG Z H , et al. A new post-quantum blind signature from lattice assumptions. IEEE Access, 2018, 6, 27251- 27258. doi: 10.1109/ACCESS.2018.2833103
21	LYUBASHEVSKY V, SEILER G. Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs[C]//Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer, 2018: 204-224.
22	POINTCHEVAL D , STERN J . Security arguments for digital signatures and blind signatures. Journal of Cryptology, 2000, 13 (3): 361- 396. doi: 10.1007/s001450010003
23	MICCIANCIO D, PEIKERT C. Trapdoors for lattices: simpler, tighter, faster, smaller[C]//Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer, 2012: 700-718.
24	MICCIANCIO D, REGEV O. Lattice-based cryptogram-phy[M]//Post-quantum cryptography. Berlin, Germany: Springer, 2009: 147-191.
25	SHANG T , LEI Q , LIU J W . Quantum random oracle model for quantum digital signature. Physical Review, A, 2016, 94 (4): 042314. doi: 10.1103/PhysRevA.94.042314
26	YAMAKAWA T, ZHANDRY M. Classical vs quantum random oracles[C]//Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer, 2021: 568-597.

[1]	LI Rui, WEN Minhua, FAN Yin, XU Dongyang, ZHANG Zhanbing, LIN Xinhua. Rejection Sampling-based Multi-start Algorithms for Global Optimization [J]. Computer Engineering, 2025, 51(10): 150-159.
[2]	Douwei LEI, Debiao HE, Min LUO, Cong PENG. High-speed Parallel Implementation of Lattice-based Cryptography Based on AVX512 [J]. Computer Engineering, 2024, 50(2): 15-24.
[3]	CHEN Hong, HOU Yuting, GUO Pengfei, ZHOU Mo, ZHAO Jufang, XIAO Chenglong. Efficient Certificateless Aggregate Signcryption Scheme with Public Verifiability [J]. Computer Engineering, 2022, 48(10): 146-157.
[4]	DOU Fengge, CAO Suzhen, MA Jiajia, DING Xiaohui, WANG Caifen. Multi-Server Multi-Keyword Searchable Encryption Scheme for Designated User [J]. Computer Engineering, 2021, 47(11): 144-149,157.
[5]	ZHAO Zongqu, HUANG Lijuan, FAN Tao, MA Shaoti. KEM-based Authenticated Key Exchange Protocol on Lattice [J]. Computer Engineering, 2020, 46(7): 122-128.
[6]	NIU Shufen, LI Wenting, WANG Caifen. Partially Blind Proxy Re-Signature Scheme Without Bilinear Pairing [J]. Computer Engineering, 2020, 46(5): 187-192.
[7]	WANG Caifen,ZHAO Bing,LIU Chao,CHENG Yudan,XU Qinbai. Multiple to One Fully Homomorphic Encryption Algorithm Based on Integer Polynomial Ring [J]. Computer Engineering, 2019, 45(4): 130-135.
[8]	ZHU Minhui,CHEN Yanli,HU Yuanyuan. Identity-based Searchable Encryption Scheme Supporting Proxy Re-encryption [J]. Computer Engineering, 2019, 45(1): 129-135,140.
[9]	CHEN Huiyan,LIU Le,ZHANG Chenchen. An Identity-based Signature Scheme with CDH Problem Security [J]. Computer Engineering, 2018, 44(4): 174-180.
[10]	CAO Suzhen,DAI Wenjie,SUN Han,WANG Xiuya. A New Certificateless Aggregate Signature Scheme [J]. Computer Engineering, 2017, 43(8): 184-187.
[11]	ZHU Jun,CHEN Linlin,ZHU Xian,XIE Ling,WEI Wei. Certificateless Proxy Re-encryption Scheme for Cloud Computing Security [J]. Computer Engineering, 2017, 43(8): 8-14.
[12]	ZUO Liming,ZHANG Tingting,GUO Hongli,CHEN Zuosong. Certificateless Aggregate Signature Scheme Based on No Pairing Mapping [J]. Computer Engineering, 2017, 43(5): 313-316.
[13]	HUANG Rufen,HUANG Zhenjie,CHEN Qunshan,NONG Qiang. Short Proxy Signature Scheme with Provable Security [J]. Computer Engineering, 2017, 43(12): 255-260,266.
[14]	DU Ruiying,ZHOU Zhenyu,Milan Heinayati. Non-interactive Key Exchange Protocol for Space DTN [J]. Computer Engineering, 2016, 42(4): 137-142.
[15]	WANG Caifen,KANG Burong. An ID-based Server-aided Verification Signcryption Scheme [J]. Computer Engineering, 2016, 42(12): 139-144.

Please choose a citation manager

Content to export