SoK: On the Security of Cryptographic Problems from Linear Algebra


lattice-based cryptography
noisy linear algebra
learning with errors
short integer solutions

How to Cite

Bootland, C., Castryck, W., Szepieniec, A., & Vercauteren, F. (2023). SoK: On the Security of Cryptographic Problems from Linear Algebra. Mathematical Cryptology, 3(1), 52–95. Retrieved from


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.

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Copyright (c) 2023 Carl Bootland, Wouter Castryck, Alan Szepieniec, Frederik Vercauteren