Document Open Access Logo

On the Impossibility of Probabilistic Proofs in Relativized Worlds

Authors Alessandro Chiesa, Siqi Liu

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.57.pdf
  • Filesize: 0.7 MB
  • 30 pages

Document Identifiers

Author Details

Alessandro Chiesa
  • UC Berkeley, CA, USA
Siqi Liu
  • UC Berkeley, CA, USA

Funding

This research was supported in part by: the Berkeley Haas Blockchain Initiative, and donations from the Ethereum Foundation and the Interchain Foundation.

Cite AsGet BibTex

Alessandro Chiesa and Siqi Liu. On the Impossibility of Probabilistic Proofs in Relativized Worlds. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 57:1-57:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.57

Abstract

We initiate the systematic study of probabilistic proofs in relativized worlds, where the goal is to understand, for a given oracle, the possibility of "non-trivial" proof systems for deterministic or nondeterministic computations that make queries to the oracle. This question is intimately related to a recent line of work that seeks to improve the efficiency of probabilistic proofs for computations that use functionalities such as cryptographic hash functions and digital signatures, by instantiating them via constructions that are "friendly" to known constructions of probabilistic proofs. Informally, negative results about probabilistic proofs in relativized worlds provide evidence that this line of work is inherent and, conversely, positive results provide a way to bypass it. We prove several impossibility results for probabilistic proofs relative to natural oracles. Our results provide strong evidence that tailoring certain natural functionalities to known probabilistic proofs is inherent.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • probabilistically checkable proofs
  • relativization

Metrics

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

Related Versions

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: A New Barrier in Complexity Theory. ACM Transactions on Computation Theory, 1(1):2:1-2:54, 2009. Google Scholar
  2. Martin R Albrecht, Carlos Cid, Lorenzo Grassi, Dmitry Khovratovich, Reinhard Lüftenegger, Christian Rechberger, and Markus Schofnegger. Algebraic Cryptanalysis of STARK-Friendly Designs: Application to MARVELlous and MiMC. IACR Cryptology ePrint Archive, Report 2019/419, 2019. Google Scholar
  3. Martin R Albrecht, Lorenzo Grassi, Léo Perrin, Sebastian Ramacher, Christian Rechberger, Dragos Rotaru, Arnab Roy, and Markus Schofnegger. Feistel Structures for MPC, and More. IACR Cryptology ePrint Archive, Report 2019/397, 2019. Google Scholar
  4. Abdelrahaman Aly, Tomer Ashur, Eli Ben-Sasson, Siemen Dhooghe, and Alan Szepieniec. Efficient Symmetric Primitives for Advanced Cryptographic Protocols. IACR Cryptology ePrint Archive, Report 2019/426, 2019. Google Scholar
  5. Sanjeev Arora, Russell Impagliazzo, and Umesh Vazirani. Relativizing versus nonrelativizing techniques: The role of local checkability. Manuscript, 1992. Google Scholar
  6. Tomer Ashur and Siemen Dhooghe. MARVELlous: a STARK-friendly family of cryptographic primitives. IACR Cryptology ePrint Archive, Report 2018/1098, 2018. Google Scholar
  7. Bariş Aydınlıoğlu and Eric Bach. Affine Relativization: Unifying the Algebrization and Relativization Barriers. ACM Transactions on Computation Theory, 10(1):1:1-1:67, 2018. Google Scholar
  8. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC '91, pages 21-32, 1991. Google Scholar
  9. Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P = ? NP question. SIAM Journal on Computing, 4(4):431-442, 1975. Google Scholar
  10. Eli Ben-Sasson, Iddo Bentov, Alessandro Chiesa, Ariel Gabizon, Daniel Genkin, Matan Hamilis, Evgenya Pergament, Michael Riabzev, Mark Silberstein, Eran Tromer, and Madars Virza. Computational integrity with a public random string from quasi-linear PCPs. In Proceedings of the 36th Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT '17, pages 551-579, 2017. Google Scholar
  11. Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable Zero Knowledge with No Trusted Setup. In Proceedings of the 39th Annual International Cryptology Conference, CRYPTO '19, pages 733-764, 2019. Google Scholar
  12. Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, and Michael Riabzev. Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming, ICALP '18, pages 14:1-14:17, 2018. Google Scholar
  13. Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. Zero Knowledge Protocols from Succinct Constraint Detection. In Proceedings of the 15th Theory of Cryptography Conference, TCC '17, pages 172-206, 2017. Google Scholar
  14. Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. Interactive Oracle Proofs with Constant Rate and Query Complexity. In Proceedings of the 44th International Colloquium on Automata, Languages and Programming, ICALP '17, pages 40:1-40:15, 2017. Google Scholar
  15. Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, and Madars Virza. Quasilinear-Size Zero Knowledge from Linear-Algebraic PCPs. In Proceedings of the 13th Theory of Cryptography Conference, TCC '16-A, pages 33-64, 2016. Google Scholar
  16. Eli Ben-Sasson, Alessandro Chiesa, Lior Goldberg, Tom Gur, Michael Riabzev, and Nicholas Spooner. Linear-Size Constant-Query IOPs for Delegating Computation. In Proceedings of the 17th Theory of Cryptography Conference, TCC '19, 2019. Google Scholar
  17. Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent Succinct Arguments for R1CS. In Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT '19, pages 103-128, 2019. Full version available at URL: https://eprint.iacr.org/2018/828.
  18. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive Oracle Proofs. In Proceedings of the 14th Theory of Cryptography Conference, TCC '16-B, pages 31-60, 2016. Google Scholar
  19. Eli Ben-Sasson and Madhu Sudan. Short PCPs with Polylog Query Complexity. SIAM Journal on Computing, 38(2):551-607, 2008. Preliminary version appeared in STOC '05. Google Scholar
  20. Charles H Bennett and John Gill. Relative to a Random Oracle A, P^A ̸= NP^A ̸= co-NP^A with Probability 1. SIAM Journal on Computing, 10(1):96-113, 1981. Google Scholar
  21. Dan Boneh and Richard J. Lipton. Algorithms for Black-Box Fields and their Application to Cryptography. In Proceedings of the 16th Annual International Cryptology Conference, CRYPTO '96, pages 283-297, 1996. Google Scholar
  22. Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, and Pankaj Rohatgi. The random oracle hypothesis is false. Journal of Computer and System Sciences, 49(1):24-39, 1994. Google Scholar
  23. Alan Cobham. The Intrinsic Computational Difficulty of Functions. In Proceedings of the 1964 International Congress in Logic, Methodology and Philosophy of Science, pages 24-30, 1965. Google Scholar
  24. Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM, 54(3):12, 2007. Google Scholar
  25. Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy. Approximating clique is almost NP-complete. In Proceedings of the 32nd Annual Symposium of Foundations of Computer Science, pages 2-12, 1991. Google Scholar
  26. Amos Fiat and Adi Shamir. How to prove yourself: practical solutions to identification and signature problems. In Proceedings of the 6th Annual International Cryptology Conference, CRYPTO '86, pages 186-194, 1986. Google Scholar
  27. Lance Fortnow. The Role of Relativization in Complexity Theory. Bulletin of the EATCS, 52:229-243, 1994. Google Scholar
  28. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186-208, 1989. Preliminary version appeared in STOC '85. Google Scholar
  29. Lorenzo Grassi, Daniel Kales, Dmitry Khovratovich, Arnab Roy, Christian Rechberger, and Markus Schofnegger. Starkad and Poseidon: New Hash Functions for Zero Knowledge Proof Systems. IACR Cryptology ePrint Archive, Report 2019/458, 2019. Google Scholar
  30. Lorenzo Grassi, Reinhard Lüftenegger, Christian Rechberger, Dragos Rotaru, and Markus Schofnegger. On a Generalization of Substitution-Permutation Networks: The HADES Design Strategy. Cryptology ePrint Archive, Report 2019/1107, 2019. Google Scholar
  31. Juris Hartmanis, Richard Chang, Suresh Chari, Desh Ranjan, and Pankaj Rohatgi. Relativization: A revisionistic retrospective. In Bulletin of the EATCS, 1992. Google Scholar
  32. Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. An axiomatic approach to algebrization. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC '09, pages 695-704, 2009. Google Scholar
  33. Yael Kalai and Ran Raz. Interactive PCP. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP '08, pages 536-547, 2008. Google Scholar
  34. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic Methods for Interactive Proof Systems. Journal of the ACM, 39(4):859-868, 1992. Google Scholar
  35. Ueli Maurer and Stefan Wolf. Lower bounds on generic algorithms in groups. In Proceedings of the 17th Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT '98, pages 72-84, 1998. Google Scholar
  36. Ueli M. Maurer. Abstract Models of Computation in Cryptography. In Proceedings of the 10th IMA International Conference on Cryptography and Coding, IMA '05, pages 1-12, 2005. Google Scholar
  37. Thilo Mie. Short PCPPs verifiable in polylogarithmic time with O(1) queries. Annals of Mathematics and Artificial Intelligence, 56:313-338, 2009. Google Scholar
  38. Vassiliy Ilyich Nechaev. Complexity of a determinate algorithm for the discrete logarithm. Mathematical Notes, 55:165-172, 1994. Google Scholar
  39. Omer Reingold, Ron Rothblum, and Guy Rothblum. Constant-Round Interactive Proofs for Delegating Computation. In Proceedings of the 48th ACM Symposium on the Theory of Computing, STOC '16, pages 49-62, 2016. Google Scholar
  40. Noga Ron-Zewi and Ron D. Rothblum. Local Proofs Approaching the Witness Length. Cryptology ePrint Archive, Report 2019/1062, 2019. Google Scholar
  41. Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4):869-877, 1992. Google Scholar
  42. Victor Shoup. Lower bounds for discrete logarithms and related problems. In Proceedings of the 16th International Conference on the Theory and Application of Cryptographic Techniques, EUROCRYPT '97, pages 256-266, 1997. Google Scholar
  43. Paul Valiant. Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency. In Proceedings of the 5th Theory of Cryptography Conference, TCC '08, pages 1-18, 2008. Google Scholar
  44. ZCash. What is Jubjub?, 2017. URL: https://z.cash/technology/jubjub.html.
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