1 Search Results for "Skverer, Tal"

Document
DOI: 10.4230/LIPIcs.ITCS.2023.59
On Interactive Proofs of Proximity with Proof-Oblivious Queries

Authors: Oded Goldreich, Guy N. Rothblum, and Tal Skverer

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

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 between 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.
Cite as

Oded Goldreich, Guy N. Rothblum, and Tal Skverer. On Interactive Proofs of Proximity with Proof-Oblivious Queries. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 59:1-59:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{goldreich_et_al:LIPIcs.ITCS.2023.59,
  author =	{Goldreich, Oded and Rothblum, Guy N. and Skverer, Tal},
  title =	{{On Interactive Proofs of Proximity with Proof-Oblivious Queries}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{59:1--59:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.59},
  URN =		{urn:nbn:de:0030-drops-175625},
  doi =		{10.4230/LIPIcs.ITCS.2023.59},
  annote =	{Keywords: Complexity Theory, Property Testing, Interactive Proofs, Interactive Proofs of Proximity, Proof-Oblivious Queries}
}
  • Refine by Author
  • 1 Goldreich, Oded
  • 1 Rothblum, Guy N.
  • 1 Skverer, Tal

  • Refine by Classification
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Interactive proof systems

  • Refine by Keyword
  • 1 Complexity Theory
  • 1 Interactive Proofs
  • 1 Interactive Proofs of Proximity
  • 1 Proof-Oblivious Queries
  • 1 Property Testing

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact