Welcome to the resource topic for 2018/966
Title:
On the Security of the Multivariate Ring Learning with Errors Problem
Authors: Carl Bootland, Wouter Castryck, Frederik Vercauteren
Abstract:The Multivariate Ring Learning with Errors (m-RLWE) problem was introduced in 2015 by Pedrouzo-Ulloa, Troncoso-Pastoriza and Pérez-González. Instead of working over a polynomial residue ring with one variable as in RLWE, it works over a polynomial residue ring in several variables. However, care must be taken when choosing the multivariate rings for use in cryptographic applications as they can be either weak or simply equivalent to univariate RLWE. For example, Pedrouzo-Ulloa et al.\ suggest using tensor products of cyclotomic rings, in particular power-of-two cyclotomic rings. They claim incorrectly that the security increases with the product of the individual degrees. In this paper, we present simple methods to solve the search m-RLWE problem far more efficiently than is stated in the current literature by reducing the problem to the RLWE problem in dimension equal to the maximal degree of its components (and not the product) and where the noise increases with the square-root of the degree of the other components. Our methods utilise the fact that the defining cyclotomic polynomials share algebraically related roots. We use these methods to successfully attack the search variant of the m-RLWE problem for a set of parameters estimated to offer more than 2600 bits of security, and being equivalent to solving the bounded distance decoding problem in a highly structured lattice of dimension 16384, in less than two weeks of computation time or just a few hours if parallelized on 128 cores. Finally, we also show that optimizing module-LWE cryptosystems by introducing an extra ring structure as is common practice to optimize LWE, often results in a total breakdown of security.
ePrint: https://eprint.iacr.org/2018/966
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 .