(2026-01) Revisiting the Concrete Security of Falcon-type Signatures
2026-01-21
Falcon is a selected signature scheme in the NIST post-quantum standardization. It is an efficient instantiation of the GPV framework over NTRU lattices. While the GPV framework comes with an elegant security proof in theory, Falcon had no formal proof involving concrete parameters for a long time. Until recently, Fouque et al. initiate the concrete security analysis of Falcon-type signatures. They give a formal proof of Falcon+, a minor modification of Falcon, in the random oracle model, whereas they claim that Falcon+-512 barely achieves the claimed 120-bit security for plain unforgeability. % and neither Falcon+-512 nor Falcon+-1024 offer strong unforgeability. Furthermore, they show that standard reductions for strong unforgeability are vacuous for Falcon parameters, necessitating the introduction of a new, non-standard assumption.
In this work, we revisit the concrete security analysis of Falcon-type signatures and present positive results. We develop improved analytic tools by leveraging the profile of the NTRU trapdoor bases. This eliminates the security loss for both Falcon+-512 and Falcon+-1024 in the case of plain unforgeability. We also apply our new analysis to the recent weak-smoothness variant Falcon-ws (Zhang et al. Asiacrypt 2025) that admits smaller parameters than Falcon under a non-standard assumption. As a result, we propose new parameters for Falcon-ws allowing for provable security under standard assumptions and signature size 17.8% (resp. 12.8%) smaller than that of Falcon-512 (resp. Falcon-1024) simultaneously. Moreover, we give a refined strong unforgeability security proof by replacing the worst-case analysis with a probabilistic analysis, which leads to a substantial increase in concrete security. Based on this, we show that by using a tighter Gaussian sampler, e.g. the one in Falcon-ws, Falcon-type signatures can achieve concrete security for strong unforgeability closely consistent with the claimed security level while keeping the compact size.