Everything Provable is Provable in Zero-Knowledge
- ️Sat Jan 01 2000
References
Adleman, L., and M. Huang, “Recognizing Primes in Random Polynomial Time,” Proceedings of the 19th STOC, 1987, pp. 462–469.
Babai, L., “Trading Group Theory for Randomness,” Proceedings of the 17th STOC, 1985, pp. 421–429.
Barrington, D., “Bounded Width Polynomial Size Branching Programs Recognize Exactly Those Languages in NC 1,” Proceedings of the 18th STOC, 1986, pp. 1–5.
Babai, L. and S. Moran, “Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes,” manuscript.
Blum, M., “Coin Flipping by Telephone,” IEEE COMPCON, 1982, pp. 133–137.
Boppana, R., J. Håstad, and S. Zachos, “Does co-NP Have Short Interactive Proofs?”, Information Processing Letters, 1987, pp. 127–132.
Brassard, G., personal communication, Augest 1988.
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.
Feldman, P., “The Optimum Prover Lives in PSPACE,” manuscript.
Fortnow, L., “The Complexity of Perfect Zero-Knowledge,” Proceedings of the 19th STOC, 1987, pp. 204–209.
Goldreich, O., “Randomness, Interactive Proofs and Zero-Knowledge (a survey),” Technion Technical Report, 1987.
Goldwasser, S., and J. Kilian, “Almost All Primes Can Be Quickly Certified,” Proceedings of the 18th STOC, 1986, pp. 316–329.
Goldwasser., S., and S. Micali, “Probabilistic Encryption,” Journal of Computer and System Sciences, Vol. 28, No. 2, 1984, pp. 270–299.
Goldwasser, S., S. Micali, and C. Rackoff, “Knowledge Complexity of Interactive Proofs,” Proceedings of the 17th STOC, 1985, pp. 291–305
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.
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.
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.
Goldwasser, S., and M. Sipser, “Arthur Merlin Games versus Interactive Proof Systems,” Proceedings of the 18th STOC, 1986, pp. 59–68.
Impagliazzo, R., personal communications, 1987.
Impagliazzo, R., and M. Yung, “Direct Minimum-Knowledge Computations,” Proceedings of Crypto-87, pp. 40–51.
Kilian, J., “Founding Cryptography on Oblivious Transfer,” Proceedings of the 20th STOC, 1988, pp. 20–31.
Kilian, J., “Primality Testing and the Cryptographic Complexity of Noisy Communications Channels,” MIT Ph.D. Thesis (in preparation), 1988.
Levin, L., “One-way Functions and Pseudorandom Generators,” Proceedings of the 17th STOC, 1985, pp. 363–368.
Micali, S., C. Rackoff and R. Sloan, “The Notion of Security for Probabilistic Cryptosystems,” SIAM Journal of Computing, 17(2):412–426, April 1988.
Oren, Y., “On the Cunning Power of Cheating Verifiers: Some Observations about Zero Knowledge Proofs,” Proceedings of the 28th FOCS, 1987, pp. 462–471.
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.
Yao, A.C., “Theory and Applications of Trapdoor Functions,” Proceedings of the 23rd FOCS, 1982, pp. 80–91.
Yung, M., personal communication, Augest 1988.