Deniable Ring Signature Scheme Based on TUOV Digital Signature Algorithm

doi:10.3969/j.issn.1671-1122.2026.06.004

Abstract

Abstract:

Deniable ring signature is a signature scheme that allows ring members to confirm or deny their identity as the signer in the absence of a trusted third party. It effectively balances privacy protection and controllable supervision, and has broad application prospects. To improve and expand the multivariable post-quantum cryptosystem, this paper proposed a denial-of-service ring signature scheme based on the triangular unbalanced oil and vinegar (TUOV) digital signature algorithm, which achieved verifiability and deniability of signatures. Through formal proof, the security and effectiveness of the scheme in terms of correctness, unforgeability, anonymity, traceability, and non-defamation were verified. Furthermore, this paper conducted a comparative analysis with the reputation ring signature (RRS)scheme based on lattices and the Denial-of-Service ring signature scheme based on the Shangyong mima 2 (SM2) standard in terms of communication and computational overhead, demonstrating good practicality.

Key words: post-quantum cryptography, multivariate public key cryptography, TUOV digital signature algorithm, ring signature, deniable ring signature

CLC Number:

TP309

ZHANG Yanshuo, YAN Ziyang, LI Baiheng, CHEN Huiyan, LIU Bing. Deniable Ring Signature Scheme Based on TUOV Digital Signature Algorithm[J]. Netinfo Security, 2026, 26(6): 886-898.

Figures/Tables 5

References 15

[1]	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.
[2]	TAKURA K, NAKAMURA K. A Public-Key Cryptosystem Suitable for Digital Multi-Signatures[J]. NEC Research & Development, 1983(71): 1-8.
[3]	CHAUM D. Blind Signatures for Untraceable Payments[C]//Springer. Advances in Cryptology(CRYPTO’82). Heidelberg: Springer, 1983: 199-203.
[4]	CHAUM D, VAN HEYST E. Group Signatures[C]//IACR. Advances in Cryptology(EUROCRYPT’91). Heidelberg: Springer, 1991: 257-265.
[5]	RIVEST R L, SHAMIR A, TAUMAN Y. How to Leak a Secret[C]//IACR. Advances in Cryptology(ASIACRYPT) 2001. Heidelberg:Springer. 2001: 552-565.
[6]	YIN Hualei, FU Yao, LI Chenlong, et al. Experimental Quantum Secure Network with Digital Signatures and Encryption[J]. National Science Review, 2023, 10(4): nwac228.
[7]	NAOR M. Deniable Ring Authentication[C]//IACR. Advances in Cryptology(CRYPTO 2002). Heidelberg: Springer, 2002: 481-498.
[8]	KOMANO Y, OHTA K, SHIMBO A, et al. Toward the Fair Anonymous Signatures: Deniable Ring Signatures[C]//IACR. Advances in Cryptology(CT-RSA 2006). Heidelberg: Springer, 2006: 174-191.
[9]	SHOR P. Algorithms for Quantum Computation: Discrete Logarithms and Factoring[C]//IEEE. The 35th Annual Symposium on Foundations of Computer Science. New York: IEEE, 1994: 124-134.
[10]	DING Jintai, GONG Boru, GUO Hao, et al. TUOV: Triangular Unbalanced Oil and Vinegar Algorithm Specifications and Supporting Documentation[EB/OL]. (2023-01-01)[2025-11-21]. https://csrc.nist.gov/projects/pqc-dig-sig/round-1-additional-signatures
[11]	LIN Hao. Research on Post-Quantum Ring Signature Schemes[D]. Jinan: Shandong University, 2022.
	林昊. 后量子环签名方案的研究[D]. 济南: 山东大学, 2022.
[12]	BAO Zijian, HE Debiao, PENG Cong, et al. Deniable Ring Signature Based on SM2 Digital Signature Algorithm[J]. Journal of Cryptologic Research, 2023, 10(2): 264-275.
	包子健, 何德彪, 彭聪, 等. 基于SM2数字签名算法的可否认环签名[J]. 密码学报, 2023, 10(2):264-275.
[13]	BEULLENS W. Multivariate Blind Signatures Revisited[C]//IACR. Selected Areas in Cryptography(SAC 2024). Heidelberg: Springer, 2024: 230-236.
[14]	MOHAMED M S E, PETZOLDT A. RingRainbow: An Efficient Multivariate Ring Signature Scheme[C]//IACR. Progress in Cryptology(AFRICACRYPT 2017). Heidelberg: Springer, 2017: 3-20.
[15]	SAKUMOTO K, SHIRAI T, HIWATARI H. Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials[C]//IACR. Advances in Cryptology(CRYPTO 2011). Heidelberg: Springer, 2011: 706-723.

符号	定义
$\lambda $	安全参数
${{{F}}_{q}} $	q阶有限域
${F}_{q}^{n} $	${F}_{q}^{{}} $上的n维向量空间
B	${F}_{q}^{{}} $上的矩阵
$a,b,\cdots $	${F}_{q}^{{}} $上的列向量
${x}={{({{x}_{1}},\cdots,{{x}_{n}})}^{\text{T}}} $	默认情况下的列向量
$[n] $	集合{1,2,…,n}
${{{0}}_{k}} $	k维零向量
${{{I}}_{n}} $	n维单位矩阵
Setup	TUOV算法参数设置算法
KeyGen	密钥生成算法
Sign	签名算法
Verify	验证算法
PPT	Probabilistic Polynomial Time的缩写，表示概率多项式时间

方案	签名算法通信开销	确认算法通信开销	否认算法通信开销
本文方案	$kn\cdot {{\log }_{2}}q $	$2n+m+32 $	$2n+m+32 $
文献[11]方案	${{\lambda }^{3}}\cdot \text{lo}{{\text{g}}_{2}}k $	${{\lambda }^{3}}\cdot \text{lo}{{\text{g}}_{2}}k $	${{\lambda }^{3}}\cdot \text{lo}{{\text{g}}_{2}}k $
文献[12]方案	$\left( n+2 \right)\left\| p \right\|+\left\| G \right\| $	$3\left\| p \right\|+3\left\| G \right\| $	$4\left\| p \right\|+\left\| {z} \right\|+2\left\| G \right\| $

比特安全级别	性能指标	5个环成员	10个环成员	20个环成员	50个环成员
128位	参数 $(n,m,{{m}_{1}},q) $	(112,44, 22,256)	(112,44, 22,256)	(112,44, 22,256)	(112,44, 22,256)
	环组公钥尺寸/KB	208.05	416.09	832.19	2080.47
	签名尺寸/B	560	1120	2240	5600
192位	参数 $(n,m,{{m}_{1}},q) $	(184,72, 36,256)	(184,72, 36,256)	(184,72, 36,256)	(184,72, 36,256)
	环组公钥尺寸/KB	911.33	1822.66	3645.31	9113.28
	签名尺寸/B	920	1840	3680	9200
256位	参数 $(n,m,{{m}_{1}},q) $	(244,96, 48,256)	(244,96, 48,256)	(244,96, 48,256)	(244,96, 48,256)
	环组公钥尺寸/KB	2160.07	4320.16	8640.31	21600.78
	签名尺寸/B	1220	2440	4880	12200

方案	具体算法	计算开销
本文方案	签名	$O({{n}^{3}})+O(2{{n}^{2}}) $
	验证	$O(k{{n}^{2}}) $
	确认 $({v}=1) $	$O({{n}^{2}}) $
	否认 $({v}=1) $	$O({{n}^{2}}) $
文献[11]方案	签名	$O({{n}^{2}}\text{lo}{{\text{g}}_{\text{2}}}q) $
	验证	$O({{n}^{2}}\text{lo}{{\text{g}}_{\text{2}}}q) $
	确认 $({v}=1) $	$O({{n}^{2}}\text{lo}{{\text{g}}_{\text{2}}}q) $
	否认 $({v}=1) $	$O({{n}^{2}}\text{lo}{{\text{g}}_{\text{2}}}q) $
文献[12]方案	签名	$O(n) $
	验证	$O(n) $
	确认 $({v}=1) $	$O(1) $
	否认 $({v}=1) $	$O(\text{lo}{{\text{g}}_{\text{2}}}q) $

比特安全级别	性能指标	5个环成员	10个环成员	20个环成员	50个环成员
128位	参数 $(n,m,{{m}_{1}},q) $	(112,44, 22,256)	(112,44, 22,256)	(112,44, 22,256)	(112,44, 22,256)
128位	计算开销（CPU周期数）	1998	3740	7225	17680
192位	参数 $(n,m,{{m}_{1}},q) $	(184,72, 36,256)	(184,72, 36,256)	(184,72, 36,256)	(184,72, 36,256)
192位	计算开销（CPU周期数）	6143	11400	21914	53456
256位	参数 $(n,m,{{m}_{1}},q) $	(244,96, 48,256)	(244,96, 48,256)	(244,96, 48,256)	(244,96, 48,256)
256位	计算开销（CPU周期数）	11175	20777	39981	97593