Paper 2026/293

Quantum Oracle Distribution Switching and Applications to Falcon and Ring Signatures

Abstract

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.

Note: Update 1: Slightly reformulated the impossibility result for the Rényi divergence (Theorem 4) and improved the proof presentation; Added QROM handling of Falcon; Revised tightness discussion for oracle switching with statistical distance. The other changes are editorial or originate from restructuring the presentation of this work.