Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-131 | 20th September 2024 20:42

Emulating Computationally Sound Public-Coin IPPs in the Pre-Coordinated Model

RSS-Feed




Revision #1
Authors: Hadar Strauss
Accepted on: 20th September 2024 20:43
Downloads: 29
Keywords: 


Abstract:

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.



Changes to previous version:

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


Paper:

TR24-131 | 5th September 2024 17:55

Emulating Computationally Sound Public-Coin IPPs in the Pre-Coordinated Model





TR24-131
Authors: Hadar Strauss
Publication: 5th September 2024 18:03
Downloads: 87
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint