In the GMR[85] paper, a conjecture is made in section 3.7:

There exist languages $L$ that have perfect or statistical zero-knowledge proof systems, but do not have any Arthur-Merlin proof system that is perfect or zero-knowledge on $L$.

I was wondering what was the state of that conjecture. Is this something that has been answered?


  • $\begingroup$ Removed cross-post, didn't know this was not allowed, thanks for noticing it! $\endgroup$ Commented Jul 8 at 9:52

1 Answer 1


In the statistical zero-knowledge ($\mathsf{SZK}$) setting, several results were established by Okamoto. He demonstrated that Private-coin $\mathsf{SZK}$ is equal to Public-coin $\mathsf{SZK}$ where Public-coin $\mathsf{SZK}$ is another term for Arthur-Merlin proof system. For the definition of "Public-coin $\mathsf{SZK}$", the following is a snippet from a paper of Pass and Venkitasubramaniam that says

While, the notion of interactive proofs introduced by Goldwasser, Micali and Rackoff considers arbitrary probability polynomial time verifiers, the notion introduced by Babai and Moran, called Arthur-Merlin games considers verifiers that only send truly random messages; such proof systems are also called public coin.

Therefore, the conjecture is false in the $\mathsf{SZK}$ setting. In the perfect zero-knowledge ($\mathsf{PZK}$) setting, to the best of my knowledge, I'm only aware of the fact that $\mathsf{PZK} \subseteq \mathsf{PP}$ from a paper of Bouland et al. After reading through the introduction of a recent work on $\mathsf{PZK}$ by Dixon et al., I believe that the conjecture remains open in this setting.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.