Cryptology ePrint Archive: Report 2014/645
Graded Multilinear Maps from Lattices
Craig Gentry and Sergey Gorbunov and Shai Halevi
Abstract: Graded multilinear encodings have found extensive applications in cryptography ranging from
non-interactive key exchange protocols, to broadcast and attribute-based encryption, and even to software obfuscation.
Despite seemingly unlimited applicability, essentially only two candidate constructions are known (GGH and CLT). In this work, we describe a new graded multilinear encoding scheme from lattices.
Our construction encodes Learning With Errors (LWE) samples
in short square matrices of higher dimensions. Addition and multiplication of the encodings corresponds naturally to addition and multiplication
of the LWE secrets. Comparisons of any two encodings
can be performed publicly at any level.
The security of our scheme relies on a hardness of a natural problem which can be thought of as analogous to standard LWE problem.
Category / Keywords: Lattices, LWE, Multilinear Maps
Date: received 20 Aug 2014, last revised 20 Aug 2014
Contact author: sergeyg at mit edu
Available format(s): PDF | BibTeX Citation
Version: 20140827:072915 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]