GGHLite: More Efficient Multilinear Maps from Ideal Lattices

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

(

λ

log

2

λ

) in

GGHLite

, with respect to the security parameter

λ

(for a constant multilinearity parameter

κ

).