Paper 2022/1612

On Black-Box Constructions of Time and Space Efficient Sublinear Arguments from Symmetric-Key Primitives

Laasya Bangalore, Georgetown University
Rishabh Bhadauria, Bar-Ilan University
Carmit Hazay, Bar-Ilan University
Muthuramakrishnan Venkitasubramaniam, Georgetown University

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.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2022
Zero Knowledge Proofs and Argument Succinct Argument Symmetric Key Primitives
Contact author(s)
lb1264 @ georgetown edu
rishabh bhadauria @ biu ac il
carmit hazay @ biu ac il
vmuthu @ gmail com
2022-11-21: approved
2022-11-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Laasya Bangalore and Rishabh Bhadauria and Carmit Hazay and Muthuramakrishnan Venkitasubramaniam},
      title = {On Black-Box Constructions of Time and Space Efficient Sublinear Arguments from Symmetric-Key Primitives},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1612},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.