The multivariate ring learning with errors
(-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. We present simple methods to solve the search
-RLWE
problem far more efficiently than was claimed in the previous 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
-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, can result in a total breakdown of
security.
Keywords
multivariate, ring learning with errors, cyclotomic rings,
module-LWE