@inproceedings{688d16e75527487a8ac93bbf53e07707,
title = "GGHLite: more efficient multilinear maps from ideal lattices",
abstract = "The GGH Graded Encoding Scheme[9], based on ideal lattices, is the first plausible approximation to a cryptographic multilinear map. Unfortunately, using the security analysis in[9], 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[9] 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{\'e}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 Ω(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(λ5 log λ) for the GGH scheme to O(λ log2λ) in GGHLite, with respect to the security parameter λ (for a constant multilinearity parameter κ).",
author = "Adeline Langlois and Damien Stehl{\'e} and Ron Steinfeld",
year = "2014",
doi = "10.1007/978-3-642-55220-5_14",
language = "English",
isbn = "9783642552199",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer, Springer Nature",
pages = "239--256",
editor = "Nguyen, {Phong Q.} and Elisabeth Oswald",
booktitle = "Advances in Cryptology",
address = "United States",
note = "33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2014 ; Conference date: 11-05-2014 Through 15-05-2014",
}