Vol. 4, No. 1, 2020

Download this article
Download this article For screen
For printing
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 2329-907X (online)
ISSN 2329-9061 (print)
 
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