Paper 2024/353

FuLeakage: Breaking FuLeeca by Learning Attacks

Felicitas Hörmann, German Aerospace Center (DLR), University of St. Gallen
Wessel van Woerden, Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest Research Centre

FuLeeca is a signature scheme submitted to the recent NIST call for additional signatures. It is an efficient hash-and-sign scheme based on quasi-cyclic codes in the Lee metric and resembles the lattice-based signature Falcon. FuLeeca proposes a so-called concentration step within the signing procedure to avoid leakage of secret-key information from the signatures. However, FuLeeca is still vulnerable to learning attacks, which were first observed for lattice-based schemes. We present three full key-recovery attacks by exploiting the proximity of the code-based FuLeeca scheme to lattice-based primitives. More precisely, we use a few signatures to extract an $n/2$-dimensional circulant sublattice from the given length-$n$ code, that still contains the exceptionally short secret-key vector. This significantly reduces the classical attack cost and, in addition, leads to a full key recovery in quantum-polynomial time. Furthermore, we exploit a bias in the concentration procedure to classically recover the full key for any security level with at most 175,000 signatures in less than an hour.

Available format(s)
Attacks and cryptanalysis
Publication info
Published by the IACR in CRYPTO 2024
learning attackFuLeecaLee metriclattice reductionquantum attack
Contact author(s)
felicitas hoermann @ dlr de
wessel van-woerden @ math u-bordeaux fr
2024-06-04: revised
2024-02-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Felicitas Hörmann and Wessel van Woerden},
      title = {{FuLeakage}: Breaking {FuLeeca} by Learning Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2024/353},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.