GGHLite: More Efficient Multilinear Maps from Ideal Lattices
Adeline Langlois, Damien Stehlé and Ron Steinfeld
Abstract: The GGH Graded Encoding Scheme \cite{GGH13}, based on ideal
lattices, is the first plausible approximation to a cryptographic
multilinear map. Unfortunately, using the security analysis
in \cite{GGH13}, 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 \cite{GGH13}
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).
Download: pdf.
Homepage