The Knowledge Complexity of Interactive Proof-Systems

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.