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 security analysis in[9], scheme requires very large parameters provide for its underlying “encoding re-randomization” process. Our main contributions are formalize, simplify and improve efficiency of re-randomization process in construction. This results new construction that we call GGHLite. In particular, lower size standard deviation parameter of[9] from exponential polynomial parameter. improvement obtained via finer “drowning” step re-randomization, which apply Renyi divergence instead conventional statistical distance as measure between distributions. second reduce number randomizers needed Ω(n logn) 2, where n dimension lattices. These two allow us decrease bit public O(λ 5 logλ) O(λlog2 λ) GGHLite, with respect λ (for constant multilinearity κ).