Probabilistically Checkable Arguments"
Speaker: Yael Kalail , Microsoft
Date: August 15 2008
Time: 10:30AM to 12:00PM
Location: 32-G449 Kiva
Contact: Be, 3-6098, imbe
Joint CIS and Microsoft talk
Abstract:
We give two results. The first is a general reduction converting any
public-coin interactive proof into a one-round (two-message) argument.
It is based on a method of Aiello et al, using a
Private-Information-Retrieval (PIR) scheme to collapse rounds in
interactive proofs. For example, the reduction implies that for any
security parameter t, the membership in any language in PSPACE can be
proved by a one-round (two-message) argument of size poly(n,t), which
is sound for malicious provers of size 2^t.
(Note that the honest prover in this construction runs in exponential
time, since she has to prove membership in PSPACE, but we can choose t
such that 2^t is significantly larger than the running time of the
honest prover).
We then define the notion of a probabilistically checkable argument
(PCA). This is a relaxation of the notion of probabilistically
checkable proof (PCP). It is defined analogously to PCP, except that
the soundness property is required to hold only computationally.
We consider the model where each verifier is associated with a public
key, and each PCA is verifier-dependent, i.e., it depends on the
verifier's public key. (The key does not need to be certified, and we
can assume that the verifier simply publishes it on his web-page). We
show that every NP language, verifiable by a poly-size formula, has a
PCA (with efficient honest prover) of size polynomial in the size of
the witness. This compares to the best PCPs that are of size
polynomial in the size of the instance (that may be significantly
larger). The number of queries to these PCAs is poly-logarithmic.
This result is proved via a general reduction that converts any
interactive-PCP (with certain properties) into a PCA, together with
a very recent interactive-PCP construction of Goldwasser et al.
The soundness property, in all our results, relies on exponential
hardness assumptions.
This is joint work with Ran Raz.
See other events that are part of Cryptography and Information Security Seminars 2007/2008
See other events happening in August 2008
