Toward a Secure Fixed-Point Implementation of the Falcon Signature Scheme

Falcon was selected by NIST in 2022 for standardization as a post-quantum digital signature scheme. Among all standardized signature schemes, Falcon achieves the smallest signature size. Its main drawback, however, is its reliance on floating-point arithmetic, which plays a critical role in the security analysis. This reliance poses significant challenges for practical implementations: some platforms lack floating-point units, floating-point division is not constant time on many processors, and protecting floating-point computations against side-channel attacks using masking techniques is particularly difficult on embedded devices.

To address portability issues, Pornin (ePrint 2019/893) proposed an implementation of that emulates floating-point arithmetic using integer operations. While it enables deployment on a wider range of platforms, this approach incurs a substantial performance penalty compared to the native floating-point implementation.

This work studies the theory and practice of implementing Falcon's signing procedure in fixed-point arithmetic. This requires a specific analysis of the boundedness and precision of intermediate variables.

1. Our boundedness analysis revolves around a key fact: almost every intermediate variable arising during key expansion and signing is bounded by a function of four quantities that can be computed at key generation time. Our modified key generation enforces thresholds on these quantities through a light rejection step that rejects less than 50% of initial Falcon keys. This then yields sharp, unconditional bounds on all fixed-point variables. Establishing these bounds is highly nontrivial, and relies on Gaussian concentration arguments as well as on symplectic pairs, a generalization of symplecticity.

2. Our precision analysis remains, for now, partly empirical. Following a Rényi divergence argument, our main theorem proves the security of fixed-point Falcon conditioned on error bounds of certain intermediate values. These error bounds are derived empirically based on extensive experiments.

We provide a C fixed-point implementation. It is approximately a factor of two slower than the original floating-point implementation, but achieves a speedup of an order of magnitude compared to emulated floating-point implementations.