Paper 2020/1448

Shorter Lattice-Based Zero-Knowledge Proofs via One-Time Commitments

Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Gregor Seiler


There has been a lot of recent progress in constructing efficient zero-knowledge proofs for showing knowledge of an $\vec{\mathbf{s}}$ with small coefficients satisfying $\bm{A}\vec{\mathbf{s}}=\vec{\mathbf{t}}$. For typical parameters, the proof sizes have gone down from several megabytes to a bit under $50$KB (Esgin et al., Asiacrypt 2020). These are now within an order of magnitude of the sizes of lattice-based signatures, which themselves constitute proof systems which demonstrate knowledge of something weaker than the aforementioned equation. One can therefore see that this line of research is approaching optimality. In this paper, we modify a key component of these proofs, as well as apply several other tweaks, to achieve a further reduction of around $30\%$ in the proof output size. We also show that this savings propagates itself when these proofs are used in a general framework to construct more complex protocols.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2021
LatticesZero-Knowledge Proofs
Contact author(s)
vad @ zurich ibm com
nkn @ zurich ibm com
gseiler @ inf ethz ch
2021-03-01: last of 4 revisions
2020-11-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Vadim Lyubashevsky and Ngoc Khanh Nguyen and Gregor Seiler},
      title = {Shorter Lattice-Based Zero-Knowledge Proofs via One-Time Commitments},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1448},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.