Speaker: Sergey Gorbunov, MIT
Title: Graded Multilinear Maps from Lattices
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 correspond 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 the hardness of a natural problem which can be thought of as analogous to the standard LWE problem.
Joint work with:Craig Gentry (IBM) and ShaiHalevi (IBM).