Paper 2025/1174
Efficient Constant-Size Linkable Ring Signatures for Ad-Hoc Rings via Pairing-Based Set Membership Arguments
, Harbin Institute of Technology, Shenzhen, Harbin Institute of Technology, Shenzhen, The Hong Kong Polytechnic University, Jinan University, Harbin Institute of Technology, Shenzhen, Guangdong Key Laboratory of New Security and Intelligence Technology, Harbin Institute of Technology, Shenzhen, Guangdong Key Laboratory of New Security and Intelligence TechnologyAbstract
Linkable Ring Signatures (LRS) allow users to anonymously sign messages on behalf of ad-hoc rings, while ensuring that multiple signatures from the same user can be linked. This feature makes LRS widely used in privacy-preserving applications like e-voting and e-cash. To scale to systems with large user groups, efficient schemes with short signatures and fast verification are essential. Recent works, such as DualDory (ESORICS’22) and LLRing (ESORICS’24), improve verification efficiency through offline precomputations but rely on static rings, limiting their applicability in ad-hoc ring scenarios. Similarly, constant-size ring signature schemes based on accumulators face the same limitation. In this paper, we propose a framework for constructing constant-size LRS suitable for large ad-hoc rings. We introduce a novel pairing-based Set Membership Argument (SMA) with a proof size of only three group elements. By leveraging KZG polynomial commitments, we optimize the verification to require only constant group exponentiations and pairings, as well as linear field multiplications. Utilizing the SMA, our framework achieves constant-size signatures with verification dominated by linear field operations, outperforming existing schemes that require linear group exponentiations in ad-hoc ring settings. Moreover, it exhibits strong scalability: (i) compatibility with any PKI-based cryptosystem and (ii) scoped linkability, enabling flexible definitions of linking scope. We instantiate our framework using a discrete logarithm public key structure. On the $BN254$ curve, our signature size is fixed at 687 bytes, which to our best knowledge is the shortest LRS for ring sizes larger than 32. For a ring size of 1024, our verification cost is only 10.4 ms, achieving 48.6×, 2.6×–467×, 7.9×–13.2×, and 2.2×–102.5× improvements over Omniring (CCS’19), DualDory (with and without precomputation), LLRing-DL (with and without precomputation), and LLRing-P (with and without precomputation), respectively. Moreover, this performance gap continues to grow as the ring size increases.
Note: This is the full version of the paper accepted to ACM CCS 2025.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Major revision. ACM CCS 2025
- DOI
- 10.1145/3719027.3744830
- Keywords
- Linkable Ring SignaturesAd-hoc RingsSet Membership ArgumentsBlockchain
- Contact author(s)
-
minxie @ stu hit edu cn
23S051021 @ stu hit edu cn
man-ho-allen au @ polyu edu hk
tjunbinfang @ jnu edu cn
wangxuan @ cs hitsz edu cn
zoeljiang @ hit edu cn - History
- 2025-11-24: last of 2 revisions
- 2025-06-20: received
- See all versions
- Short URL
- https://ia.cr/2025/1174
- License
-
CC BY-NC-ND
BibTeX
@misc{cryptoeprint:2025/1174,
author = {Min Xie and Zhengzhou Tu and Man Ho Au and Junbin Fang and Xuan Wang and Zoe Lin Jiang},
title = {Efficient Constant-Size Linkable Ring Signatures for Ad-Hoc Rings via Pairing-Based Set Membership Arguments},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1174},
year = {2025},
doi = {10.1145/3719027.3744830},
url = {https://eprint.iacr.org/2025/1174}
}
