Public-Coin Zero-Knowledge Arguments with (almost) Minimal Time and Space Overheads

Alexander R.  Block; Justin Holmgren; Alon Rosen; Ron D. Rothblum; Pratik Soni

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2020/1425

Public-Coin Zero-Knowledge Arguments with (almost) Minimal Time and Space Overheads

Alexander R. Block

Justin Holmgren

Alon Rosen

Ron D. Rothblum

Pratik Soni

Abstract

Zero-knowledge protocols enable the truth of a mathematical statement to be certified by a verifier without revealing any other information. Such protocols are a cornerstone of modern cryptography and recently are becoming more and more practical. However, a major bottleneck in deployment is the efficiency of the prover and, in particular, the space-efficiency of the protocol. For every $\mathsf{NP}$ relation that can be verified in time $T$ and space $S$, we construct a public-coin zero-knowledge argument in which the prover runs in time $T \cdot \mathrm{polylog}(T)$ and space $S \cdot \mathrm{polylog}(T)$. Our proofs have length $\mathrm{polylog}(T)$ and the verifier runs in time $T \cdot \mathrm{polylog}(T)$ (and space $\mathrm{polylog}(T)$). Our scheme is in the random oracle model and relies on the hardness of discrete log in prime-order groups. Our main technical contribution is a new space efficient polynomial commitment scheme for multi-linear polynomials. Recall that in such a scheme, a sender commits to a given multi-linear polynomial $P \colon \mathbb{F}^n \rightarrow \mathbb{F}$ so that later on it can prove to a receiver statements of the form "$P(x) = y$". In our scheme, which builds on the commitment schemes of Bootle et al. (Eurocrypt 2016) and Bünz et al. (S&P 2018), we assume that the sender is given multi-pass streaming access to the evaluations of $P$ on the Boolean hypercube and w show how to implement both the sender and receiver in roughly time $2^n$ and space $n$ and with communication complexity roughly $n$.

Note: Fixed abstract and added full version of paper.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A major revision of an IACR publication in TCC 2020
DOI: 10.1007/978-3-030-64378-2_7
Keywords: zero-knowledge SNARKs space efficiency
Contact author(s): alexander r block @ gmail com
History: 2023-11-12: revised; 2020-11-15: received; See all versions
Short URL: https://ia.cr/2020/1425
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1425,
      author = {Alexander R.  Block and Justin Holmgren and Alon Rosen and Ron D. Rothblum and Pratik Soni},
      title = {Public-Coin Zero-Knowledge Arguments with (almost) Minimal Time and Space Overheads},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1425},
      year = {2020},
      doi = {10.1007/978-3-030-64378-2_7},
      note = {\url{https://eprint.iacr.org/2020/1425}},
      url = {https://eprint.iacr.org/2020/1425}
}