Mehdi Tibouchi

FrodoKEM, a key encapsulation mechanism based on the standard (unstructured) LWE assumption, is recommended as a conservative choice for post-quantum key exchange by agencies like BSI and ANSSI. As such, it has garnered substantial attention from an implementation security standpoint. In particular, several papers have looked into masking FrodoKEM, and, like for various other lattice-based cryptosystems, identified the Gaussian sampling operation as a major bottleneck. In FrodoKEM, it is carried out using a CDT-based sampler, which compares a uniformly random value in [0, 1) (with fixed precision) to each of the probabilities in the cumulative distribution table of the target distribution.Two recent works proposed masked gadgets at arbitrary order for that operation: one by Gérard and Guerreau (CASCADE 2026), which simply masks each of the comparisons with the table elements (using a ripple carry adder as the Boolean comparison circuit), and another by Eid et al. (TCHES 2026), that uses a novel approach based on a binary search tree, significantly reducing the number of masked comparisons for larger tables. Eid et al. also choose the Kogge–Stone adder as the basis for their comparison circuit.In this paper, we provide an extensive analysis of the choices and trade-offs involved in masked CDT-based sampling, and propose several optimizations that further improve upon these previous works by a considerable margin. In particular, since FrodoKEM, like almost all the schemes that rely Gaussian sampling, generates hundreds of samples at a time, we find it beneficial to utilize approaches that lend themselves to a high degree of parallelization. This includes bitslicing (with which, importantly, the ripple carry adder has been proved optimal for comparisons), as well as techniques such as the use of algebraic normal form in masked multiplexers.As a result, on an ARM Cortex-M4 STM32F4 target board, our companion implementation in pure C outperforms the hand-crafted assembly of Eid et al. (resp. Gérard–Guerreau) by a factor of around 2 (resp. 7 to 9) at masking order 1. The gap is even larger at higher order: we outperform the higher-order code of Eid et al. (in C with assembly for expensive gadgets) by a factor ranging from 5 at masking order 2 to 9 as masking order 8.

Gentry’s original blueprint for the construction of fully homomorphic encryption (FHE) starts from a somewhat homomorphic encryption scheme, that supports the homomorphic evaluation of arithmetic circuits of moderate multiplicative depth up to L, and whose decryption circuit itself can furthermore be “squashed” to a multiplicative depth less than L. Then, the homomorphic evaluation of this squashed decryption circuit, called bootstrapping, transforms any ciphertext into a ciphertext supporting at least one extra level of multiplication, enabling the homomorphic evaluation of arbitrary arithmetic circuits. Bootstrapping is the cornerstone of Gentry’s breakthrough. Unfortunately, it introduces substantial overhead that limits the efficiency of most FHE schemes so far. Consequently, numerous attempts have been made to circumvent the bottleneck of bootstrapping by directly constructing encryption schemes that support the evaluation of circuits of unbounded depth, e.g., by avoiding ciphertext noise, the randomness present in Gentry-like somewhat homomorphic schemes that grows after each homomorphic multiplication. Noise effectively limits the depths of supported circuits, as ciphertexts fail to correctly decrypt when noise size exceeds a certain threshold. Most attempts to achieve noiseless FHE schemes have proved insecure, however. In this paper, we take a closer look at a recent construction along those lines due to Zheng et al.’s unbounded FHE scheme, and show that it is no exception. We show that it is susceptible to an efficient full key recovery attack, and moreover that ciphertexts can be decrypted faster with the public parameters alone than the time it takes to generate the public key.