Welcome to the resource topic for 2022/1612
Title:
On Black-Box Constructions of Time and Space Efficient Sublinear Arguments from Symmetric-Key Primitives
Authors: Laasya Bangalore, Rishabh Bhadauria, Carmit Hazay, Muthuramakrishnan Venkitasubramaniam
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 design the first such zero-knowledge system with sublinear communication complexity (when the underlying \textsf{NP} relation uses non-trivial space) and provide evidence why existing techniques are unlikely to improve the communication complexity in this setting.
Namely, for every NP relation that can be verified in time T and space S by a RAM program, 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 \widetilde{O}(T) and space \widetilde{O}(S), the verifier runs in time \widetilde{O}(T/S+S) and space \widetilde{O}(1) and the communication is \widetilde{O}(T/S), where \widetilde{O}() ignores polynomial factors in \log T and \kappa is the security parameter. As our construction is public-coin, we can apply the Fiat-Shamir heuristic to make it non-interactive with sample communication/computation complexities.
Furthermore, we give evidence that reducing the proof length below \widetilde{O}(T/S) will be hard using existing symmetric-key based techniques by arguing the space-complexity of constant-distance error correcting codes.
ePrint: https://eprint.iacr.org/2022/1612
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 .