Paper 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 $$, or lost at least a factor $$ 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.