verifiers—indeed one may say that one
may have never realized that the PCP
theorem may be true, had it not been
for some of the prior explorations!
Interactive Proofs: The first notion of a
probabilistic proof system to emerge
in the literature was that of an
interactive proof. This emerged in the works
of Goldwasser et al. 20 and Babai and
Moran. 7 An interactive proof consists
of an interaction between two entities
(or agents), a “prover” and a “verifier.”
The prover wishes to convince the verifier that some theorem A is true. The
verifier is again probabilistic and runs
in polynomial time, and should be
convinced if the assertion is true and
should reject any interaction with high
probability if the assertion is not true.
The goal here was not to improve on
the efficiency with which, say, proofs
of 3-satisfiability could be checked.
Instead the goal was to enhance the
class of assertions that could be verified in polynomial time. A nonmathematical, day-to-day, example of an
interactive proof would be that of
distinguishing between two drinks.
Imagine convincing your spouse or
friend that buying an expensive bottle of wine, brand X, is really worth it.
They may counter with a cheap bottle,
brand Y, that they claim tastes exactly
the same. You insist that they taste
quite different, but it is hard to prove
your point with any written proof. But
this is something we could attempt
to prove interactively, by a blind taste
test. You can ask your spouse/friend
to challenge you with a random glass
of wine and if by tasting you can tell
which brand it is, you manage to convince your partner that you may have a
point—the two drinks do taste different. By repeating this test many times,
you partner’s conviction increases.
Interactive proofs attempt to such capture phenomena and more. Indeed,
this very example is converted to a very
mathematical one by Goldreich et al., 19
who use a mathematical version here
to give proofs that two graphs are distinguishable, that is, they are not isomorphic. (This is a problem for which
we do not know how to give a polynomially long proof.)
The initial interest in interactive
proofs came from two very different
motivations. Goldwasser et al. were interested in the “knowledge” revealed
one of the
somewhat strange
aspects of PcP
research has been
that even though
the existence of
PcPs seems to
be a “positive”
statement, its use
is mostly negative.
We suggest that
positive uses might
emerge as more
of our life turns
digital, and we start
worrying not only
about the integrity
of the data, but
some of the
properties
they satisfy.
in multiparty interactions, from the
point of view of maintaining secrets.
To understand this concept, they first
needed to define interactive protocols
and interactive proofs, and then a formal measure of the knowledge complexity of this interaction. They noted
that while interaction may reveal many
bits of “information” (in the sense of
Shannon34) to the interacting players,
it may reveal little knowledge. For example, the interactive proof above that
brand X is distinguishable from brand
Y reveals no more “knowledge” than
the bare fact that they are distinguishable. It does not, for example, tell you
what features are present in one brand
and not in the other.
Babai and Moran’s motivation was
more oriented towards computational
complexity of some number-theoretic
and group-theoretic problems. They
were able to present interactive proofs
with just one rounds of interaction
between verifier and the prover for a
number of problems not known to be
in NP (i.e, not reducible to satisfiability). The implication, proved formally
in later works, was that such problems
may not be very hard computationally.
The theory of interactive proofs saw
many interesting discoveries through
the 1980s, and then culminated in
a surprising result in 1990 when
Shamir, 33 based on the work of Lund
et al., 28 showed the set of assertions
that could be proved interactively were
exactly those that could be verified by a
polynomial space bounded verifier.
Multi-prover and Oracle-Interactive
Proofs: Part of the developments in the
1980s led to variations on the theme of
interactive proofs. One such variation
that became significant to the development of PCPs was the notion of a
“Multi-prover Interactive Proof” (MIP)
discovered by Ben-Or et al. 8 Ben-Or
et al. were trying to replace some cryptographic assumptions (along the lines
of statements such as “RSA is secure”)
in existing interactive proofs with non-cryptographic ones. This led them to
propose the study of the setting where
the proof comes from a pair of provers
who, for the purpose of the verification
task, are willing to be separated and
quizzed by the verifier. The hope is that
the verifier can quiz them on related
facts to detect inconsistency on their
part. This limits the prover’s ability to