Paper 2021/605

On the Randomness Complexity of Interactive Proofs and Statistical Zero-Knowledge Proofs

Benny Applebaum and Eyal Golombek


We study the randomness complexity of interactive proofs and zero-knowledge proofs. In particular, we ask whether it is possible to reduce the randomness complexity, $R$, of the verifier to be comparable with the number of bits, $C_V$, that the verifier sends during the interaction. We show that such \emph{randomness sparsification} is possible in several settings. Specifically, unconditional sparsification can be obtained in the non-uniform setting (where the verifier is modelled as a circuit), and in the uniform setting where the parties have access to a (reusable) common-random-string (CRS). We further show that constant-round uniform protocols can be sparsified without a CRS under a plausible worst-case complexity-theoretic assumption that was used previously in the context of derandomization. All the above sparsification results preserve statistical-zero knowledge provided that this property holds against a \emph{cheating verifier}. We further show that randomness sparsification can be applied to honest-verifier statistical zero-knowledge (HVSZK) proofs at the expense of increasing the communication from the prover by $R-F$ bits, or, in the case of honest-verifier perfect zero-knowledge (HVPZK) by slowing down the simulation by a factor of $2^{R-F}$. Here $F$ is a new measure of \emph{accessible bit complexity} of an HVZK proof system that ranges from 0 to $R$, where a maximal grade of $R$ is achieved when zero-knowledge holds against a ``semi-malicious'' verifier that maliciously selects its random tape and then plays honestly. Consequently, we show that some classical HVSZK proof systems, like the one for the complete Statistical-Distance problem (Sahai and Vadhan, JACM 2003) admit randomness sparsification with no penalty. Along the way we introduce new notions of pseudorandomness against interactive proof systems, and study their relations to existing notions of pseudorandomness.

Available format(s)
Publication info
Preprint. MINOR revision.
interactive proofszero-knowledgepseudorandomness
Contact author(s)
benny applebaum @ gmail com
2021-05-10: received
Short URL
Creative Commons Attribution


      author = {Benny Applebaum and Eyal Golombek},
      title = {On the Randomness Complexity of Interactive Proofs and Statistical Zero-Knowledge Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2021/605},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.