Paper 2022/1690
Private Re-Randomization for Module LWE and Applications to Quasi-Optimal ZK-SNARKs
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)
- 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
-
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} }