International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Finding short integer solutions when the modulus is small

Authors:
Léo Ducas , CWI
Thomas Espitau , PQShield
Eamonn Postlethwaite , CWI
Download:
DOI: 10.1007/978-3-031-38548-3_6 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
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.
BibTeX
@inproceedings{crypto-2023-33177,
  title={Finding short integer solutions when the modulus is small},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-38548-3_6},
  author={Léo Ducas and Thomas Espitau and Eamonn Postlethwaite},
  year=2023
}