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 #3 to TR22-124 | 17th November 2022 18:06

On Interactive Proofs of Proximity with Proof-Oblivious Queries

RSS-Feed




Revision #3
Authors: Oded Goldreich, Guy Rothblum, Tal Skverer
Accepted on: 17th November 2022 18:06
Downloads: 10
Keywords: 


Abstract:

Interactive proofs of proximity (IPPs) offer ultra-fast
approximate verification of assertions regarding their input,
where ultra-fast means that only a small portion of the input is read
and approximate verification is analogous to the notion of
approximate decision that underlies property testing.
Specifically, in an IPP, the prover can make the verifier
accept each input in the property, but cannot fool the verifier
into accepting an input that is far from the property
(except for with small probability).

The verifier in an IPP system engages in two very different types
of activities: interacting with an untrusted prover, and querying its input.
The definition allows for arbitrary coordination between these two activities,
but keeping them separate is both conceptually interesting
and necessary for important applications
such as addressing temporal considerations
(i.e., at what time is each of the services available)
and facilitating the construction of zero-knowledge schemes.
In this work we embark on a systematic study of IPPs
with proof-oblivious queries, where the queries should not be affected
by the interaction with the prover.
We assign the query and interaction activities to separate modules,
and consider different limitations on their coordination.

The most strict limitation requires these activities to
be totally isolated from one another; they just feed
their views to a separate deciding module.
We show that such systems can be efficiently emulated by standard testers.

Going to the other extreme, we only disallow information
to flow from the interacting module to the querying module,
but allow free information flow in the other direction.
We show that extremely efficient one-round (i.e., two-message) systems
of such type can be used to verify properties that are extremely
hard to test (without the help of a prover).
That is, the complexity of verifying can be polylogarithmic in the complexity of testing.
This stands in contrast the MAPs (viewed as $1/2$-round systems)
in which proof-oblivious queries are as limited as our isolated model.

Our focus is on an intermediate model that allows
shared randomness among the querying and interacting modules
but no information flow between them.
In this case we show
that 1-round systems are efficiently emulated by standard testers
but $3/2$-round systems of extremely low complexity
exist for properties that are extremely hard to test.
One additional result about this model is that it can
efficiently emulate any IPP for any property of low-degree polynomials.



Changes to previous version:

Adding an open problem section (Sec 6) and correcting the last couple of paragraphs in Sec 1.6.


Revision #2 to TR22-124 | 12th September 2022 19:39

On Interactive Proofs of Proximity with Proof-Oblivious Queries





Revision #2
Authors: Oded Goldreich, Guy Rothblum, Tal Skverer
Accepted on: 12th September 2022 19:39
Downloads: 100
Keywords: 


Abstract:

Interactive proofs of proximity (IPPs) offer ultra-fast
approximate verification of assertions regarding their input,
where ultra-fast means that only a small portion of the input is read
and approximate verification is analogous to the notion of
approximate decision that underlies property testing.
Specifically, in an IPP, the prover can make the verifier
accept each input in the property, but cannot fool the verifier
into accepting an input that is far from the property
(except for with small probability).

The verifier in an IPP system engages in two very different types
of activities: interacting with an untrusted prover, and querying its input.
The definition allows for arbitrary coordination between these two activities,
but keeping them separate is both conceptually interesting
and necessary for important applications
such as addressing temporal considerations
(i.e., at what time is each of the services available)
and facilitating the construction of zero-knowledge schemes.
In this work we embark on a systematic study of IPPs
with proof-oblivious queries, where the queries should not be affected
by the interaction with the prover.
We assign the query and interaction activities to separate modules,
and consider different limitations on their coordination.

The most strict limitation requires these activities to
be totally isolated from one another; they just feed
their views to a separate deciding module.
We show that such systems can be efficiently emulated by standard testers.

Going to the other extreme, we only disallow information
to flow from the interacting module to the querying module,
but allow free information flow in the other direction.
We show that extremely efficient one-round (i.e., two-message) systems
of such type can be used to verify properties that are extremely
hard to test (without the help of a prover).
That is, the complexity of verifying can be polylogarithmic in the complexity of testing.
This stands in contrast the MAPs (viewed as $1/2$-round systems)
in which proof-oblivious queries are as limited as our isolated model.

Our focus is on an intermediate model that allows
shared randomness among the querying and interacting modules
but no information flow between them.
In this case we show
that 1-round systems are efficiently emulated by standard testers
but $3/2$-round systems of extremely low complexity
exist for properties that are extremely hard to test.
One additional result about this model is that it can
efficiently emulate any IPP for any property of low-degree polynomials.



Changes to previous version:

Correcting Guy's affiliation.


Revision #1 to TR22-124 | 9th September 2022 11:39

On Interactive Proofs of Proximity with Proof-Oblivious Queries





Revision #1
Authors: Oded Goldreich, Guy Rothblum, Tal Skverer
Accepted on: 9th September 2022 11:39
Downloads: 83
Keywords: 


Abstract:

Interactive proofs of proximity (IPPs) offer ultra-fast
approximate verification of assertions regarding their input,
where ultra-fast means that only a small portion of the input is read
and approximate verification is analogous to the notion of
approximate decision that underlies property testing.
Specifically, in an IPP, the prover can make the verifier
accept each input in the property, but cannot fool the verifier
into accepting an input that is far from the property
(except for with small probability).

The verifier in an IPP system engages in two very different types
of activities: interacting with an untrusted prover, and querying its input.
The definition allows for arbitrary coordination between these two activities,
but keeping them separate is both conceptually interesting
and necessary for important applications
such as addressing temporal considerations
(i.e., at what time is each of the services available)
and facilitating the construction of zero-knowledge schemes.
In this work we embark on a systematic study of IPPs
with proof-oblivious queries, where the queries should not be affected
by the interaction with the prover.
We assign the query and interaction activities to separate modules,
and consider different limitations on their coordination.

The most strict limitation requires these activities to
be totally isolated from one another; they just feed
their views to a separate deciding module.
We show that such systems can be efficiently emulated by standard testers.

Going to the other extreme, we only disallow information
to flow from the interacting module to the querying module,
but allow free information flow in the other direction.
We show that extremely efficient one-round (i.e., two-message) systems
of such type can be used to verify properties that are extremely
hard to test (without the help of a prover).
That is, the complexity of verifying can be polylogarithmic in the complexity of testing.
This stands in contrast the MAPs (viewed as $1/2$-round systems)
in which proof-oblivious queries are as limited as our isolated model.

Our focus is on an intermediate model that allows
shared randomness among the querying and interacting modules
but no information flow between them.
In this case we show
that 1-round systems are efficiently emulated by standard testers
but $3/2$-round systems of extremely low complexity
exist for properties that are extremely hard to test.
One additional result about this model is that it can
efficiently emulate any IPP for any property of low-degree polynomials.



Changes to previous version:

No change. The name of the third author was omitted from the record, and added now. Hopefully it will work.


Paper:

TR22-124 | 9th September 2022 11:31

On Interactive Proofs of Proximity with Proof-Oblivious Queries





TR22-124
Authors: Oded Goldreich, Guy Rothblum, Tal Skverer
Publication: 9th September 2022 11:31
Downloads: 66
Keywords: 


Abstract:

Interactive proofs of proximity (IPPs) offer ultra-fast
approximate verification of assertions regarding their input,
where ultra-fast means that only a small portion of the input is read
and approximate verification is analogous to the notion of
approximate decision that underlies property testing.
Specifically, in an IPP, the prover can make the verifier
accept each input in the property, but cannot fool the verifier
into accepting an input that is far from the property
(except for with small probability).

The verifier in an IPP system engages in two very different types
of activities: interacting with an untrusted prover, and querying its input.
The definition allows for arbitrary coordination between these two activities,
but keeping them separate is both conceptually interesting
and necessary for important applications
such as addressing temporal considerations
(i.e., at what time is each of the services available)
and facilitating the construction of zero-knowledge schemes.
In this work we embark on a systematic study of IPPs
with proof-oblivious queries, where the queries should not be affected
by the interaction with the prover.
We assign the query and interaction activities to separate modules,
and consider different limitations on their coordination.

The most strict limitation requires these activities to
be totally isolated from one another; they just feed
their views to a separate deciding module.
We show that such systems can be efficiently emulated by standard testers.

Going to the other extreme, we only disallow information
to flow from the interacting module to the querying module,
but allow free information flow in the other direction.
We show that extremely efficient one-round (i.e., two-message) systems
of such type can be used to verify properties that are extremely
hard to test (without the help of a prover).
That is, the complexity of verifying can be polylogarithmic in the complexity of testing.
This stands in contrast the MAPs (viewed as $1/2$-round systems)
in which proof-oblivious queries are as limited as our isolated model.

Our focus is on an intermediate model that allows
shared randomness among the querying and interacting modules
but no information flow between them.
In this case we show
that 1-round systems are efficiently emulated by standard testers
but $3/2$-round systems of extremely low complexity
exist for properties that are extremely hard to test.
One additional result about this model is that it can
efficiently emulate any IPP for any property of low-degree polynomials.



ISSN 1433-8092 | Imprint