Finding short integer solutions when the modulus is small

ePrint Report: Finding short integer solutions when the modulus is small

Léo Ducas, Thomas Espitau, Eamonn W. Postlethwaite

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 …

cryptanalysis eprint report exploiting geometry integer isis problem report solution solutions thomas