Paper 2024/553

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

Abstract

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 $$, our framework requires an SoK of the NP statement with size $$. 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 $$. By comparison, existing post-quantum ring signatures, regardless of linkability considerations, have signature sizes of $$ 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 $$. 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 $$. In our experiment, at $$-bit security and ring size of $$, our LRS has a size of $$KB, and an amortized verification cost of $$ ms, surpassing the state-of-the-art by a significant margin. Even without considering amortization, the verification time for a single signature is $$ 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 ($$ bytes), while public keys of existing constructions are in the order of kilobytes.