Welcome to the resource topic for 2014/826
Title:
Learning with Errors in the Exponent
Authors: Ozgur Dagdelen, Sebastian Gajek, 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.
ePrint: https://eprint.iacr.org/2014/826
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .