Paper 2019/1109

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

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 = \prod_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., $\Phi_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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision.Mathematics
DOI
10.3390/math9080858
Keywords
Tensor of Number FieldsLattice CryptographyHomomorphic EncryptionRing Learning with ErrorsMultivariate RingsHardness Assumptions
Contact author(s)
apedrouzo @ gts uvigo es
juan troncoso-pastoriza @ epfl ch
nicolas @ inpher io
mariya @ inpher io
fperez @ gts uvigo es
History
2021-04-21: revised
2019-09-29: received
See all versions
Short URL
https://ia.cr/2019/1109
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1109,
      author = {Alberto Pedrouzo-Ulloa and Juan Ramón Troncoso-Pastoriza and Nicolas Gama and Mariya Georgieva and Fernando Pérez-González},
      title = {Revisiting Multivariate Ring Learning with Errors and its Applications on Lattice-based Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1109},
      year = {2019},
      doi = {10.3390/math9080858},
      note = {\url{https://eprint.iacr.org/2019/1109}},
      url = {https://eprint.iacr.org/2019/1109}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.