Tighter Security Proof of Falcon \(^{+}\) in the Quantum Random Oracle Model
摘要
Falcon is a lattice-based (NTRU lattice) post-quantum digital signature scheme recently standardized by NIST, which follows the well-known full-domain-hash GPV framework and replaces the original statistical distance in GPV with Rényi divergence to measure the distribution closeness. In order to deal with the incompatibility between the GPV proof and the Rényi divergence based Falcon scheme, Gajland, Janneck and Kiltz [12] established that incorporating a carefully constrained set of modifications ( \(\textsc {Falcon} ^{+}\) ) to the scheme permits its first rigorous security proof via Rényi divergence analysis. However, the security guarantee of their scheme is currently established solely in the classical setting, while its resilience against quantum adversaries, specifically, the security proof of \(\textsc {Falcon} ^{+}\) in the quantum setting remains an unresolved problem. In this paper, we first find that a simple method that combines several existing techniques including evaluating the difference between quantum oracles in [6, Lemma 3], adaptive reprogramming [14, Theorem 1], and Pinsker’s inequality, can give a QROM proof for \(\textsc {Falcon} ^{+}\) . However, such a simple method will suffer a large reduction loss, which mainly comes from the usage of [6, Lemma 3]. In particular, [6, Lemma 3] gives the quantum oracle distinguishing advantage \( 4q^2\sqrt{\epsilon }\) . Thus, exploiting the distribution property of the quantum oracles satisfied by \(\textsc {Falcon} ^{+}\) , we improve such a distinguishing advantage to \(q\epsilon \) . Finally, we apply this improved distinguishing advantage to obtain a tighter QROM proof of \(\textsc {Falcon} ^{+}\) with Rényi divergence.