SoK: On the Security of Cryptographic Problems from Linear Algebra

Carl Bootland, Wouter Castryck, 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.

Available format(s)
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
lattice-based cryptographynoisy linear algebralearning with errorsshort integer solutionsNTRU
Contact author(s)
carl bootland @ esat kuleuven be
wouter castryck @ esat kuleuven be
alan @ nervos org
frederik vercauteren @ esat kuleuven be
History
Short URL
https://ia.cr/2021/1354

CC BY

BibTeX

@misc{cryptoeprint:2021/1354,
author = {Carl Bootland and Wouter Castryck and Alan Szepieniec and Frederik Vercauteren},
title = {SoK: On the Security of Cryptographic Problems from Linear Algebra},
howpublished = {Cryptology ePrint Archive, Paper 2021/1354},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1354}},
url = {https://eprint.iacr.org/2021/1354}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.