Welcome to the resource topic for 2024/553
Title:
Efficient Linkable Ring Signatures: New Framework and Post-Quantum Instantiations
Authors: Yuxi Xue, Xingye Lu, Man Ho Au, Chengru Zhang
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 n, our framework requires a 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 inherents the post-quantum security 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 ring signatures for any 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, which is still 10x better than state-of-the-art succinct construction, marking it comparable to those featuring linear signature size. A similar performance advantage can also be seen at signing.
ePrint: https://eprint.iacr.org/2024/553
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .