6/15/92 Richard Ladner Talk at ICSI

[Mark Kempson]

The International Computer Science Institute
is pleased to present a talk:

Monday, June 15, 1992 10:00 a.m.

RICHARD LADNER
Department of Computer Science and Engineering
University of Washington
Seattle, WA

``Interactive Proof Systems with Polynomially Bounded Strategies''

Interactive proof systems (IP) were introduced by
Goldwasser, Micali, and Rackoff as a formal model to inves-
tigate issues in cryptography and as a natural extension to
NP, the class of problems solvable in nondeterministic poly-
nomial time. The vision was that in an interactive proof
system a Prover and a Verifier would interact in such way
that the Prover could convince the Verifier with high proba-
bility of a true fact, but could only convince a Verifier
with very low probability of a false fact. In this model,
the Prover is all-powerful and the Verifier is limited to
run in polynomial time. The Verifier has the additional
ability to flip an unbiased coin.

The issue which we address in this paper is whether
this original IP model can really serve as a practical basis
for cryptography or as a practical extension of NP. We
define restrictions which can be placed on both the Prover
and the Verifier in order to make interactive proof systems
potentially practical. Then, we prove a number of results
about these restricted interactive proof systems. The prin-
cipal restriction we consider is limiting the Prover to hav-
ing a polynomial size strategy. The restriction to poly-
strategy is tantamount to saying that the interactive proof
system could potentially be practically implemented.

If the interaction between Prover and Verifier can be
represented by a polynomial size computation tree, visible
to the Prover, then the Prover has a very simple polynomial
size strategy. Alternatively, if the Verifier is limited to
a logarithmic number of flips of a coin, then again the
Prover has a simple polynomial size strategy. Thus, we
define restrictions on interactive proof systems called
poly-tree-size and log-random-bits, which are special cases
of poly-strategy. If we restrict the Prover and Verifier to
logarithmic space then the question arises as to whether a
restricted Prover can convince such a limited Verifier of as
much as it could when they each had no such space limita-
tion. It turns out that our most technically challenging
results are about interactive proof systems where the Prover
and Verifier limited to logarithmic space. We call this
restriction log-space. Finally, interactive proof systems
may be public or private, referring respectively to whether
the Prover has full view of what the Verifier is doing or
whether what the Verifier is doing can be partially hidden
from the Prover.

A main result of the paper is that interactive proof
systems in which the Prover is restricted to a poly-strategy
are equivalent to MA, Merlin-Arthur games, defined by Babai
and Moran. Poly-tree-size is also equivalent to MA, but
when log-space is added as a restriction, the power of
poly-tree-size reduces to NP. Log-random-bits is equivalent
to NP, and when log-space is added as a restriction, the
power is not diminished. The proof that NP $bseteq$
IP(log-space, log-random-bits) illustrates an interesting
application of the new ``fingerprinting'' method of Lipton.
Public interactive proof systems which have the poly-
strategy restriction are also investigated.

(Joint work with Anne Condon, University of Wisconsin, Madison)

This talk will be held in the Main Lecture Hall at ICSI.
1947 Center Street, Sixth Floor, Berkeley, CA 94704
(On Center between Milvia and Martin Luther King Jr. Way)