We present cryptanalysis of the inhomogenous short integer solution (ISIS) problem for anomalously small moduli 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 versions of the lattice signature scheme FALCON and its variant MITAKA.
For one small parametrisation of FALCON we reduce the estimated security against signature forgery by approximately 26 bits. For one small parametrisation of MITAKA we successfully forge a signature in seconds.
We also show that our attack applies to the ``distortion'' technique suggested in [Espitau–Tibouchi–Wallet–Yu, CRYPTO 2022].
I am currently a postdoctoral researcher at Centrum Wiskunde en Informatica (CWI) with Léo Ducas focussing on constructions from and cryptanalysis of lattice based cryptography. I will start as a junior lecturer at King's College London in January.