Welcome to the resource topic for 2020/1425
Title:
Public-Coin Zero-Knowledge Arguments with (almost) Minimal Time and Space Overheads
Authors: 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.
ePrint: https://eprint.iacr.org/2020/1425
Talk: https://www.youtube.com/watch?v=ce6mxVDZjfk
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .