Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings

Muhammed F.  Esgin; Ngoc Khanh Nguyen; Gregor Seiler

Paper 2020/518

Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings

Muhammed F. Esgin, Ngoc Khanh Nguyen, and Gregor Seiler

Abstract

We propose a very fast lattice-based zero-knowledge proof system for exactly proving knowledge of a ternary solution $\vec{s} \in \{-1,0,1\}^n$ to a linear equation $A\vec{s}=\vec{u}$ over $\mathbb{Z}_q$, which improves upon the protocol by Bootle, Lyubashevsky and Seiler (CRYPTO 2019) by producing proofs that are shorter by a factor of $8$. At the core lies a technique that utilizes the module-homomorphic BDLOP commitment scheme (SCN 2018) over the fully splitting cyclotomic ring $\mathbb{Z}_q[X]/(X^d + 1)$ to prove scalar products with the NTT vector of a secret polynomial.

Note: update using corrected protocol from 2020/517

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A major revision of an IACR publication in ASIACRYPT 2020
Keywords: lattice-based zero-knowledge commitments
Contact author(s): gseiler @ inf ethz ch
History: 2020-11-10: last of 5 revisions; 2020-05-05: received; See all versions
Short URL: https://ia.cr/2020/518
License: CC BY

BibTeX

@misc{cryptoeprint:2020/518,
      author = {Muhammed F.  Esgin and Ngoc Khanh Nguyen and Gregor Seiler},
      title = {Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings},
      howpublished = {Cryptology ePrint Archive, Paper 2020/518},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/518}},
      url = {https://eprint.iacr.org/2020/518}
}