CryptoDB
On Black-Box Constructions of Time and Space Efficient Sublinear Arguments from Symmetric-Key Primitives
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2022 |
| Abstract: | Zero-knowledge proofs allow a prover to convince a verifier of a statement without revealing anything besides its validity. A major bottleneck in scaling sub-linear zero-knowledge proofs is the high space requirement of the prover, even for NP relations that can be verified in a small space. In this work, we ask whether there exist complexity-preserving (i.e. overhead w.r.t time and space are minimal) succinct zero-knowledge arguments of knowledge with minimal assumptions while making only black-box access to the underlying primitives. We essentially resolve this question up to polylogarithmic factors. Namely, for every NP relation that can be verified in time T and space S, we construct a public-coin zero-knowledge argument system that is black-box based on collision-resistant hash-functions (CRH) where the prover runs in time $\O(T)$ and space $\O(S)$, the verifier runs in time $\O(T/S+S)$ and space $\O(\kappa)$ and the communication is $\O(T/S)$, where $\kappa$ is the statistical security parameter. Using the Fiat-Shamir heuristic, our construction yields the first complexity-preserving ZK-SNARK based on CRH (via a black-box construction). Furthermore, we give evidence that reducing the proof length below $\O(T/S)$ will be hard using existing techniques by arguing the space-complexity of constant-distance error correcting codes. |
BibTeX
@inproceedings{tcc-2022-32615,
title={On Black-Box Constructions of Time and Space Efficient Sublinear Arguments from Symmetric-Key Primitives},
publisher={Springer-Verlag},
author={Laasya Bangalore and Rishabh Bhadauria and Carmit Hazay and Muthuramakrishnan Venkitasubramaniam},
year=2022
}