Paper 2025/1841

Pegasus and PegaRing: Efficient (Ring) Signatures from Sigma-Protocols for Power Residue PRFs with (Q)ROM Security

Abstract

In this work, we present a novel commit-and-open $\Sigma$-protocol based on the power residue PRFs. Our construction leverages the oblivious linear evaluation (OLE) correlations inherent in PRF evaluations and requires only black-box access to a tree-PRG-based vector commitment. By applying the standard Fiat-Shamir transform, we obtain a post-quantum signature scheme, Pegasus, which improves upon the prior power residue PRFs based signature scheme PorcRoast (PQCrypto 2020) across all key metrics. In particular, Pegasus requires only a three-move interaction between the prover and verifier, compared to seven moves in PorcRoast. For the same power residue PRF, we reduce the signature size by 426 to 928 bytes, and in the fast parameter variant, our public key is eight times shorter than that in PorcRoast. Moreover, the signing and verification time of Pegasus are comparable to, or slightly faster than those of PorcRoast. Finally, we also provide security proof of Pegasus in the quantum random oracle model (QROM), addressing a limitation of all prior PRF-based signatures. We further develop a ring signature scheme, PegaRing, that preserves the three-move commit-and-open structure of Pegasus. Compared to previous PRF-based ring signature called DualRing-PRF (ACISP 2024), PegaRing reduces the constant communication overhead by more than half and achieves significantly faster signing and verification. We prove the security of PegaRing in both the random oracle model and the quantum random oracle model. To the best of our knowledge, PegaRing is the first post-quantum ring signature based on symmetric-key primitives that simultaneously achieves practical performance and provable security in the QROM.

Note: Extended the Range of Parameter Choices