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 s.

doi.org/10.1007/978-3-031-38548-3_6
Lecture Notes in Computer Science
A Reduction Theory for Codes and Lattices in Cryptography
43rd Annual International Cryptology Conference, CRYPTO 2023

Ducas, L., Espitau, T., & Postlethwaite, E. W. (2023). Finding short integer solutions when the modulus Is small. In Advances in Cryptology (pp. 150–176). doi:10.1007/978-3-031-38548-3_6