Cryptology ePrint Archive: Report 2021/1354

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:

[ Cryptology ePrint archive ]