Search papers, labs, and topics across Lattice.
This paper presents four security reductions in the quantum-accessible random oracle model (QROM) for two generic ring signature constructions: two for the AOS framework and two for a construction paradigm based on ring trapdoors. The work addresses the need for post-quantum secure ring signatures, which are crucial for applications like deniable authenticated key exchange. The authors employ techniques like measure-and-reprogram, QROM straightline extraction, history-free reductions, and QROM reprogramming, and also analyze the behavior of quantum algorithms interacting with oracles having different output distributions, providing tight bounds for statistical distance.
Securing ring signatures against quantum attacks just got a boost: this work provides QROM security proofs for two generic constructions, paving the way for post-quantum deniable key exchange protocols.
Ring signatures are a powerful primitive that allows a member to sign on behalf of a group, without revealing their identity. Recently, ring signatures have received additional attention as an ingredient for post-quantum deniable authenticated key exchange, e.g., for a post-quantum version of the Signal protocol, employed by virtually all end-to-end-encrypted messenger services. While several ring signature constructions from post-quantum assumptions offer suitable security and efficiency for use in deniable key exchange, they are currently proven secure in the random oracle model (ROM) only, which is insufficient for post-quantum security. In this work, we provide four security reductions in the quantum-accessible random oracle model (QROM) for two generic ring signature constructions: two for the AOS framework and two for a construction paradigm based on ring trapdoors, whose generic backbone we formalize. The two security proofs for AOS ring signatures differ in their requirements on the underlying sigma protocol and their tightness. The two reductions for the ring-trapdoor-based ring signatures exhibit various differences in requirements and the security they provide. We employ the measure-and-reprogram technique, QROM straightline extraction tools based on the compressed oracle, history-free reductions and QROM reprogramming tools. To make use of R\'enyi divergence properties in the QROM, we study the behavior of quantum algorithms that interact with an oracle whose distribution is based on one of two different distributions over the set of outputs. We provide tight bounds for the statistical distance, show that the R\'enyi divergence can not be used to replace the entire oracle and provide a workaround.
