Document Open Access Logo

Zero-Knowledge Proofs of Proximity

Authors Itay Berman, Ron D. Rothblum, Vinod Vaikuntanathan

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.19.pdf
  • Filesize: 0.63 MB
  • 20 pages

Document Identifiers

Author Details

Itay Berman
Ron D. Rothblum
Vinod Vaikuntanathan

Cite AsGet BibTex

Itay Berman, Ron D. Rothblum, and Vinod Vaikuntanathan. Zero-Knowledge Proofs of Proximity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ITCS.2018.19

Abstract

Interactive proofs of proximity (IPPs) are interactive proofs in which the verifier runs in time sub-linear in the input length. Since the verifier cannot even read the entire input, following the property testing literature, we only require that the verifier reject inputs that are far from the language (and, as usual, accept inputs that are in the language). In this work, we initiate the study of zero-knowledge proofs of proximity (ZKPP). A ZKPP convinces a sub-linear time verifier that the input is close to the language (similarly to an IPP) while simultaneously guaranteeing a natural zero-knowledge property. Specifically, the verifier learns nothing beyond (1) the fact that the input is in the language, and (2) what it could additionally infer by reading a few bits of the input. Our main focus is the setting of statistical zero-knowledge where we show that the following hold unconditionally (where N denotes the input length): - Statistical ZKPPs can be sub-exponentially more efficient than property testers (or even non-interactive IPPs): We show a natural property which has a statistical ZKPP with a polylog(N) time verifier, but requires Omega(sqrt(N)) queries (and hence also runtime) for every property tester. - Statistical ZKPPs can be sub-exponentially less efficient than IPPs: We show a property which has an IPP with a polylog(N) time verifier, but cannot have a statistical ZKPP with even an N^(o(1)) time verifier. - Statistical ZKPPs for some graph-based properties such as promise versions of expansion and bipartiteness, in the bounded degree graph model, with polylog(N) time verifiers exist. Lastly, we also consider the computational setting where we show that: - Assuming the existence of one-way functions, every language computable either in (logspace uniform) NC or in SC, has a computational ZKPP with a (roughly) sqrt(N) time verifier. - Assuming the existence of collision-resistant hash functions, every language in NP has a statistical zero-knowledge argument of proximity with a polylog(N) time verifier.
Keywords
  • Property Testing
  • Interactive Proofs
  • Zero-Knowledge

Metrics

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

References

  1. Scott Aaronson. Impossibility of succinct quantum proofs for collision-freeness. Quantum Information & Computation, 12(1-2):21-28, 2012. URL: http://www.rintonpress.com/xxqic12/qic-12-12/0021-0028.pdf.
  2. Noga Alon, Michael Krivelevich, Ilan Newman, and Mario Szegedy. Regular languages are testable with a constant number of queries. SIAM J. Comput., 30(6):1842-1862, 2000. URL: http://dx.doi.org/10.1137/S0097539700366528.
  3. Benny Applebaum and Pavel Raykov. From private simultaneous messages to zero-information arthur-merlin protocols and back. In Eyal Kushilevitz and Tal Malkin, editors, Theory of Cryptography - 13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part II, volume 9563 of Lecture Notes in Computer Science, pages 65-82. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-662-49099-0_3.
  4. Mihir Bellare, Silvio Micali, and Rafail Ostrovsky. Perfect zero-knowledge in constant rounds. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 482-493. ACM Press, 1990. Google Scholar
  5. Mihir Bellare and Moti Yung. Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation. J. Cryptology, 9(3):149-166, 1996. Google Scholar
  6. Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Håstad, Joe Kilian, Silvio Micali, and Phillip Rogaway. Everything provable is provable in zero-knowledge. In Shafi Goldwasser, editor, Advances in Cryptology - CRYPTO '88, 8th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1988, Proceedings, volume 403 of Lecture Notes in Computer Science, pages 37-56. Springer, 1988. URL: http://dx.doi.org/10.1007/0-387-34799-2_4.
  7. Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. On probabilistic checking in perfect zero knowledge. IACR Cryptology ePrint Archive, 2016:988, 2016. URL: http://eprint.iacr.org/2016/988.
  8. Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, and Madars Virza. Quasi-linear size zero knowledge from linear-algebraic pcps. In Eyal Kushilevitz and Tal Malkin, editors, Theory of Cryptography - 13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part II, volume 9563 of Lecture Notes in Computer Science, pages 33-64. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-662-49099-0_2.
  9. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In Martin Hirt and Adam D. Smith, editors, Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part II, volume 9986 of Lecture Notes in Computer Science, pages 31-60, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53644-5_2.
  10. Itay Berman, Ron D. Rothblum, and Vinod Vaikuntanathan. Zero-knowledge proofs of proximity. IACR Cryptology ePrint Archive, 2017:114, 2017. URL: http://eprint.iacr.org/2017/114.
  11. Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. Computational Complexity, 21(2):311-358, 2012. URL: http://dx.doi.org/10.1007/s00037-012-0040-x.
  12. Manuel Blum. Coin flipping by telephone. In Advances in Cryptology - CRYPTO'81, pages 11-15, 1981. Google Scholar
  13. Ran Canetti and Amit Lichtenberg, 2017. Unpublished manuscript. Google Scholar
  14. Alessandro Chiesa, Michael A. Forbes, and Nicholas Spooner. A zero knowledge sumcheck and its applications. Electronic Colloquium on Computational Complexity (ECCC), 24:57, 2017. URL: https://eccc.weizmann.ac.il/report/2017/057.
  15. Artur Czumaj and Christian Sohler. Testing expansion in bounded-degree graphs. Combinatorics, Probability & Computing, 19(5-6):693-709, 2010. URL: http://dx.doi.org/10.1017/S096354831000012X.
  16. Funda Ergün, Ravi Kumar, and Ronitt Rubinfeld. Fast approximate probabilistically checkable proofs. Inf. Comput., 189(2):135-159, 2004. URL: http://dx.doi.org/10.1016/j.ic.2003.09.005.
  17. Uriel Feige, Dror Lapidot, and Adi Shamir. Multiple non-interactive zero knowledge proofs under general assumptions. sicomp, 1999. Preliminary version in FOCS'90. Google Scholar
  18. 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: http://dx.doi.org/10.1145/2554797.2554841.
  19. Oded Goldreich. Foundations of Cryptography: Basic Tools. Cambridge University Press, 2001. Google Scholar
  20. Oded Goldreich. Introduction to Property Testing. forthcoming (http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html), 2016.
  21. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. URL: http://dx.doi.org/10.1145/285055.285060.
  22. Oded Goldreich and Tom Gur. Universal locally testable codes. Electronic Colloquium on Computational Complexity (ECCC), 23:42, 2016. URL: http://eccc.hpi-web.de/report/2016/042.
  23. 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: http://dx.doi.org/10.1007/978-3-662-47672-7_54.
  24. Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, pages 691-729, 1991. Preliminary version in FOCS'86. Google Scholar
  25. Oded Goldreich and Erez Petrank. Quantifying knowledge complexity. Computational Complexity, 8(1):50-98, 1999. URL: http://dx.doi.org/10.1007/s000370050019.
  26. Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):302-343, 2002. URL: http://dx.doi.org/10.1007/s00453-001-0078-7.
  27. Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. In Oded Goldreich, editor, Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, volume 6650 of Lecture Notes in Computer Science, pages 68-75. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22670-0_9.
  28. Oded Goldreich and Ron D. Rothblum. Enhancements of trapdoor permutations. J. Cryptology, 26(3):484-512, 2013. URL: http://dx.doi.org/10.1007/s00145-012-9131-8.
  29. Oded Goldreich, Amit Sahai, and Salil P. Vadhan. Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In Jeffrey Scott Vitter, editor, Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 399-408. ACM, 1998. URL: http://dx.doi.org/10.1145/276698.276852.
  30. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. sicomp, pages 186-208, 1989. Preliminary version in STOC'85. Google Scholar
  31. Mika Göös, Toniann Pitassi, and Thomas Watson. Zero-information protocols and unambiguity in arthur-merlin communication. Algorithmica, 76(3):684-719, 2016. URL: http://dx.doi.org/10.1007/s00453-015-0104-9.
  32. Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, and Amit Sahai. Interactive locking, zero-knowledge pcps, and unconditional cryptography. In Tal Rabin, editor, Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings, volume 6223 of Lecture Notes in Computer Science, pages 173-190. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14623-7_10.
  33. Tom Gur and Ron D. Rothblum, 2015. Unpublished observation. Google Scholar
  34. Tom Gur and Ron D. Rothblum. Non-interactive proofs of proximity. Computational Complexity, pages 1-109, 2016. URL: http://dx.doi.org/10.1007/s00037-016-0136-9.
  35. Tom Gur and Ron D. Rothblum. A hierarchy theorem for interactive proofs of proximity. In Proceedings of the 2017 ACM Conference on Innovations in Theoretical Computer Science, Berkeley, CA, USA, January 9-11, 2016, 2017. Google Scholar
  36. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Zero-knowledge proofs from secure multiparty computation. SIAM J. Comput., 39(3):1121-1152, 2009. URL: http://dx.doi.org/10.1137/080725398.
  37. Yuval Ishai and Mor Weiss. Probabilistically checkable proofs of proximity with zero-knowledge. In Yehuda Lindell, editor, Theory of Cryptography - 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings, volume 8349 of Lecture Notes in Computer Science, pages 121-145. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-642-54242-8_6.
  38. Yuval Ishai, Mor Weiss, and Guang Yang. Making the best of a leaky situation: Zero-knowledge pcps from leakage-resilient circuits. In Eyal Kushilevitz and Tal Malkin, editors, Theory of Cryptography - 13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part II, volume 9563 of Lecture Notes in Computer Science, pages 3-32. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-662-49099-0_1.
  39. Toshiya Itoh, Yuji Ohta, and Hiroki Shizuya. A language-dependent cryptographic primitive. Journal of Cryptology, pages 37-49, 1997. Google Scholar
  40. Yael Tauman Kalai and Ran Raz. Interactive PCP. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II - Track B: Logic, Semantics, and Theory of Programming & Track C: Security and Cryptography Foundations, volume 5126 of Lecture Notes in Computer Science, pages 536-547. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-70583-3_44.
  41. 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: http://dx.doi.org/10.1007/978-3-662-48000-7_21.
  42. Satyen Kale and C. Seshadhri. An expansion tester for bounded degree graphs. SIAM J. Comput., 40(3):709-720, 2011. URL: http://dx.doi.org/10.1137/100802980.
  43. Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC), pages 723-732, 1992. Google Scholar
  44. Joe Kilian, Erez Petrank, and Gábor Tardos. Probabilistically checkable proofs with zero knowledge. In Frank Thomson Leighton and Peter W. Shor, editors, Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 496-505. ACM, 1997. URL: http://dx.doi.org/10.1145/258533.258643.
  45. Silvio Micali and Rafael Pass. Precise zero knowledge. http://www.cs.cornell.edu/~rafael/papers/preciseZK.pdf, 2007.
  46. Daniele Micciancio and Salil Vadhan. Statistical zero-knowledge proofs with efficient provers: lattice problems and more. In crypto03, pages 282-298, 2003. Google Scholar
  47. Asaf Nachmias and Asaf Shapira. Testing the expansion of a graph. Inf. Comput., 208(4):309-314, 2010. URL: http://dx.doi.org/10.1016/j.ic.2009.09.002.
  48. Minh-Huyen Nguyen and Salil Vadhan. Zero knowledge with efficient provers. In stoc38, pages 287-295, 2006. Google Scholar
  49. Shien Jin Ong and Salil P. Vadhan. An equivalence between zero knowledge and commitments. In Ran Canetti, editor, Theory of Cryptography, Fifth Theory of Cryptography Conference, TCC 2008, New York, USA, March 19-21, 2008., volume 4948 of Lecture Notes in Computer Science, pages 482-500. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-78524-8_27.
  50. 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: http://dx.doi.org/10.1145/2897518.2897652.
  51. Guy N. Rothblum, Salil P. Vadhan, and Avi Wigderson. Interactive proofs of proximity: delegating computation in sublinear time. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 793-802, 2013. Google Scholar
  52. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. URL: http://dx.doi.org/10.1137/S0097539793255151.
  53. Salil P. Vadhan. A Study of Statistical Zero-Knowledge Proofs. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 1999. Google Scholar
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