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