Paper 2014/487
GGHLite: More Efficient Multilinear Maps from Ideal Lattices
Adeline Langlois, Damien Stehle, and Ron Steinfeld
Abstract
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
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in EUROCRYPT 2014
- Keywords
- multilinear maps
- Contact author(s)
- adeline langlois @ ens-lyon fr
- History
- 2014-06-23: received
- Short URL
- https://ia.cr/2014/487
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2014/487, author = {Adeline Langlois and Damien Stehle and Ron Steinfeld}, title = {{GGHLite}: More Efficient Multilinear Maps from Ideal Lattices}, howpublished = {Cryptology {ePrint} Archive, Paper 2014/487}, year = {2014}, url = {https://eprint.iacr.org/2014/487} }