Paper 2020/1183

Practical Lattice-Based Zero-Knowledge Proofs for Integer Relations

Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Gregor Seiler

Abstract

We present a novel lattice-based zero-knowledge proof system for showing that (arbitrary-sized) committed integers satisfy additive and multiplicative relationships. The proof sizes of our schemes are between two to three orders of magnitude smaller than in the lattice proof system of Libert et al. (CRYPTO 2018) for the same relations. Because the proof sizes of our protocols grow linearly in the integer length, our proofs will eventually be longer than those produced by quantum-safe succinct proof systems for general circuits (e.g. Ligero, Aurora, etc.). But for relations between reasonably-sized integers (e.g. $512$-bit), our proofs still result in the smallest zero-knowledge proof system based on a quantum-safe assumption. Of equal importance, the run-time of our proof system is at least an order of magnitude faster than any other quantum-safe scheme.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACM CCS 2020
DOI
10.1145/3372297.3417894
Keywords
lattice-basedzero-knowledge proofs
Contact author(s)
vad @ zurich ibm com
nkn @ zurich ibm com
gseiler @ inf ethz ch
History
2020-09-30: received
Short URL
https://ia.cr/2020/1183
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1183,
      author = {Vadim Lyubashevsky and Ngoc Khanh Nguyen and Gregor Seiler},
      title = {Practical Lattice-Based Zero-Knowledge Proofs for Integer Relations},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1183},
      year = {2020},
      doi = {10.1145/3372297.3417894},
      note = {\url{https://eprint.iacr.org/2020/1183}},
      url = {https://eprint.iacr.org/2020/1183}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.