Paper 2020/1425
PublicCoin ZeroKnowledge Arguments with (almost) Minimal Time and Space Overheads
Alexander R. Block, Justin Holmgren, Alon Rosen, Ron D. Rothblum, and Pratik Soni
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$.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published by the IACR in TCC 2020
 Keywords
 zero knowledgeSNARKsspace efficiency
 Contact author(s)
 block9 @ purdue edu
 History
 20201115: received
 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}, note = {\url{https://eprint.iacr.org/2020/1425}}, url = {https://eprint.iacr.org/2020/1425} }