GGHLite: More Efficient Multilinear Maps from Ideal Lattices

The Diffie-Hellman key exchange protocol allows two users to agree on a shared secret key. It is based on the hardness of the discrete logarithm problem.

Cryptographic multilinar maps were first introduced in 2003 to generalize the Diffie Hellman key exchange protocol from two to a large number of users. But constructing such a map was an open problem until 2013. The GGH Graded Encoding Scheme (of Garg, Gentry and Halevi), based on ideal lattices, is the first plausible approximation to a cryptographic multilinear map. Unfortunately, using the security analysis the authors provided, the scheme requires very large parameters to provide security for its underlying encoding re-randomization process.

Our main contributions are to formalize, simplify and improve the efficiency and the security analysis of the re-randomization process in the GGH construction. We apply these results in a new construction that we call GGHLite.

In this talk I will first introduce the notion of cryptographic multilinear maps, their applications in cryptography, and the GGH construction, then I will explain our contributions and how they allow us to decrease the bit size of the public parameters from O (λ5 log λ) for the GGH scheme to O (λ log2 λ) in GGHLite, with respect to the security parameter λ for a constant multilinearity parameter.