Cryptology ePrint Archive: Report 2019/1109

Revisiting Multivariate Ring Learning with Errors and its Applications on Lattice-based Cryptography

Alberto Pedrouzo-Ulloa and Juan Ramón Troncoso-Pastoriza and Nicolas Gama and 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 \emph{et al.} has some important consequences on the security of the multivariate RLWE problem with ``non-coprime'' modular functions; this attack transforms instances of $m$-RLWE with power-of-two cyclotomic modular functions 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 modular functions (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 modular functions. 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.

Category / Keywords: public-key cryptography / Tensor of Number Fields, Lattice Cryptography, Homomorphic Encryption, Ring Learning with Errors, Multivariate Rings, Hardness Assumptions

Date: received 27 Sep 2019

Contact author: apedrouzo at gts uvigo es, juan troncoso-pastoriza@epfl ch, nicolas@inpher io, mariya@inpher io, fperez@gts uvigo es

Available format(s): PDF | BibTeX Citation

Version: 20190929:184614 (All versions of this report)

Short URL: ia.cr/2019/1109


[ Cryptology ePrint archive ]