Cryptology ePrint Archive: Report 2014/826
Learning with Errors in the Exponent
Ozgur Dagdelen and 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.
Category / Keywords: Lattice theory, group theory, public-key encryption, existential relations, double hardness
Date: received 11 Oct 2014, last revised 11 Oct 2014
Contact author: sebastian gajek at gmail com
Available format(s): PDF | BibTeX Citation
Version: 20141012:010114 (All versions of this report)
Short URL: ia.cr/2014/826
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]