Paper 2022/1690

Private Re-Randomization for Module LWE and Applications to Quasi-Optimal ZK-SNARKs

Ron Steinfeld, Monash University
Amin Sakzad, Monash University
Muhammed F. Esgin, Monash University, CSIRO's Data61
Veronika Kuchta, Florida Atlantic University
Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Lattice Zero-Knowledge Proof Post-Quantum SNARK
Contact author(s)
ron steinfeld @ monash edu
amin sakzad @ monash edu
muhammed esgin @ monash edu
vkuchta @ fau edu
History
2022-12-06: approved
2022-12-06: received
See all versions
Short URL
https://ia.cr/2022/1690
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1690,
      author = {Ron Steinfeld and Amin Sakzad and Muhammed F. Esgin and Veronika Kuchta},
      title = {Private Re-Randomization for Module LWE and Applications to Quasi-Optimal ZK-SNARKs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1690},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1690}},
      url = {https://eprint.iacr.org/2022/1690}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.