## 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

Short URL: ia.cr/2016/589

[ Cryptology ePrint archive ]