Document Open Access Logo

Pseudo-Deterministic Proofs

Authors Shafi Goldwasser, Ofer Grossman, Dhiraj Holden

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.17.pdf
  • Filesize: 496 kB
  • 18 pages

Document Identifiers

Author Details

Shafi Goldwasser
Ofer Grossman
Dhiraj Holden

Cite AsGet BibTex

Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden. Pseudo-Deterministic Proofs. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ITCS.2018.17

Abstract

We introduce pseudo-deterministic interactive proofs (psdIP): interactive proof systems for search problems where the verifier is guaranteed with high probability to output the same output on different executions. As in the case with classical interactive proofs, the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover. We view pseudo-deterministic interactive proofs as an extension of the study of pseudo-deterministic randomized polynomial time algorithms: the goal of the latter is to find canonical solutions to search problems whereas the goal of the former is to prove that a solution to a search problem is canonical to a probabilistic polynomial time verifier. Alternatively, one may think of the powerful prover as aiding the probabilistic polynomial time verifier to find canonical solutions to search problems, with high probability over the randomness of the verifier. The challenge is that pseudo-determinism should hold not only with respect to the randomness, but also with respect to the prover: a malicious prover should not be able to cause the verifier to output a solution other than the unique canonical one. The IP=PSPACE characterization implies that psdIP = IP. The challenge is to find constant round pseudo-deterministic interactive proofs for hard search problems. We show a constant round pseudo-deterministic interactive proof for the graph isomorphism problem: on any input pair of isomorphic graphs (G_0,G_1), there exist a unique isomorphism phi from G_0 to G_1 (although many isomorphism many exist) which will be output by the verifier with high probability, regardless of any dishonest prover strategy. In contrast, we show that it is unlikely that psdIP proofs with constant rounds exist for NP-complete problems by showing that if any NP-complete problem has a constant round psdIP protocol, then the polynomial hierarchy collapses.
Keywords
  • Pseudo-Deterministic
  • Interactive Proofs

Metrics

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

References

  1. Dorit Aharonov and Oded Regev. Lattice problems in NP ∩ coNP. Journal of the ACM (JACM), 52(5):749-765, 2005. Google Scholar
  2. László Babai. Trading group theory for randomness. In Proceedings of the seventeenth annual ACM symposium on Theory of computing, pages 421-429. ACM, 1985. Google Scholar
  3. László Babai and Eugene M Luks. Canonical labeling of graphs. In Proceedings of the fifteenth annual ACM symposium on Theory of computing, pages 171-183. ACM, 1983. Google Scholar
  4. J. Cai, V. Chakaravarthy, L. Hemaspaandra, and M. Ogihara. Competing provers yield improved Karp-Lipton collapse results. Information and Computation, 198(1):1-23, 2005. Google Scholar
  5. John J Cannon. Construction of defining relators for finite groups. Discrete Mathematics, 5(2):105-129, 1973. Google Scholar
  6. Eran Gat and Shafi Goldwasser. Probabilistic search algorithms with unique answers and their cryptographic applications. In Electronic Colloquium on Computational Complexity (ECCC), volume 18, page 136, 2011. Google Scholar
  7. Oded Goldreich. Modern cryptography, probabilistic proofs and pseudorandomness, volume 17. Springer Science &Business Media, 1998. Google Scholar
  8. Oded Goldreich, Shafi Goldwasser, and Dana Ron. On the possibilities and limitations of pseudodeterministic algorithms. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 127-138. ACM, 2013. Google Scholar
  9. 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 (JACM), 38(3):690-728, 1991. Google Scholar
  10. Shafi Goldwasser and Ofer Grossman. Perfect bipartite matching in pseudo-deterministic RNC. In Electronic Colloquium on Computational Complexity (ECCC), volume 22, page 208, 2015. Google Scholar
  11. Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 59-68. ACM, 1986. Google Scholar
  12. Joachim Grollmann and Alan L Selman. Complexity measures for public-key cryptosystems. SIAM Journal on Computing, 17(2):309-335, 1988. Google Scholar
  13. Ofer Grossman. Finding primitive roots pseudo-deterministically. In Electronic Colloquium on Computational Complexity (ECCC), volume 22, page 207, 2015. Google Scholar
  14. E. Hemaspaandra, L. Hemaspaandra, and C. Menton. Search versus decision for election manipulation problems. In Proceedings of the 30th Annual Symposium on Theoretical Aspects of Computer Science, pages 377-388. Leibniz International Proceedings in Informatics (LIPIcs), 2013. Google Scholar
  15. L. Hemaspaandra and D. Narváez. The opacity of backbones. In AAAI-2017, pages 3900-3906. AAAI Press, 2017. Google Scholar
  16. Lane A Hemaspaandra, Ashish V Naik, Mitsunori Ogihara, and Alan L Selman. Computing solutions uniquely collapses the polynomial hierarchy. SIAM Journal on Computing, 25(4):697-708, 1996. Google Scholar
  17. Dhiraj Holden. A note on unconditional subexponential-time pseudo-deterministic algorithms for BPP search problems. arXiv preprint arXiv:1707.05808, 2017. Google Scholar
  18. Neil Immerman. Nondeterministic space is closed under complementation. SIAM Journal on computing, 17(5):935-938, 1988. Google Scholar
  19. Rudolf Mathon. A note on the graph isomorphism counting problem. Information Processing Letters, 8(3):131-136, 1979. Google Scholar
  20. Peter Bro Miltersen, N Variyam Vinodchandran, and Osamu Watanabe. Super-polynomial versus half-exponential circuit size in the exponential hierarchy. In International Computing and Combinatorics Conference, pages 210-220. Springer, 1999. Google Scholar
  21. Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of computer and System Sciences, 49(2):149-167, 1994. Google Scholar
  22. Igor C Oliveira and Rahul Santhanam. Pseudodeterministic constructions in subexponential time. arXiv preprint arXiv:1612.01817, 2016. Google Scholar
  23. Omer Reingold, Guy N Rothblum, and Ron D Rothblum. Constant-round interactive proofs for delegating computation. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 49-62. ACM, 2016. Google Scholar
  24. Adi Shamir. IP=PSPACE. Journal of the ACM (JACM), 39(4):869-877, 1992. Google Scholar
  25. Róbert Szelepcsényi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26(3):279-284, 1988. 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