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

Alexander R. Block, Justin Holmgren, Alon Rosen, Ron D. Rothblum, and 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\$.

Available format(s)
Category
Cryptographic protocols
Publication info
Keywords
zero knowledgeSNARKsspace efficiency
Contact author(s)
block9 @ purdue edu
History
Short URL
https://ia.cr/2020/1425

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},
note = {\url{https://eprint.iacr.org/2020/1425}},
url = {https://eprint.iacr.org/2020/1425}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.