Speaker: Ron Rothblum (WIS)
Title: Proofs and Arguments of Proximity: Verifying Correctness in Sub-Linear Time
Abstract:
An interactive proof of proximity (IPP) is an interactive
protocol in which a prover tries to convince a sublinear-time
verifier that x \in L. Since the verifier runs in sublinear-time,
following the property testing literature, the verifier is only
required to reject inputs that are far from L. In a recent
work, (Guy) Rothblum, Vadhan and Wigderson (STOC, 2013) constructed
an IPP for every language computable by a low depth circuit.
In this work we consider the computational analogue, where
soundness is required to hold only against a computationally
bounded cheating prover. We call such protocols interactive
arguments of proximity.
Assuming the existence of a sub-exponentially secure FHE
scheme, we construct a one-round argument of proximity for
every language computable in time t, where the running time
of the verifier is o(n) + polylog(t) and the running time of
the prover is poly(t).
As our second result, assuming sufficiently hard cryptographic
PRGs, we give a lower bound, showing that the parameters obtained
both in the IPPs of Rothblum et-al, and in our arguments of
proximity, are close to optimal.
Based on joint work with Yael Kalai.