Document Open Access Logo

On Interactive Proofs of Proximity with Proof-Oblivious Queries

Authors Oded Goldreich, Guy N. Rothblum, Tal Skverer

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.59.pdf
  • Filesize: 0.71 MB
  • 16 pages

Document Identifiers

Author Details

Oded Goldreich
  • Weizmann Institute of Science, Rehovot, Israel
Guy N. Rothblum
  • Apple, Cupertino, CA, USA
Tal Skverer
  • Weizmann Institute of Science, Rehovot, Israel

Funding

  • Goldreich, Oded: Partially supported by the Israel Science Foundation (grant No. 1041/18) and by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 819702).
  • Rothblum, Guy N.: Received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 819702), from the Israel Science Foundation (grant number 5219/17), and from the Simons Foundation Collaboration on the Theory of Algorithmic Fairness.
  • Skverer, Tal: Partially supported by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness.

Acknowledgements

We are grateful to Ron Rothblum for helpful discussions.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ITCS.2023.59

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Theory of computation → Interactive proof systems
Keywords
  • Complexity Theory
  • Property Testing
  • Interactive Proofs
  • Interactive Proofs of Proximity
  • Proof-Oblivious Queries

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, 1998. URL: https://doi.org/10.1145/278298.278306.
  2. László Babai and Peter G. Kimmel. Randomized simultaneous messages: Solution of a problem of yao in communication complexity. In Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, Ulm, Germany, June 24-27, 1997, pages 239-246. IEEE Computer Society, 1997. URL: https://doi.org/10.1109/CCC.1997.612319.
  3. Mihir Bellare, Oded Goldreich, and Shafi Goldwasser. Randomness in interactive proofs. Comput. Complex., 3:319-354, 1993. URL: https://doi.org/10.1007/BF01275487.
  4. Itay Berman, Ron D. Rothblum, and Vinod Vaikuntanathan. Zero-knowledge proofs of proximity. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 19:1-19:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.19.
  5. Amit Chakrabarti, Graham Cormode, Andrew McGregor, and Justin Thaler. Annotations in data streams. ACM Trans. Algorithms, 11(1):7:1-7:30, 2014. URL: https://doi.org/10.1145/2636924.
  6. Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian. Verifiable stream computation and arthur-merlin communication. SIAM J. Comput., 48(4):1265-1299, 2019. URL: https://doi.org/10.1137/17M112289X.
  7. Alessandro Chiesa and Tom Gur. Proofs of proximity for distribution testing. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 53:1-53:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. See full version in ECCC, TR17-155, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.53.
  8. Graham Cormode, Justin Thaler, and Ke Yi. Verifying computations with streaming interactive proofs. Proc. VLDB Endow., 5(1):25-36, 2011. URL: https://doi.org/10.14778/2047485.2047488.
  9. Funda Ergün, Ravi Kumar, and Ronitt Rubinfeld. Fast approximate pcps. In Jeffrey Scott Vitter, Lawrence L. Larmore, and Frank Thomson Leighton, editors, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA, pages 41-50. ACM, 1999. URL: https://doi.org/10.1145/301250.301267.
  10. Uriel Feige, Dror Lapidot, and Adi Shamir. Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput., 29(1):1-28, 1999. URL: https://doi.org/10.1137/S0097539792230010.
  11. Guy Goldberg and Guy N. Rothblum. Sample-based proofs of proximity. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 77:1-77:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.77.
  12. Oded Goldreich. Modern Cryptography, Probabilistic Proofs and Pseudorandomness, volume 17 of Algorithms and Combinatorics. Springer, 1998. URL: https://doi.org/10.1007/978-3-662-12521-2.
  13. Oded Goldreich. The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press, 2001. URL: https://doi.org/10.1017/CBO9780511546891.
  14. Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781108135252.
  15. Oded Goldreich, Guy N. Rothblum, and Tal Skverer. On interactive proofs of proximity with proof-oblivious queries. Electron. Colloquium Comput. Complex., TR22-124, 2022. URL: https://eccc.weizmann.ac.il/report/2022/124, URL: http://arxiv.org/abs/TR22-124.
  16. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186-208, 1989. URL: https://doi.org/10.1137/0218012.
  17. Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 59-68. ACM, 1986. URL: https://doi.org/10.1145/12130.12137.
  18. Tom Gur, Yang P. Liu, and Ron D. Rothblum. An exponential separation between MA and AM proofs of proximity. Comput. Complex., 30(2):12, 2021. URL: https://doi.org/10.1007/s00037-021-00212-3.
  19. Tom Gur and Ron D. Rothblum. Non-interactive proofs of proximity. Comput. Complex., 27(1):99-207, 2018. URL: https://doi.org/10.1007/s00037-016-0136-9.
  20. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. ACM, 39(4):859-868, 1992. URL: https://doi.org/10.1145/146585.146605.
  21. Guy N. Rothblum, Salil P. Vadhan, and Avi Wigderson. Interactive proofs of proximity: delegating computation in sublinear time. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 793-802. ACM, 2013. URL: https://doi.org/10.1145/2488608.2488709.
  22. Salil P. Vadhan. On transformation of interactive proofs that preserve the prover’s complexity. In F. Frances Yao and Eugene M. Luks, editors, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 200-207. ACM, 2000. URL: https://doi.org/10.1145/335305.335330.
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