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 \textrm{ mod } q$.
• Signing: consider a message msg, it outputs a signature :
  1. Key expansion: process sk in order to compute an expanded key (this can be done once per key and cached).
  2. Hash: compute $c = H(msg || salt)$, where salt is randomly generated.
  3. Sample: compute a short vector $s = (s1, s2)$ such that $s1 + s2 \cdot h = c$.
• Verification: given a signature, it checks that (i) $s$ is short, (ii) $s1 + s2 \cdot 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?

Fixed-point arithmetic

Fixed-point arithmetic approximates real numbers with scaled integers. Throughout this section, we illustrate this idea using decimal numbers. However real-life implementations will use binary numbers. In fixed-point arithmetic, a value $x_0$ is approximated by some $x = v \cdot 10^{-f}$, where $v$ is stored as a $k$-digit integer and $f$ is a compile-time constant. For example, $\pi \approx 3.14159265\ldots$ can be approximated by $x = 314159265\cdot 10^{-8}$. We say that $f$ is the number of fractional digits, and $10^{-f}$ is the scaling factor. The choice of the scaling factor can thus be seen as allocating $f$ digits for the fractional part and $(k – f)$ digits for the integer part.

We need to avoid two pitfalls. Underflow happens when too many digits are budgeted for the integer part, leading to an unnecessary loss of precision. Overflow happens when not enough digits are budgeted for the integer part, leading to catastrophically incorrect results .

Arithmetic in fixed-point is much simpler than in floating-point. Addition is just integer addition, and multiplication is word-doubling multiplication, followed by dropping the least significant digits. In contrast, emulated floating-point operations can be highly complex to implement, see Pornin’s implementation. Some operations, such as multiplication, may change the scaling factor. We call “Type 1” implementations that force all variables to share a common scaling factor, and “Type 2” those that allow a per-variable scaling factor. Type 1 is simpler, while Type 2 can be more efficient.

All the concepts discussed above are illustrated in this interactive widget.

Division and square root, both of which are needed in Falcon’s key expansion, are more delicate operations. In both cases, we rely on the Newton-Raphson method which, for concision, we only illustrate for the division. The idea is to take $y_0$ to be a coarse approximation of $1/x$, then to iterate the formula $y_{n+1} ← y_n \cdot (2 − x \cdot y_n)$, which is easily evaluated as it contains one subtraction and two multiplications. Because each iteration roughly doubles the number of correct digits, this only requires a few iterations, in practice five or six for Falcon. This method is illustrated in the interactive widget below.

Our modifications to Falcon

Now, our goal is to implement Falcon in fixed-point. The key generation of Falcon generates a private key $sk = (f, g, F, G)$ and a public key $h = g / f \textrm{ mod } q$. It is crucial to provably bound all intermediate variables during signing, in order to avoid overflow in fixed-point arithmetic. Our main insight is the following statement:

Every single intermediate variable during signing is upper bounded by some function of $sk$.

Due to the complex and mathematically involved nature of Falcon, proving this statement in a formal manner ended up being a highly technical task. Here are two challenges we solved:

• Key expansion computes inversions $1/x$. These additionally require a lower bound on the input $x$. We leverage a geometric property of the lattices used in Falcon, called symplecticity. In our context, symplecticity allows us to convert upper bounds into lower bounds. Furthermore, it allows us to store only half of the expanded key, as explained in a 2022 paper by Sun et al.
• Each intermediate variable of the signing can be expressed as the projection of a discrete Gaussian on an affine line. These values are then easily bounded using  well-known concentration bounds.

In the end, we determine that four easily-computable values ${\norm{\mathrm{FFT}(f,g)}}_\infty$, ${\norm{\mathrm{FFT}(F,G)}}_\infty$, $\alpha_{\textrm{hybrid}}$ and ${\norm{\textrm{FFT}(k)}}_\infty$ control the magnitude of every intermediate variable in a rather tight manner.

We therefore propose a simple tweak on Falcon: during key generation, these four values are checked against threshold values $\gamma_{f,g}$, $\gamma_{F,G}$, $\gamma_{\textrm{hybrid}}$, and $\gamma_{\textrm{root}}$, as illustrated below. This provides unconditional bounds on the intermediate variables manipulated during signing. In turn, this allows us to set tight individual scaling factors with no risk of overflow. Concretely, by rejecting less than 50% of the admissible keys, we ensure that each intermediate variable is bounded by 2²¹. Since 21<32, a global format 32.64 is perfectly suitable for a fixed-point implementation.

Implementation

We provide two proof-of-concept implementations: 

• A Type 1 C implementation. We use the format 64.64, meaning that 64 bits are reserved for the integer part and as many for the fractional part. This implementation performs signing about 7 times faster than the emulated floating-point version.
• A Type 2 Python implementation. The specification is a bit more involved (we need our multiplications to have an additional parameter to specify the final shift), but all fixed-point variables hold in 64 bits.

We provide implementation timings here on an x86-64 commodity laptop, using the native floating-point implementation as a baseline. Note that a type 2 implementation would offer even better speed.

Let us note that it is significantly simpler to implement fixed-point implementations compared to emulated floating-point implementations. For example, here is the code for addition in emulated floating-point, whereas fixed-point addition is simply integer addition.

What now?

Our paper and proof-of-concept implementations demonstrate that Falcon can be implemented in fixed-point arithmetic efficiently, and without degrading security. Perhaps surprisingly, this requires only minimal changes to the scheme itself.

We believe this can benefit the upcoming FN-DSA standard. All the tweaks involved are simple: the four bound checks presented above, and some other minor tweaks appearing in prior work and recalled in our paper. If NIST decides to incorporate our tweaks into the FN-DSA specification, a fixed-point FN-DSA could be specified with little effort, making it deployable on devices without a floating-point unit. Fixed-point arithmetic is also more amenable to the specification and validation of KATs, as hardware floating-point has a weaker determinism.

The paper is available on IACR ePrint, and both implementations are on GitHub.