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

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

Laasya Bangalore, Rishabh Bhadauria, Carmit Hazay, Muthuramakrishnan Venkitasubramaniam

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 …

box eprint report key space