Paper 2020/1425
PublicCoin ZeroKnowledge Arguments with (almost) Minimal Time and Space Overheads
Abstract
Zeroknowledge 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 spaceefficiency of the protocol. For every $\mathsf{NP}$ relation that can be verified in time $T$ and space $S$, we construct a publiccoin zeroknowledge 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 primeorder groups. Our main technical contribution is a new space efficient polynomial commitment scheme for multilinear polynomials. Recall that in such a scheme, a sender commits to a given multilinear 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 multipass 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)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in TCC 2020
 DOI
 10.1007/9783030643782_7
 Keywords
 zeroknowledgeSNARKsspace efficiency
 Contact author(s)
 alexander r block @ gmail com
 History
 20231112: revised
 20201115: 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 = {PublicCoin ZeroKnowledge Arguments with (almost) Minimal Time and Space Overheads}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/1425}, year = {2020}, doi = {10.1007/9783030643782_7}, url = {https://eprint.iacr.org/2020/1425} }