In section 8.4 of Arora and Barak, after describing the public coin protocol for $\mathsf{GNI}$ and $\mathrm{IP=PSPACE}$, the authors state:

A curious feature of many known interactive proof systems is that in order to prove membership in language $L$ the prover needs to do more powerful computation than just deciding membership in $L$. We give some examples.

  1. The public coin system for graph nonisomorphism in Theorem 8.13 requires the prover to produce, for some randomly chosen hash function $h$ and a random element $y$ in the range of $h$, a graph $H$ such that $h(H)$ is isomorphic to either $G_1$ or $G_2$ and $h(x)=y$. This seems harder than just solving graph non-isomorphism (though we do not know of any proof that it is).

I believe the intent was:

...a graph $H$ such that $H$ is isomorphic to either $G_1$or $G_2$ and $h(H)=y$...

although I can't find it in any errata.

But more importantly, I believe the comment was to the effect of "finding preimages of hashes can be challenging, and the only obvious way for Merlin to execute the public coin $\mathsf{GNI}$ protocol is to go through each and every permutation $\pi$ of $G_1$ or $G_2$ and calculate $h(\pi(G_i))$ until he finds an $h(\pi(G_i))=y$."

But is it the case that all such public-coin protocols put a heavy burden on the prover? For example, the hash $h$ is not required to be difficult to invert; it just needs to be strongly universal, which, as I understand, is not the same as being one-way. So if Arthur were to give Merlin an image $y$ for some "easy-to-invert" hash function $h$, then it might not be so difficult for Merlin to find the preimage.

Is that the right interpretation of Arora and Barak? Has there been any progress on Arora and Barak's statement?

Answers to this question suggests that it is an open question as to whether an interactive proof for a problem in $\mathrm{coNP}$ requires the prover to do as much work as a $\mathrm{\#P}$ machine.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.