GGHLite: more efficient multilinear maps from ideal lattices

Adeline Langlois, Damien Stehlé, Ron Steinfeld

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

90 Citations (Scopus)

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é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 κ).

Original languageEnglish
Title of host publicationAdvances in Cryptology
Subtitle of host publicationEUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsPhong Q. Nguyen, Elisabeth Oswald
Place of PublicationHeidelberg
PublisherSpringer, Springer Nature
Pages239-256
Number of pages18
ISBN (Electronic)9783642552205
ISBN (Print)9783642552199
DOIs
Publication statusPublished - 2014
Event33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2014 - Copenhagen, Denmark
Duration: 11 May 201415 May 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8441 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2014
Country/TerritoryDenmark
CityCopenhagen
Period11/05/1415/05/14

Fingerprint

Dive into the research topics of 'GGHLite: more efficient multilinear maps from ideal lattices'. Together they form a unique fingerprint.

Cite this