The Knowledge Complexity of Interactive Proof-Systems

Shafi Goldwasser, Silvio Micali, Charles Rackoff, 1985, STOC

About this paperEnglishTiếng Việt中文beside Englishbeside Tiếng Việtbeside 中文

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

対話型証明システムの知識計算量*

要旨。通常、定理の証明には、その定理が真であるという単なる事実以上の知識が含まれている。例えば、グラフがハミルトン閉路を持つことを証明するには、そのグラフのハミルトン閉路を示せば十分である。しかし、これはハミルトン閉路を持つか否かを表す1ビット以上の知識を含んでいるように思われる。

References

  1. [AGH] B. Aiello, S. Goldwasser, and J. Hastad, On the power of interaction, in Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, 1986, pp. 368-379.
  2. [AH] B. Aiello and J. Hastad, Perfect zero-knowledge languages can be recognized in two rounds, in Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, pp. 439-448.
  3. [BGGHKRM] M. Ben-Or, O. Goldreich, S. Goldwasser, J. Hastad, J. Kilian, P. Rogaway, and S. Micali, Everything provable is provable in zero-knowledge, in Proc. Crypto88, to appear.
  4. [Bl] M. Blum, Coin flipping by telephone, IEEE COMPCON 1982, pp. 133-137.
  5. [BHZ] R. Boppana, J. Hastad, and S. Zachos, Does co-NP have short interactive proofs?, Inform. Process. Lett., 25 (1987) pp. 127-132.
  6. [Ba] L. Babai, Trading group theory for randomness, in Proc. 17th ACM Annual Symposium on Theory of Computation, 1975, pp. 421-429.
  7. [BM] L. Babai and S. Moran, Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes, J. Comput. Sci. Systems; a previous version was entitled Trading group theory for randomness, in Proc. 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 421-429.
  8. [BS] L. Babai and E. Szemeredi, On the complexity of matrix group problems, in Proc. 25th Annual IEEE Symposium on Foundations of Computer Science, pp. 229-240.
  9. [BC] G. Brassard and C. Crepeau, Non-transitive transfer of confidence: A perfect zero-knowledge interactive protocol for SAT and beyond, Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, October 1986.
  10. [Ch] D. Chaum, Demonstrating the public predicate can be satisfied without revealing any information how, in Proc. Crypto86.
  11. [Co] J. Cohen (Benaloh), Cryptographic capsules, in Proc. Crypto86.
  12. [CKS] A. Chandra, D. Kozen, and L. Stockmeyer, Alternation, J. Assoc. Comput. Mach., 28 (1981), pp. 114-133.
  13. [C] S. Cook, The complexity of theorem-proving procedures, in Proc. 3rd Annual ACM Symposium of Theory of Computation, 1971, pp. 151-158.
  14. [CR] S. Cook and R. Reckhow, The relative efficiency of propositional proof systems, J. Symbolic Logic, 44 (1979).
  15. [F] P. Feldman, private communication.
  16. [FMRW] M. Fischer, S. Micali, C. Rackoff, and D. Witenberg, *A secure protocol for the oblivious transfer*, unpublished manuscript, 1986.
  17. [FFS] U. Feige, A. Fiat, and A. Shamir, *Zero knowledge proofs of identity*, in Proc. 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 210–217.
  18. [Fo] L. Fortnow, *The complexity of perfect zero-knowledge*, in Proc. 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 204–209.
  19. [FH] R. Fagin and J. Halpern, *Belief, awareness, and limited reasoning*, in Proc. 9th International Joint Conference on Artificial Intelligence, 1985, pp. 491–501.
  20. [FHV] R. Fagin, J. Halpern, and M. Vardi, *A model theoretic analysis of knowledge*, in Proc. 25th Annual IEEE Symposium on Foundations of Computer Science, 1984, pp. 268–278.
  21. [GM] S. Goldwasser and S. Micali, *Probabilistic encryption*, J. Comput. Science and Systems, 28 (1984), pp. 270–299.
  22. [GM1] ———, *Proofs with untrusted oracles*, unpublished manuscript (submitted to STOC, 1984). Revised version: *The information content of proof systems*, unpublished manuscript (submitted to STOC, 1984).
  23. [GMS] O. Goldreich, Y. Mansour, and M. Sipser, *Interactive proof systems: Provers that never fail and random selection*, in Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, pp. 449–460.
  24. [GMR] S. Goldwasser, S. Micali, and C. Rackoff, *The knowledge complexity of interactive proof systems*, in Proc. 27th Annual Symposium on Foundations of Computer Science, 1985, pp. 291–304. Earlier version: *Knowledge complexity*, unpublished manuscript, (submitted to FOCS, 1984).
  25. [GS] S. Goldwasser and M. Sipser, *Private coins versus public coins in interactive proof-systems*, in Proc. 18th Annual Symposium on Theory of Computing, 1986, pp. 59–68.
  26. [GHY] Z. Galil, S. Haber, and M. Yung, *A private interactive test of a Boolean predicate and minimum-knowledge public-key cryptosystems*, in Proc. 26th Annual IEEE Symposium on Foundations of Computer Science, 1985, pp. 360–371.
  27. [GMW] O. Goldreich, S. Micali, and A. Wigderson, *Proofs that yield nothing but their validity and a methodology of cryptographic protocol design*, in Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, 1986, pp. 174–187.
  28. ———, *How to play any mental game*, in Proc. 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 218–229.
  29. [HM] J. Halpern and Y. Moses, *Knowledge and common knowledge in a distributed environment*, in Proc. 3rd Principles of Distributed Computing Conference, 1984, pp. 50–61.
  30. [LMR] M. Luby, S. Micali, and C. Rackoff, *How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin*, in Proc. 24th Annual IEEE Symposium on Foundations of Computer Science, 1983, pp. 11–22.
  31. [O] Y. Oren, *On the cunning power of cheating verifiers: some observations of zero-knowledge proofs*, in Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, pp. 462–471.
  32. [P] C. Papadimitriou, *Games against nature*, in Proc. 24th Annual IEEE Symposium on Foundations of Computer Science, 1983, pp. 446–450.
  33. [TW] M. Tompa and H. Woll, *Random self reducibility and zero knowledge interactive proofs of possession of information*, in Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, pp. 472–482.
  34. [ZF] S. Zachos and M. Furer, *Probabilistic quantifiers vs. distrustful adversaries*, in Proc. Structure of Complexity Classes Conference, 1986.
  35. [Y] A. Yao, *Theory and application of trapdoor functions*, in Proc. 23rd Annual IEEE Symposium on Foundations of Computer Science, November 1982, pp. 80–91.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into 日本語 by gpt-5, against glossary version 6. Translated from the English.