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 $\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$).

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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2014/487}},
      url = {https://eprint.iacr.org/2014/487}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.