Paper 2020/737

A non-PCP Approach to Succinct Quantum-Safe Zero-Knowledge

Jonathan Bootle, Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Gregor Seiler

Abstract

Today's most compact zero-knowledge arguments are based on the hardness of the discrete logarithm problem and related classical assumptions. If one is interested in quantum-safe solutions, then all of the known techniques stem from the PCP-based framework of Kilian (STOC 92) which can be instantiated based on the hardness of any collision-resistant hash function. Both approaches produce asymptotically logarithmic sized arguments but, by exploiting extra algebraic structure, the discrete logarithm arguments are a few orders of magnitude more compact in practice than the generic constructions. In this work, we present the first (poly)-logarithmic, potentially post-quantum zero-knowledge arguments that deviate from the PCP approach. At the core of succinct zero-knowledge proofs are succinct commitment schemes (in which the commitment and the opening proof are sub-linear in the message size), and we propose two such constructions based on the hardness of the (Ring)-Short Integer Solution (Ring-SIS) problem, each having certain trade-offs. For commitments to $N$ secret values, the communication complexity of our first scheme is $\tilde{O}(N^{1/c})$ for any positive integer $c$, and $O(\log^2 N)$ for the second. Both of these are a significant theoretical improvement over the previously best lattice construction by Bootle et al. (CRYPTO 2018) which gave $O(\sqrt{N})$-sized proofs.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2020
Keywords
LatticesZero-Knowledge ProofsSNARKS
Contact author(s)
jonathan bootle @ berkeley edu
vad @ zurich ibm com
nkn @ zurich ibm com
gseiler @ inf ethz ch
History
2020-07-30: revised
2020-06-18: received
See all versions
Short URL
https://ia.cr/2020/737
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/737,
      author = {Jonathan Bootle and Vadim Lyubashevsky and Ngoc Khanh Nguyen and Gregor Seiler},
      title = {A non-PCP Approach to Succinct Quantum-Safe Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2020/737},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/737}},
      url = {https://eprint.iacr.org/2020/737}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.