## Delegation for Bounded Space

by Yael Tauman Kalai, Ran Raz, and Ron Rothblum

#### Oded's comments

This work concerns *two-message* interactive proof systems
(with computational soundness)
in which the verification time is almost linear
and the (honest) prover strategy can be
implemented in polynomial time.
Such proof systems are obtained for any set in SC
(see a more general and accurate stmt in the abstract).

The proof uses an odd model of MIP systems,
and shows that (1) a known transformation of MIP systems
to the desired interactive proof systems that may fail in
general is sound when applied to systems of this odd model,
and (2) that adeqaute schemes can be constructed in the odd model.
Hence, odd or not, this odd model (aka no-signaling) proved useful.

The authors believe that they can extend the result to any set in P;
the last details are currently being verified and a proof
will be posted soon (hopefully).

**Update (Dec'13):** The prophecy made in the prior paragraph was
just fulfilled; see
ECCC
TR13-183.

#### The original abstract

We construct a 1-round delegation scheme for every language computable
in time t=t(n) and space s=s(n),
where the running time of the prover is poly(t)
and the running time of the verifier is $\pl(t)\cdot(n + poly(s))$,
where $\pl(t)=\polylog t$.

The proof exploits a curious connection between the problem of
computation delegation and the model of multi-prover interactive proofs
that are sound against no-signaling (cheating) strategies, a model that
was studied in the context of multi-prover interactive proofs with
provers that share quantum entanglement, and is motivated by the
physical principle that information cannot travel faster than light.

For any language computable in time t=t(n) and space s=s(n), we
construct MIPs that are sound against no-signaling strategies, where
the running time of the provers is poly(t),
the number of provers is $\pl(t)\cdot s$,
and the running time of the verifier is $\pl(t)\cdot(s+n)$.

We then show how to use the method suggested by Aiello et-al (ICALP,
2000) to convert our MIP into a 1-round delegation scheme, by using a
computational private information retrieval (PIR) scheme. Thus,
assuming the existence of a sub-exponentially secure PIR scheme, we get
our 1-round delegation scheme.

Back to
list of Oded's choices.