CryptoDB
Finding short integer solutions when the modulus is small
NOTE: imports for ToSC and TCHES are no longer functioning.
Authors: |
|
---|---|
Download: |
|
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 }