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

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.