Mon, 03 Apr 2023 09:00 Private Re-Randomization for Module LWE and Applications to Quasi-Optimal ZK-SNARKs by Ron Steinfeld (Monash University)

We introduce the first candidate lattice-based Designated Verifier (DV) ZK-SNARK protocol with \emph{quasi-optimal proof length} (quasi-linear in the security/privacy parameter), avoiding the use of the exponential smudging technique. Our ZK-SNARK also achieves significant improvements in proof length in practice, with proofs length below 6 KB for 128-bit security/privacy level. Our main technical result is a new regularity theorem for `private' re-randomization of Module LWE (MLWE) samples using discrete Gaussian randomization vectors, also known as a lattice-based leftover hash lemma with leakage, which applies with a discrete Gaussian re-randomization parameter that is polynomial in the statistical privacy parameter. To obtain this result, we obtain bounds on the smoothing parameter of an intersection of a random q-ary SIS module lattice, Gadget SIS module lattice, and Gaussian orthogonal module lattice over standard power of 2 cyclotomic rings, and a bound on the minimum of module gadget lattices. We then introduce a new candidate \emph{linear-only} homomorphic encryption scheme called Module Half-GSW (HGSW), which is a variant of the GSW somewhat homomorphic encryption scheme over modules, and apply our regularity theorem to provide smudging-free circuit-private homomorphic linear operations for Module HGSW.

Note the changed time.

Speaker Bio:

Ron Steinfeld is an Associate Professor at Monash University. His research focuses on post-quantum cryptography and its applications. He obtained his Ph.D. degree in cryptography at Monash University in 2003. He was a postdoctoral ARC Research Fellow at Macquarie University. He joined Monash University in 2012.

Venue: Online