Interactive proofs of proximity (IPPs) for a property are relaxed proof systems analogous to property testers in which the goal is for the verifier to be convinced to accept inputs that are in the property, and to not be fooled into accepting inputs that are far from the property.

The general definition of IPPs allows the verifier to fully coordinate its interaction with the prover and its queries to the input oracle. In contrast, in IPPs with proof-oblivious queries in the pre-coordinated model, the verifier is decomposed into separate modules, one interacting with the prover and another querying the input, such that no information flow between the modules is allowed. The only coordination that is allowed between the modules is through shared randomness.

Goldreich, Rothblum, and Skverer (ECCC, TR22-124) showed that while the pre-coordinated model is significantly more powerful than standard property testers, it is also considerably limited compared to general IPPs. In this work we show that if we relax the soundness condition to computational soundness, then the pre-coordinated model becomes significantly stronger. Specifically, assuming the existence of collision-resistant hashing functions, we obtain a computationally sound (public-coin) IPP in the pre-coordinated model for any property that has a general computationally sound public-coin IPP, such that the complexities of the resulting IPP are related to the complexities of the original IPP.

Corrected a mistake in the proof of Lemma 2.3 and fixed some typos.

Interactive proofs of proximity (IPPs) for a property are relaxed proof systems analogous to property testers in which the goal is for the verifier to be convinced to accept inputs that are in the property, and to not be fooled into accepting inputs that are far from the property.

The general definition of IPPs allows the verifier to fully coordinate its interaction with the prover and its queries to the input oracle. In contrast, in IPPs with proof-oblivious queries in the pre-coordinated model, the verifier is decomposed into separate modules, one interacting with the prover and another querying the input, such that no information flow between the modules is allowed. The only coordination that is allowed between the modules is through shared randomness.

Goldreich, Rothblum, and Skverer (ECCC, TR22-124) showed that while the pre-coordinated model is significantly more powerful than standard property testers, it is also considerably limited compared to general IPPs. In this work we show that if we relax the soundness condition to computational soundness, then the pre-coordinated model becomes significantly stronger. Specifically, assuming the existence of collision-resistant hashing functions, we obtain a computationally sound (public-coin) IPP in the pre-coordinated model for any property that has a general computationally sound public-coin IPP, such that the complexities of the resulting IPP are related to the complexities of the original IPP.