Paper 2026/1349

Sharper and Closed-Form Attacks on $\mathsf{SIS}$ When Modulus Is Small

Abstract

The Large Norm attacks of Ducas-Espitau-Postlethwaite (CRYPTO 2023) on the $\mathsf{ISIS}$ problem have shown that small values of $q$ can be used to recover short solutions. This was applied to Falcon and Mitaka. Two issues are left, however. First, the cost model of the attack oversimplifies the BDGL sieve; it does not account for how long vectors will be distributed and treats two dependent probabilistic events as if they were independent, which results in an overestimation of the attack cost. Secondly, the analysis only deals with the $\ell_2$ norm and has not yet been extended to $\mathsf{ISIS}^\infty$, which underlies Dilithium-type systems. This work addresses both issues. First, we extend the cost model of the Large Norm attack by including the principal sieve length distribution into our estimation of success probabilities. In addition, we use a joint probability rather than an approximate factor where possible. Since all other parts of the original $\theta$ convolution framework are reused, the extension is relatively minor. We reduce the attack cost of Large Norm on Falcon-256 by a $\approx\!11\times$ cheaper model, and successfully forge a Mitaka-512 signature in $\approx\!4.5$ seconds at a higher success rate. We additionally introduce a closed-form $\ell_\infty$ variant as a Z-shape attack against Dilithium-type $\mathsf{ISIS}^{\infty}$ at small-to-moderate modulus, which succeeds in $\le\!1.6$ seconds across three presets.