The signature scheme Falcon, selected for standardization as FN-DSA (future FIPS-206), offers a compact yet efficient alternative to ML-DSA. However, it suffers from one big Achilles’ heel: it relies heavily on floating-point arithmetic (FPA). The main way of performing FPA is via a dedicated hardware floating-point unit (FPU), but these are not always present on lower-end devices. Moreover, FPA offers more avenues for timing and side-channel leakage than plain integer arithmetic; this has been exploited in recent side-channel attacks against Falcon implementations. Alternatively, one may emulate FPA using integer arithmetic, but this is about 20 times slower than native FPA when doing so in constant-time.
In a paper at CRYPTO 2026 by PQShield and University of Rennes researchers, we propose a new implementation strategy for Falcon that sidesteps FPA. We achieve this by relying on a more robust and efficient type of arithmetic: fixed-point arithmetic.
Overview of Falcon
Falcon is built on the hash-and-sign paradigm. We highlight in orange all operations that currently rely on floating-point arithmetic.
- Key generation: the private key sk is a short tuple of polynomials (f,g,F,G), while the public key pk is the ratio h=g/f mod q.
- Signing: consider a message msg, it outputs a signature :
- Key expansion: process sk in order to compute an expanded key (this can be done once per key and cached).
- Hash: compute c=H(msg||salt), where salt is randomly generated.
- Sample: compute a short vector s=(s1,s2) such that s1+s2⋅h=c.
- Verification: given a signature, it checks that (i) s is short, (ii) s1+s2⋅h=c.
Implementing key generation in fixed point has already been done by Pornin. Verification uses only integer arithmetic, so it does not need a fixed-point implementation. For signing, we need to consider two steps. The Sample step involves multiplication and additions by real numbers, while the Key expansion also needs division and square-root operations. Let us understand how to implement those operations efficiently in fixed-point. However, first of all, let’s ask: what is fixed-point arithmetic?