Paper 2024/553

Efficient Linkable Ring Signatures: New Framework and Post-Quantum Instantiations

Yuxi Xue, The Hong Kong Polytechnic University
Xingye Lu, The Hong Kong Polytechnic University
Man Ho Au, The Hong Kong Polytechnic University
Chengru Zhang, The University of Hong Kong

In this paper, we introduce a new framework for constructing linkable ring signatures (LRS). Our framework is based purely on signatures of knowledge (SoK) which allows one to issue signatures on behalf of any NP-statement using the corresponding witness. Our framework enjoys the following advantages: (1) the security of the resulting LRS depends only on the security of the underlying SoK; (2) the resulting LRS naturally supports online/offline signing (resp. verification), where the output of the offline signing (resp. verification) can be re-used across signatures of the same ring. For a ring size $n$, our framework requires an SoK of the NP statement with size $\log n$. To instantiate our framework, we adapt the well-known post-quantum secure non-interactive argument of knowledge (NIAoK), ethSTARK, into an SoK. This SoK is inherently post-quantum secure and has a signature size poly-logarithmic in the size of the NP statement. Thus, our resulting LRS has a signature size of $O(\text{polylog}(\log n))$. By comparison, existing post-quantum ring signatures, regardless of linkability considerations, have signature sizes of $O(\log n)$ at best. Furthermore, leveraging online/offline verification, part of the verification of signatures on the same ring can be shared, resulting in a state-of-the-art amortized verification cost of $O(\text{polylog}(\log n))$. Our LRS also performs favourably against existing schemes in practical scenarios. Concretely, our scheme has the smallest signature size among all post-quantum linkable ring signatures with non-slanderability for ring size larger than $32$. In our experiment, at $128$-bit security and ring size of $1024$, our LRS has a size of $29$KB, and an amortized verification cost of $0.3$ ms, surpassing the state-of-the-art by a significant margin. Even without considering amortization, the verification time for a single signature is $128$ ms, comparable to those featuring linear signature size. A similar performance advantage can also be seen at signing. Furthermore, our LRS has extremely short public keys ($32$ bytes), while public keys of existing constructions are in the order of kilobytes.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. ESORICS 2024
Linkable Ring Signaturespost-quantum cryptographysignature of knowledge
Contact author(s)
yuxi-ivy xue @ connect polyu hk
xing-ye lu @ polyu edu hk
mhaau @ polyu edu hk
u3008875 @ connect hku hk
2024-04-29: revised
2024-04-09: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      author = {Yuxi Xue and Xingye Lu and Man Ho Au and Chengru Zhang},
      title = {Efficient Linkable Ring Signatures: New Framework and Post-Quantum Instantiations},
      howpublished = {Cryptology ePrint Archive, Paper 2024/553},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.