**SoK: On the Security of Cryptographic Problems from Linear Algebra**

*Carl Bootland and Wouter Castryck and Alan Szepieniec and Frederik Vercauteren*

**Abstract: **There are two main aims to this paper. Firstly, we survey the relevant existing attack strategies known to apply to the most commonly used lattice-based cryptographic problems as well as to a number of their variants. In particular, we consider attacks against problems in the style of LWE, SIS and NTRU defined over rings of the form $\mathbb{Z}[X]/(f(X), g(X))$, where classically $g(X) = q$ is an integer modulus. We also include attacks on variants which use only large integer arithmetic, corresponding to the degree one case $g(X) = X - c$. Secondly, for each of these approaches we investigate whether they can be generalised to the case of a polynomial modulus $g(X)$ having degree larger than one, thus addressing the security of the generalised cryptographic problems from linear algebra introduced by Bootland et al. We find that some attacks readily generalise to a wide range of parameters while others require very specific conditions to be met in order to work.

**Category / Keywords: **foundations / lattice-based cryptography, noisy linear algebra, learning with errors, short integer solutions, NTRU

**Date: **received 7 Oct 2021

**Contact author: **carl bootland at esat kuleuven be, wouter castryck at esat kuleuven be, alan at nervos org, frederik vercauteren at esat kuleuven be

**Available format(s): **PDF | BibTeX Citation

**Version: **20211012:061007 (All versions of this report)

**Short URL: **ia.cr/2021/1354

[ Cryptology ePrint archive ]