Revisiting Multivariate Ring Learning with Errors and Its Applications on Lattice-Based Cryptography

Alberto Pedrouzo-Ulloa, Juan Ramón Troncoso-Pastoriza, Nicolas Gama, Mariya Georgieva and Fernando Pérez-González
Additional contact information
Alberto Pedrouzo-Ulloa: AtlanTTic Research Center, Universidade de Vigo, 36310 Vigo, Spain
Juan Ramón Troncoso-Pastoriza: Laboratory for Data Security, École Polytechnique Fédérale de Lausanne, CH-1015 Lausanne, Switzerland
Nicolas Gama: Inpher, CH-1015 Lausanne, Switzerland
Mariya Georgieva: Inpher, CH-1015 Lausanne, Switzerland
Fernando Pérez-González: AtlanTTic Research Center, Universidade de Vigo, 36310 Vigo, Spain

Mathematics, 2021, vol. 9, issue 8, 1-42

Abstract: The “Multivariate Ring Learning with Errors” problem was presented as a generalization of Ring Learning with Errors (RLWE), introducing efficiency improvements with respect to the RLWE counterpart thanks to its multivariate structure. Nevertheless, the recent attack presented by Bootland, Castryck and Vercauteren has some important consequences on the security of the multivariate RLWE problem with “non-coprime” cyclotomics; this attack transforms instances of m -RLWE with power-of-two cyclotomic polynomials of degree n = ? i n i into a set of RLWE samples with dimension max i { n i } . This is especially devastating for low-degree cyclotomics (e.g., ? 4 ( x ) = 1 + x 2 ). In this work, we revisit the security of multivariate RLWE and propose new alternative instantiations of the problem that avoid the attack while still preserving the advantages of the multivariate structure, especially when using low-degree polynomials. Additionally, we show how to parameterize these instances in a secure and practical way, therefore enabling constructions and strategies based on m -RLWE that bring notable space and time efficiency improvements over current RLWE-based constructions.

Keywords: tensor of number fields; lattice cryptography; homomorphic encryption; ring learning with errors; multivariate rings (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/8/858/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/8/858/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:8:p:858-:d:535967

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().