Editing Interactive proof system (section)

=== Public coin protocol versus private coin protocol ===

In a ''public coin'' protocol, the random choices made by the verifier are made public. They remain private in a private coin protocol.

In the same conference where Babai defined his proof system for '''MA''', [[Shafi Goldwasser]], [[Silvio Micali]] and [[Charles Rackoff]]<ref>{{Cite journal | last1=Goldwasser | first1=S. | last2=Micali | first2=S. | last3=Rackoff | first3=C. | title=The knowledge complexity of interactive proof systems | url=http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC02/GMR89.pdf | year=1989 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=18 | issue=1 | pages=186–208 | doi=10.1137/0218012 }} [http://theory.lcs.mit.edu/~cis/pubs/shafi/1985-stoc.pdf Extended abstract] {{Webarchive|url=https://web.archive.org/web/20060623020231/http://theory.lcs.mit.edu/~cis/pubs/shafi/1985-stoc.pdf |date=2006-06-23 }}</ref> published a paper defining the interactive proof system '''IP'''[''f''(''n'')]. This has the same machines as the '''MA''' protocol, except that ''f''(''n'') ''rounds'' are allowed for an input of size ''n''. In each round, the verifier performs computation and passes a message to the prover, and the prover performs computation and passes information back to the verifier. At the end the verifier must make its decision. For example, in an '''IP'''[3] protocol, the sequence would be VPVPVPV, where V is a verifier turn and P is a prover turn.

In Arthur–Merlin protocols, Babai defined a similar class '''AM'''[''f''(''n'')] which allowed ''f''(''n'') rounds, but he put one extra condition on the machine: the verifier must show the prover all the random bits it uses in its computation. The result is that the verifier cannot "hide" anything from the prover, because the prover is powerful enough to simulate everything the verifier does if it knows what random bits it used. This is called a ''public coin'' protocol, because the random bits ("coin flips") are visible to both machines. The '''IP''' approach is called a ''private coin'' protocol by contrast.

The essential problem with public coins is that if the prover wishes to maliciously convince the verifier to accept a string which is not in the language, it seems like the verifier might be able to thwart its plans if it can hide its internal state from it. This was a primary motivation in defining the '''IP''' proof systems.

In 1986, Goldwasser and [[Michael Sipser|Sipser]]<ref>Shafi Goldwasser and Michael Sipser. [http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-stoc.pdf Private coins versus public coins in interactive proof systems] {{Webarchive|url=https://web.archive.org/web/20050127045423/http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-stoc.pdf |date=2005-01-27 }}. ''Proceedings of ACM STOC'86'', pp. 58–68. 1986.</ref>  showed, perhaps surprisingly, that the verifier's ability to hide coin flips from the prover does it little good after all, in that an Arthur–Merlin public coin protocol with only two more rounds can recognize all the same languages. The result is that public-coin and private-coin protocols are roughly equivalent.  In fact, as Babai shows in 1988, '''AM'''[''k'']='''AM''' for all constant ''k'', so the '''IP'''[''k''] have no advantage over '''AM'''.<ref>László Babai and [[Shlomo Moran]]. [http://portal.acm.org/citation.cfm?id=49987 Arthur–Merlin games: a randomized proof system, and a hierarchy of complexity classes]. ''Journal of Computer and System Sciences'', 36: p.254–276. 1988.</ref>

To demonstrate the power of these classes, consider the [[graph isomorphism problem]], the problem of determining whether it is possible to permute the vertices of one graph so that it is identical to another graph. This problem is in '''NP''', since the proof certificate is the permutation which makes the graphs equal. It turns out that the 
[[complement (complexity)|complement]] of the graph isomorphism problem, a co-'''NP''' problem not known to be in '''NP''', has an '''AM''' algorithm and the best way to see it is via a private coins algorithm.<ref name="O. Goldreich, S. Micali 1991">O. Goldreich, S. Micali, A. Wigderson. [http://portal.acm.org/citation.cfm?id=116852 Proofs that yield nothing but their validity]. ''Journal of the ACM'', volume 38, issue 3, p.690–728. July 1991.</ref>