[Resource Topic] 2014/487: GGHLite: More Efficient Multilinear Maps from Ideal Lattices

Welcome to the resource topic for 2014/487

GGHLite: More Efficient Multilinear Maps from Ideal Lattices

Authors: Adeline Langlois, Damien Stehle, Ron Steinfeld


The GGH Graded Encoding Scheme, based on ideal lattices, is the first plausible approximation to a cryptographic multilinear map. Unfortunately, using the security analysis in the original paper, 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. This results in a new construction that we call GGHLite. In particular, we first lower the size of a standard deviation parameter of the re-randomization process of the original scheme from exponential to polynomial in the security parameter. This first improvement is obtained via a finer security analysis of the drowning step of re-randomization, in which we apply the Rényi divergence instead of the conventional statistical distance as a measure of distance between distributions. Our second improvement is to reduce the number of randomizers needed from \Omega(n \log n) to 2, where n is the dimension of the underlying ideal lattices. These two contributions allow us to decrease the bit size of the public parameters from O(\lambda^5 \log \lambda) for the GGH scheme to O(\lambda \log^2 \lambda) in GGHLite, with respect to the security parameter \lambda (for a constant multilinearity parameter \kappa).

ePrint: https://eprint.iacr.org/2014/487

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .