Paper 2023/1125

Finding short integer solutions when the modulus is small

Léo Ducas, Centrum Wiskunde & Informatica, Mathematical Institute, Leiden University
Thomas Espitau, PQShield, France
Eamonn W. Postlethwaite, Centrum Wiskunde & Informatica
Abstract

We present cryptanalysis of the inhomogenous short integer solution (ISIS) problem for anomalously small moduli \(q\) by exploiting the geometry of BKZ reduced bases of $q$-ary lattices. We apply this cryptanalysis to examples from the literature where taking such small moduli has been suggested. A recent work [Espitau–Tibouchi–Wallet–Yu, CRYPTO 2022] suggests small \(q\) versions of the lattice signature scheme FALCON and its variant MITAKA. For one small \(q\) parametrisation of FALCON we reduce the estimated security against signature forgery by approximately 26 bits. For one small \(q\) parametrisation of MITAKA we successfully forge a signature in $15$ seconds.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published by the IACR in CRYPTO 2023
Contact author(s)
ducas @ cwi nl
t espitau @ gmail com
ewp @ cwi nl
History
2023-07-24: approved
2023-07-19: received
See all versions
Short URL
https://ia.cr/2023/1125
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2023/1125,
      author = {Léo Ducas and Thomas Espitau and Eamonn W. Postlethwaite},
      title = {Finding short integer solutions when the modulus is small},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1125},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1125}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.