## Séminaire Algorithmique |

Le séminaire a lieu **le mardi à 11 h 45** (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

# Résumé du séminaire du Mardi 16 Décembre 2014

*GGHLite: More Efficient Multilinear Maps from Ideal Lattices*

## par Adeline Langlois (LIP, ENS Lyon)

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*(λ
log^{2} λ) in GGHLite, with respect to the security
parameter λ for a constant multilinearity parameter.