Cryptanalysis of the Falcon-M Signature Scheme
TL;DR
A rigorous security and correctness analysis on Falcon-M, a lightweight signature scheme, reveals that removing the NTRU trapdoor breaks the essential computational asymmetry, causing the verification equation to degenerate into a publicly solvable linear system.
Abstract
Symmetry is crucial in lattice cryptography, where secure signatures rely on structural invariants over polynomial rings. This paper conducts a rigorous security and correctness analysis on Falcon-M, a lightweight signature scheme. We first demonstrate a fundamental correctness failure through an explicit experimental instantiation of the scheme: because the signing algorithm is algebraically decoupled from the secret key, no honestly generated signature was accepted in our tested experiments. Furthermore, we reveal that removing the NTRU trapdoor breaks the essential computational asymmetry, causing the verification equation to degenerate into a publicly solvable linear system. Consequently, for invertible public keys, an adversary can execute a direct universal forgery attack purely from public data via pointwise algebraic inversion in the frequency domain with Onlogn time complexity. For non-invertible keys, we further identify a practical existential forgery utilizing a localized salt-search. Ultimately, these practical cryptanalytic results mathematically invalidate the claimed security under the analyzed instantiation.