Paper 2014/826

Learning with Errors in the Exponent

Ozgur Dagdelen, Sebastian Gajek, and Florian Gopfert

Abstract

We initiate the study of a novel class of group-theoretic intractability problems. Inspired by the theory of learning in presence of errors [Regev, STOC'05] we ask if noise in the exponent amplifies intractability. We put forth the notion of Learning with Errors in the Exponent (LWEE) and rather surprisingly show that various attractive properties known to exclusively hold for lattices carry over. Most notably are worst-case hardness and post-quantum resistance. In fact, LWEE's duality is due to the reducibility to two seemingly unrelated assumptions: learning with errors and the representation problem [Brands, Crypto'93] in finite groups. For suitable parameter choices LWEE superposes properties from each individual intractability problem. The argument holds in the classical and quantum model of computation. We give the very first construction of a semantically secure public-key encryption system in the standard model. The heart of our construction is an ``error recovery'' technique inspired by [Joye-Libert, Eurocrypt'13] to handle critical propagations of noise terms in the exponent.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
Lattice theorygroup theorypublic-key encryptionexistential relationsdouble hardness
Contact author(s)
sebastian gajek @ gmail com
History
2014-10-12: received
Short URL
https://ia.cr/2014/826
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/826,
      author = {Ozgur Dagdelen and Sebastian Gajek and Florian Gopfert},
      title = {Learning with Errors in the Exponent},
      howpublished = {Cryptology ePrint Archive, Paper 2014/826},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/826}},
      url = {https://eprint.iacr.org/2014/826}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.