Cryptology ePrint Archive: Report 2016/589

Dimension-Preserving Reductions from LWE to LWR

Jacob Alperin-Sheriff and Daniel Apon

Abstract: The Learning with Rounding (LWR) problem was first introduced by Banerjee, Peikert, and Rosen (Eurocrypt 2012) as a \emph{derandomized} form of the standard Learning with Errors (LWE) problem. The original motivation of LWR was as a building block for constructing efficient, low-depth pseudorandom functions on lattices. It has since been used to construct reusable computational extractors, lossy trapdoor functions, and deterministic encryption.

In this work we show two (incomparable) dimension-preserving reductions from LWE to LWR in the case of a \emph{polynomial-size modulus}. Prior works either required a superpolynomial modulus $q$, or lost at least a factor $\log(q)$ in the dimension of the reduction. A direct consequence of our improved reductions is an improvement in parameters (i.e. security and efficiency) for each of the known applications of poly-modulus LWR.

Our results directly generalize to the ring setting. Indeed, our formal analysis is performed over ``module lattices,'' as defined by Langlois and Stehlé (DCC 2015), which generalize both the general lattice setting of LWE and the ideal lattice setting of RLWE as the single notion M-LWE. We hope that taking this broader perspective will lead to further insights of independent interest.

Category / Keywords: lattice-based cryptography; Learning with Errors; LWE; Learning with Rounding; LWR; reduction

Date: received 4 Jun 2016

Contact author: dapon at cs umd edu

Available format(s): PDF | BibTeX Citation

Version: 20160606:150451 (All versions of this report)

Short URL: ia.cr/2016/589

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]