Paper 2026/2170

Swing the Lure: How to Cheaply Mitigate Sign Leakage in Falcon

Abstract

Falcon is one of the three post-quantum signature schemes selected by NIST for standardization so far. It is efficient and has particularly short signatures, but has the drawback of being difficult to implement correctly and securely, owing to its use of floating point arithmetic and secret-dependent lattice Gaussian sampling. In particular, obtaining implementations of Falcon that are protected against side-channel attacks seems to be a tremendous challenge that has no satisfactory solution so far. While it is theoretically possible to rely on generic countermeasures like masking, they are likely so costly as to be effectively inapplicable. And yet, side-channels are an actual threat to Falcon: a number of them have been demonstrated against various parts of the signing algorithm, including floating point operations and Gaussian sampling. Multiple power analysis attacks in fact achieve full key recovery from very realistic numbers of traces. This is especially the case for a series of side-channel attacks that can be broadly categorized as based on “sign leakage” within a specific part of the one-dimensional Gaussian sampler. In this paper, we take a closer look at this class of side-channel attacks, and obtain yet another one of a somewhat different flavor: while it also targets the sign of a variable in the one-dimensional Gaussian sampler, that variable is the input center, and in particular does not depend on the sampling randomness, making previously proposed mitigations modifying the base sampler ineffective. Furthermore, we propose, analyze and experimentally validate a novel, inexpensive countermeasure to protect Falcon against this class of side channel attacks. The idea, taking inspiration from shuffling, is to twist the target vector by random roots of unity in every recursive call of the fast Fourier sampling algorithm: this averages away the sign leakage efficiently. While this mitigation technique is heuristic and does not offer the provable guarantees of masking, it significantly enhances the physical security of Falcon fairly cheaply. In particular, it provides a more robust and more widely applicable protection than the countermeasure of Lin et al. (PKC 2025) at a much lower cost (incurring a 1.4-fold overhead in signing in dynamic mode and 2-fold in tree mode, compared to 3.5-fold and 6.8-fold for Lin et al. respectively). To the best of our knowledge, this is the first shuffling countermeasure proposed for Falcon.