Paper 2021/605

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

Benny Applebaum and Eyal Golombek

Abstract

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.