Paper 2025/1841

Fast Post-Quantum Ring Signature from Power Residue PRFs with QROM Security

Abstract

Ring signatures enable a user to sign anonymously on behalf of a group, providing a fundamental building block for privacy-preserving applications such as anonymous credentials and private transactions. Existing post-quantum constructions, however, face a persistent tension between efficiency and rigorous quantum security: practical schemes are typically analysed only in the classical random oracle model (ROM), whereas schemes with proofs in the quantum random oracle model (QROM) either incur multi-megabyte signatures, lack implementations, or rely on reductions too loose to support concrete parameter selection. We present PegaRing, the first post-quantum ring signature to combine practical performance with concretely parameterised security in QROM. At the 128-bit security level and a ring size of 1024, PegaRing produces 28KB signatures, reducing signature size by a factor of 88 relative to the smallest prior concretely parameterised QROM-secure construction. Our implementation signs in 4.325 ms and verifies in 3.074 ms. Compared with the state-of-the-art VOLE-in-the-head ring signature, which is proven secure only in classical ROM, PegaRing reduces signing and verification latency by factors of 2.65 and 3.80, respectively, while providing security in QROM. Finally, when using the first message-dependent Fiat-Shamir challenge as the boundary between offline and online computation, PegaRing's online signing phase takes 0.018 ms, compared with 7.611 ms for VOLE-in-the-head construction, achieving a reduction of more than 400 times. These results substantially narrow the gap between rigorous quantum security and practical performance for post-quantum ring signatures and make QROM-secure anonymous authentication feasible for various anonymity sets.

Note: Major Revision. This version updates the key contribution of the paper and revised analysis of beta-approximate PRF relation with respect to arithmetic progression list. We also updated the implementation and experiment results.