I refer to the works
These works initiate a study of computationally sound variants of the notion of interactive proofs of proximity (IPP), demonstrate their power even when restricted to so-called pre-coordinated operation (of the interactive and querying modules), and their limitations in the even more restricted ``isolated'' operation (of these modules).
A word about the aforementioned restricted operation models in in place. The point is that, in an IPP system, the verifier conducts two different operations: It interacts with a potentially malicious prover as well as queries the input at locations of its choice. These two activities are carried out by two corresponding modules, which feed a final decisional model (see Sections 1.2 and 2 in HERE). In the isolated model, the former two modules are totally independented of one another, whereas in the pre-coordinated model these two modules share a random tape (but do not communicate with one another).
Using standard cryptographic assumptions (i.e., CRH), the first work shows that one can reduce the query complexity to $O(1/\eps)$ while essentially preserving other complexity measures. (The reduction of the query complexity was not stressed in the original work, since its focus was on showing that the restriction to the pre-coordinated model has little cost.) The second work shows that such a result is impossible for the isolated model, by showing that a problem that has polylog complexity in the pre-coordinated model cannot have such complexity in the isolated model.
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.
See ECCC TR24-131.
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 far from the property being verified. 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.
Of particular interest are IPPs in which the querying and the interacting activities are performed independently, with no information flow from one activity to the other. Such IPPs were systematically studied by Goldreich, Rothblum, and Skverer (ITCS 2023), who introduced two variants: the pre-coordinated model, where the querying and interacting activities 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.
We focus on what is possible under these models when soundness is relaxed to computational soundness. Our previous work (ECCC, TR24-131) showed that the pre-coordinated model becomes significantly more powerful under this relaxation. In this work, we consider the isolated model under the same relaxation and show a separation between the two models. We consider a property that, by our previous work, has a computationally sound IPP in the pre-coordinated model with poly-logarithmic complexities (assuming the existence of collision-resistant hashing functions), and show that any computationally sound IPP in the isolated model for this property must have either query complexity or communication complexity that is $n sup Omega(1)$, where n is the length of the input.
See ECCC TR25-097.