Finding Short Integer Solutions When the Modulus Is Small

Back
Categories: Research Papers
Date: 09/08/2023
Source: Crypto 2023
Authors: Thomas Espitau (PQShield), Léo Ducas, Eamonn W. Postlethwaite

Abstract

We present cryptanalysis of the inhomogenous short integer solution 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.