Paper 2024/353
FuLeakage: Breaking FuLeeca by Learning Attacks
Abstract
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 of 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.
Metadata
- Available format(s)
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- learning attackFuLeecaLee metriclattice reductionquantum attack
- Contact author(s)
-
felicitas hoermann @ dlr de
wessel van-woerden @ math u-bordeaux fr - History
- 2024-03-01: approved
- 2024-02-27: received
- See all versions
- Short URL
- https://ia.cr/2024/353
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/353, 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{https://eprint.iacr.org/2024/353}}, url = {https://eprint.iacr.org/2024/353} }