Public Coins Versus Private Coins
In the same conference where Babai defined his proof system for MA, Shafi Goldwasser, Silvio Micali and Charles Rackoff published a paper defining the interactive proof system IP. 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 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 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. We call this 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 Sipser 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=AM for all constant k, so the IP have no advantage over AM.
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 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.
Read more about this topic: Interactive Proof System
Famous quotes containing the words public, coins and/or private:
“Money is power, and in that government which pays all the public officers of the states will all political power be substantially concentrated.”
—Andrew Jackson (1767–1845)
“A war undertaken without sufficient monies has but a wisp of force. Coins are the very sinews of battles.”
—François Rabelais (1494–1553)
“My gentleman gives the law where he is; he will outpray saints in chapel, outgeneral veterans in the field, and outshine all courtesy in the hall. He is good company for pirates, and good with academicians; so that it is useless to fortify yourself against him; he has the private entrance to all minds, and I could as easily exclude myself, as him.”
—Ralph Waldo Emerson (1803–1882)