The Rényi divergence is a measure of closeness of two probabilitydistributions. We show that it can often be used as an alternativeto the statistical distance in security proofs for lattice-based cryptography.Using the Rényi divergence is particularly suited for security proofsof primitives in which the attacker is required to solve a search problem(e.g., forging a signature).We show that it may also be used in the case ofdistinguishing problems (e.g., semantic security of encryption schemes),when they enjoy a public sampleability property. The techniques lead tosecurity proofs for schemes with smaller parameters, and sometimes tosimpler security proofs than the existing ones.
Motivated by digital signature algorithms ranging from Falcon to fully-anonymous ring signatures used in Signal-style key exchange, such as Gandalf, we revisit a fundamental problem in post-quantum security proofs: distinguishing oracle functions whose outputs are sampled independently from distributions
P and
Q that are close. In the context of signatures, closeness is often measured via Rényi divergences, which yield multiplicative bounds in the classical setting. A counterexample shows that such multiplicative-error bounds for distinguishers with classical oracle access have no analogue for quantum access, and we provide two alternative approaches based on small-range distributions and reprogramming techniques. We also give a concrete, optimal bound for the case where
P and
Q are close in statistical distance. We apply these techniques to the motivating constructions. (i) We give the first QROM security proof for Falcon that avoids oracle indistinguishability arguments based on statistical distance. This is crucial, as Falcon's ROM proof relies on Rényi divergence, while the statistical distance induced by its parameters is too large to yield meaningful bounds. (ii) We formalize and abstract the ring signature construction used in Gandalf as a modular framework by defining ring trapdoor preimage-sampleable functions (RPSFs), for which we obtain two QROM proofs. We also provide two QROM security proofs for AOS ring signatures, adapting existing QROM techniques. Together with our results on RPSF-based ring signatures, this yields QROM security proofs for a broad class of fully-anonymous linear ring signature constructions, including Gandalf and the AOS-based constructions Erebor and MayoRS.