link.springer.com

Everything Provable is Provable in Zero-Knowledge

  • ️Sat Jan 01 2000

References

  1. Adleman, L., and M. Huang, “Recognizing Primes in Random Polynomial Time,” Proceedings of the 19th STOC, 1987, pp. 462–469.

    Google Scholar 

  2. Babai, L., “Trading Group Theory for Randomness,” Proceedings of the 17th STOC, 1985, pp. 421–429.

    Google Scholar 

  3. Barrington, D., “Bounded Width Polynomial Size Branching Programs Recognize Exactly Those Languages in NC 1,” Proceedings of the 18th STOC, 1986, pp. 1–5.

    Google Scholar 

  4. Babai, L. and S. Moran, “Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes,” manuscript.

    Google Scholar 

  5. Blum, M., “Coin Flipping by Telephone,” IEEE COMPCON, 1982, pp. 133–137.

    Google Scholar 

  6. Boppana, R., J. Håstad, and S. Zachos, “Does co-NP Have Short Interactive Proofs?”, Information Processing Letters, 1987, pp. 127–132.

    Article  MathSciNet  Google Scholar 

  7. Brassard, G., personal communication, Augest 1988.

    Google Scholar 

  8. Chaum, D., I. Damgård, and J. van de Graaf, “Multiparty Computations Ensuring Privacy of Each Party’s Input and Correctness of the Result,” Proceedings of Crypto-87, pp. 87–119.

    Google Scholar 

  9. Feldman, P., “The Optimum Prover Lives in PSPACE,” manuscript.

    Google Scholar 

  10. Fortnow, L., “The Complexity of Perfect Zero-Knowledge,” Proceedings of the 19th STOC, 1987, pp. 204–209.

    Google Scholar 

  11. Goldreich, O., “Randomness, Interactive Proofs and Zero-Knowledge (a survey),” Technion Technical Report, 1987.

    Google Scholar 

  12. Goldwasser, S., and J. Kilian, “Almost All Primes Can Be Quickly Certified,” Proceedings of the 18th STOC, 1986, pp. 316–329.

    Google Scholar 

  13. Goldwasser., S., and S. Micali, “Probabilistic Encryption,” Journal of Computer and System Sciences, Vol. 28, No. 2, 1984, pp. 270–299.

    Article  MathSciNet  Google Scholar 

  14. Goldwasser, S., S. Micali, and C. Rackoff, “Knowledge Complexity of Interactive Proofs,” Proceedings of the 17th STOC, 1985, pp. 291–305

    Google Scholar 

  15. Goldreich, M., Y. Mansour, and M. Sipser, “Interactive Proof Systems: Provers that Never Fail and Random Selection,” Proceedings of the 28th FOCS, 1987, pp. 449–461.

    Google Scholar 

  16. Goldreich, O., S. Micali, and A. Wigderson, “Proofs that Yield Nothing but their Validity and a Methodology of Cryptographic Protocol Design,” Proceedings of the 27th FOCS, 1986, pp. 174–187.

    Google Scholar 

  17. Goldreich, O., S. Micali, and A. Wigderson, “How to Play Any Mental Game, or, A Completeness Theorem for Protocols with Honest Majority,” Proceedings of the 19th STOC, 1987, pp. 218–229.

    Google Scholar 

  18. Goldwasser, S., and M. Sipser, “Arthur Merlin Games versus Interactive Proof Systems,” Proceedings of the 18th STOC, 1986, pp. 59–68.

    Google Scholar 

  19. Impagliazzo, R., personal communications, 1987.

    Google Scholar 

  20. Impagliazzo, R., and M. Yung, “Direct Minimum-Knowledge Computations,” Proceedings of Crypto-87, pp. 40–51.

    Google Scholar 

  21. Kilian, J., “Founding Cryptography on Oblivious Transfer,” Proceedings of the 20th STOC, 1988, pp. 20–31.

    Google Scholar 

  22. Kilian, J., “Primality Testing and the Cryptographic Complexity of Noisy Communications Channels,” MIT Ph.D. Thesis (in preparation), 1988.

    Google Scholar 

  23. Levin, L., “One-way Functions and Pseudorandom Generators,” Proceedings of the 17th STOC, 1985, pp. 363–368.

    Google Scholar 

  24. Micali, S., C. Rackoff and R. Sloan, “The Notion of Security for Probabilistic Cryptosystems,” SIAM Journal of Computing, 17(2):412–426, April 1988.

    Article  MathSciNet  Google Scholar 

  25. Oren, Y., “On the Cunning Power of Cheating Verifiers: Some Observations about Zero Knowledge Proofs,” Proceedings of the 28th FOCS, 1987, pp. 462–471.

    Google Scholar 

  26. Tompa, M., and H. Woll, “Random Self-Reducibility and Zero Knowledge Interactive Proofs of Possession of Information,” Proceedings of the 28th FOCS, 1987, pp. 472–482.

    Google Scholar 

  27. Yao, A.C., “Theory and Applications of Trapdoor Functions,” Proceedings of the 23rd FOCS, 1982, pp. 80–91.

    Google Scholar 

  28. Yung, M., personal communication, Augest 1988.

    Google Scholar 

Download references