Vol. 4, No. 1, 2020

 Recent Volumes 5: Gauge Theory and Low-Dimensional Topology 4: ANTS XIV 3: Hillman: Poincaré Duality 2: ANTS XIII 1: ANTS X
 The Open Book Series All Volumes About the Series Ethics Statement Purchase Printed Copies Author Index ISSN (electronic): 2329-907X ISSN (print): 2329-9061 MSP Books and Monographs Other MSP Publications
On the security of the multivariate ring learning with errors problem

Carl Bootland, Wouter Castryck and Frederik Vercauteren

Vol. 4 (2020), No. 1, 57–71
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. We present simple methods to solve the search $m$-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 $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, can result in a total breakdown of security.

Keywords
multivariate, ring learning with errors, cyclotomic rings, module-LWE
Mathematical Subject Classification 2010
Primary: 11T71
Secondary: 11R18, 94A60
Milestones
Received: 28 February 2020
Accepted: 29 April 2020
Published: 29 December 2020
Authors
 Carl Bootland imec – COSIC KU Leuven Heverlee Belgium Wouter Castryck imec – COSIC KU Leuven Leuven Belgium Department of Mathematics: Algebra and Geometry Ghent University Ghent Belgium Frederik Vercauteren imec – COSIC KU Leuven Heverlee Belgium