Document Open Access Logo

Sample-Based Proofs of Proximity

Authors Guy Goldberg , Guy N. Rothblum

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.77.pdf
  • Filesize: 0.72 MB
  • 19 pages

Document Identifiers

Author Details

Guy Goldberg
  • Weizmann Institute of Science, Rehovot, Israel
Guy N. Rothblum
  • Weizmann Institute of Science, Rehovot, Israel

Funding

  • Goldberg, Guy: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 819702) and from the Israel Science Foundation (grant number 5219/17).
  • N. Rothblum, Guy: This project has 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.

Acknowledgements

We would like to thank Oded Goldreich, Shafi Goldwasser and Ron Rothblum for helpful and illuminating conversations and comments.

Cite AsGet BibTex

Guy Goldberg and Guy N. Rothblum. Sample-Based Proofs of Proximity. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 77:1-77:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.77

Abstract

Suppose we have random sampling access to a huge object, such as a graph or a database. Namely, we can observe the values of random locations in the object, say random records in the database or random edges in the graph. We cannot, however, query locations of our choice. Can we verify complex properties of the object using only this restricted sampling access? In this work, we initiate the study of sample-based proof systems, where the verifier is extremely constrained; Given an input, the verifier can only obtain samples of uniformly random and i.i.d. locations in the input string, together with the values at those locations. The goal is verifying complex properties in sublinear time, using only this restricted access. Following the literature on Property Testing and on Interactive Proofs of Proximity (IPPs), we seek proof systems where the verifier accepts every input that has the property, and with high probability rejects every input that is far from the property. We study both interactive and non-interactive sample-based proof systems, showing: - On the positive side, our main result is that rich families of properties / languages have sub-linear sample-based interactive proofs of proximity (SIPPs). We show that every language in NC has a SIPP, where the sample and communication complexities, as well as the verifier’s running time, are Õ(√n), and with polylog(n) communication rounds. We also show that every language that can be computed in polynomial-time and bounded-polynomial space has a SIPP, where the sample and communication complexities of the protocol, as well as the verifier’s running time are roughly √n, and with a constant number of rounds. This is achieved by constructing a reduction protocol from SIPPs to IPPs. With the aid of an untrusted prover, this reduction enables a restricted, sample-based verifier to simulate an execution of a (query-based) IPP, even though it cannot query the input. Applying the reduction to known query-based IPPs yields SIPPs for the families described above. - We show that every language with an adequate (query-based) property tester has a 1-round SIPP with constant sample complexity and logarithmic communication complexity. One such language is equality testing, for which we give an explicit and simple SIPP. - On the negative side, we show that interaction can be essential: we prove that there is no non-interactive sample-based proof of proximity for equality testing. - Finally, we prove that private coins can dramatically increase the power of SIPPs. We show a strong separation between the power of public-coin SIPPs and private-coin SIPPs for Equality Testing.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive proof systems
Keywords
  • Interactive Proof Systems
  • Sample-Based Access
  • Proofs of Proximity

Metrics

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

Related Versions

References

  1. László Babai and Shlomo Moran. Arthur-merlin games: A randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci., 36(2):254-276, 1988. URL: https://doi.org/10.1016/0022-0000(88)90028-1.
  2. 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.
  3. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 73-83. ACM, 1990. URL: https://doi.org/10.1145/100216.100225.
  4. Clément L. Canonne. A survey on distribution testing: Your data is big. but is it blue? Electron. Colloquium Comput. Complex., 22:63, 2015. URL: http://eccc.hpi-web.de/report/2015/063.
  5. 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. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.53.
  6. Anne Condon. Space-bounded probabilistic game automata. J. ACM, 38(2):472-494, 1991. URL: https://doi.org/10.1145/103516.128681.
  7. Anne Condon and Richard E. Ladner. Probabilistic game automata. J. Comput. Syst. Sci., 36(3):452-489, 1988. URL: https://doi.org/10.1016/0022-0000(88)90038-4.
  8. Anne Condon and Richard J. Lipton. On the complexity of space bounded interactive proofs (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 462-467. IEEE Computer Society, 1989. URL: https://doi.org/10.1109/SFCS.1989.63519.
  9. Cynthia Dwork and Larry J. Stockmeyer. Finite state verifiers I: the power of interaction. J. ACM, 39(4):800-828, 1992. URL: https://doi.org/10.1145/146585.146599.
  10. Cynthia Dwork and Larry J. Stockmeyer. Finite state verifiers II: zero knowledge. J. ACM, 39(4):829-858, 1992. URL: https://doi.org/10.1145/146585.146601.
  11. Funda Ergün, Ravi Kumar, and Ronitt Rubinfeld. Fast approximate probabilistically checkable proofs. Inf. Comput., 189(2):135-159, 2004. URL: https://doi.org/10.1016/j.ic.2003.09.005.
  12. Eldar Fischer, Yonatan Goldhirsh, and Oded Lachish. Partial tests, universal tests and decomposability. In Moni Naor, editor, Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 483-500. ACM, 2014. URL: https://doi.org/10.1145/2554797.2554841.
  13. Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781108135252.
  14. Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky. Testing monotonicity. Comb., 20(3):301-337, 2000. URL: https://doi.org/10.1007/s004930070011.
  15. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. URL: https://doi.org/10.1145/285055.285060.
  16. Oded Goldreich, Tom Gur, and Ron D. Rothblum. Proofs of proximity for context-free languages and read-once branching programs - (extended abstract). In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 666-677. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_54.
  17. Oded Goldreich and Dana Ron. On sample-based testers. ACM Trans. Comput. Theory, 8(2):7:1-7:54, 2016. URL: https://doi.org/10.1145/2898355.
  18. Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N. Rothblum. Verifying and decoding in constant depth. In David S. Johnson and Uriel Feige, editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 440-449. ACM, 2007. URL: https://doi.org/10.1145/1250790.1250855.
  19. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: interactive proofs for muggles. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 113-122. ACM, 2008. URL: https://doi.org/10.1145/1374376.1374396.
  20. 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.
  21. Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, and Amir Yehudayoff. Interactive proofs for verifying machine learning. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185 of LIPIcs, pages 41:1-41:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.41.
  22. 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.
  23. Tom Gur, Yang P. Liu, and Ron D. Rothblum. An exponential separation between MA and AM proofs of proximity. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 73:1-73:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.73.
  24. Tom Gur and Ron D. Rothblum. A hierarchy theorem for interactive proofs of proximity. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of LIPIcs, pages 39:1-39:43. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.39.
  25. 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.
  26. Yael Tauman Kalai and Ron D. Rothblum. Arguments of proximity - [extended abstract]. In Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II, volume 9216 of Lecture Notes in Computer Science, pages 422-442. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48000-7_21.
  27. Eyal Kaplan, Moni Naor, and Omer Reingold. Derandomized constructions of k-wise (almost) independent permutations. Algorithmica, 55(1):113-133, 2009. URL: https://doi.org/10.1007/s00453-008-9267-y.
  28. 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.
  29. Moni Naor and Guy N. Rothblum. The complexity of online memory checking. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pages 573-584. IEEE Computer Society, 2005. URL: https://doi.org/10.1109/SFCS.2005.71.
  30. Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 49-62. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897652.
  31. Noga Ron-Zewi and Ron Rothblum. Local proofs approaching the witness length. Electron. Colloquium Comput. Complex., page 127, 2019. URL: https://eccc.weizmann.ac.il/report/2019/127.
  32. Guy N. Rothblum and Ron D. Rothblum. Batch verification and proofs of proximity with polylog overhead. In Rafael Pass and Krzysztof Pietrzak, editors, Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part II, volume 12551 of Lecture Notes in Computer Science, pages 108-138. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-64378-2_5.
  33. 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.
  34. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. URL: https://doi.org/10.1137/S0097539793255151.
  35. Adi Shamir. IP = PSPACE. J. ACM, 39(4):869-877, 1992. URL: https://doi.org/10.1145/146585.146609.
  36. Leslie G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134-1142, 1984. URL: https://doi.org/10.1145/1968.1972.
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