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 $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 $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},
      url = {https://eprint.iacr.org/2020/518}
}