Hadar Strauss

Abstract of Master Thesis (Weizmann Inst., 2025)

On the Power of Computationally Sound Interactive Proofs of Proximity

Interactive proofs of proximity (IPPs) are a relaxation of interactive proofs, analogous to property testing, in which soundness is required to hold only for inputs that are $\epsilon$-far from the property being verified, where $\epsilon>0$ is a proximity parameter. In such proof systems, the verifier has oracle access to the input, and it engages in two types of activities before making its decision: querying the input oracle and communicating with the prover. The main objective is to achieve protocols where both the query and communication complexities are extremely low.

In this work, we focus on computationally sound IPPs (cs-IPPs). We study their power in two aspects:

• Query complexity: We show that, assuming the existence of collision-resistant hashing functions (CRHFs), any public-coin cs-IPP that has query complexity $q$ can be transformed into a cs-IPP that makes only $O(1/\epsilon)$ queries, while increasing the communication complexity by roughly $q$. If we further assume the existence of a good computational PIR (private information retrieval) scheme, then a similar transformation holds for general (i.e., possibly private-coin) cs-IPPs.
• Coordination: Aside from the low query complexity, the resulting cs-IPP has only minimal coordination between the verifier's two activities. The general definition of IPPs allows the verifier to fully coordinate its interaction with the prover and its queries to the input oracle. Goldreich, Rothblum, and Skverer (ITCS 2023) introduced two restricted models of IPPs that are minimally coordinated: The pre-coordinated model, where no information flows between the querying and interacting activities, but they may use a common source of randomness, and the isolated model, where the two activities are fully independent, each operating with a separate source of randomness.
  Our transformation shows that (under the aforementioned computational assumptions) any cs-IPP can be made to be in the pre-coordinated model, while preserving its efficiency. Hence, pre-coordinated cs-IPPs are essentially as powerful as general cs-IPPs.
  In contrast, we show that cs-IPPs in the isolated model are extremely limited, offering almost no advantage over property testers. Specifically, extending on a result shown by Goldreich et al. for unconditionally sound IPPs in the isolated model, we show that if a property has a cs-IPP in the isolated model that makes $q$ queries and uses $c>0$ bits of communication, then it has a tester with query complexity $O(c\cdot q)$.

Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, Nov 2025.

Available: the thesis (in PDF file).

Back to Oded Goldreich's homepage.