Welcome to the resource topic for 2021/1354
Title:
SoK: On the Security of Cryptographic Problems from Linear Algebra
Authors: Carl Bootland, Wouter Castryck, Alan Szepieniec, 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.
ePrint: https://eprint.iacr.org/2021/1354
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .