Paper 2025/1375
Revisiting Linkable Ring Signatures with Logarithmic Verification Complexity
, National Technical University of Athens, Archimedes, Athena Research CenterAbstract
Ring Signatures allow a user to sign on behalf of an ad-hoc set of public keys, while hiding their identity inside that set. Linkable Ring Signatures (LRS) add the functionality of detecting signatures originating from the same signer. They have found many applications in anonymous transactions and e-voting. The LLRing family of linkable ring signature schemes by Hui and Chau (ESORICS 2024) is one of the more efficient LRS schemes. However, we show that it has an unlinkability vulnerability, meaning an adversary can create more unlinkable signatures than the number of secret keys they own. The vulnerability is caused by the introduction of unwanted structure to base elements used in proofs. We also find a similar attack against the Threshold Ring Referral (TRR) scheme of Ta, Hui, and Chau (Security and Privacy 2025), rendering it unsound. We show how to achieve strong linkability with logarithmic verification complexity in the pairing based setting by first reverting the unsafe construction of base elements, and by also adjusting the arguments of knowledge used in order to maintain efficiency. Concretely, by modifying the Dory argument to fit our scheme we are able to match the performance of LLRing-P. We separate the design and analysis of the scheme from the instantiation of the knowledge arguments, which helps prevent unwanted interactions between the two, and can provide easier upgrades to more efficient proof systems.
Note: Full version of PKC 2026 paper.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- A major revision of an IACR publication in PKC 2026
- DOI
- 10.1007/978-3-032-26737-5_17
- Keywords
- Linkable Ring SignaturesZero Knowledge ProtocolsDigital Signatures
- Contact author(s)
-
balla danai @ gmail com
pchaidos @ di uoa gr - History
- 2026-06-14: last of 3 revisions
- 2025-07-28: received
- See all versions
- Short URL
- https://ia.cr/2025/1375
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1375,
author = {Danai Balla and Pyrros Chaidos},
title = {Revisiting Linkable Ring Signatures with Logarithmic Verification Complexity},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1375},
year = {2025},
doi = {10.1007/978-3-032-26737-5_17},
url = {https://eprint.iacr.org/2025/1375}
}
