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 $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.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
lattice-based cryptographyLearning with ErrorsLWELearning with RoundingLWRreduction
Contact author(s)
dapon @ cs umd edu
History
2016-06-06: received
Short URL
https://ia.cr/2016/589
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/589,
      author = {Jacob Alperin-Sheriff and Daniel Apon},
      title = {Dimension-Preserving Reductions from LWE to LWR},
      howpublished = {Cryptology ePrint Archive, Paper 2016/589},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/589}},
      url = {https://eprint.iacr.org/2016/589}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.