Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

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 O5 log λ) for the GGH scheme to O(λ log2 λ) in GGHLite, with respect to the security parameter λ for a constant multilinearity parameter.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr