A.M. TURING CENTENARY CELEBRATION WEBCAST
  • go to Butler W Lampson's profile page
  • go to Charles W Bachman's profile page
  • go to Richard W. Hamming's profile page
  • go to Ronald L Rivest's profile page
  • go to Charles P. Thacker's profile page
  • go to Robert W. Floyd's profile page
  • go to Raj Reddy's profile page
  • go to Richard Karp's profile page
  • go to Whitfield Diffie 's profile page
  • go to Joseph Sifakis's profile page
  • go to Edsger W. Dijkstra's profile page
  • go to Edwin Catmull's profile page
  • go to Edgar F. Codd's profile page
  • go to John E Hopcroft's profile page
  • go to Sir Tim Berners-Lee's profile page
  • go to Allen Newell 's profile page
  • go to E. Allen Emerson's profile page
  • go to Maurice V. Wilkes's profile page
  • go to Richard E Stearns's profile page
  • go to Herbert A. Simon's profile page
  • go to Michael Stonebraker's profile page
  • go to A. J. Perlis 's profile page
  • go to Yoshua Bengio's profile page
  • go to Judea Pearl's profile page
A.M. TURING AWARD WINNERS BY...
Short Annotated Bibliography
  1. Goldwasser, S. and S. Micali, “Probabilistic Encryption,” Journal of Computer and System Sciences(JCSS), Vol. 28, Num. 2, pp. 270-299, April 1984.  This is the first paper to introduce formal notions of security of cryptographic systems, and applies them to public-key encryption and other fundamental practical algorithms.
  2. Blum, M. and S. Micali, “How to generate Cryptographically Strong Sequences of Pseudo-Random Bits,” SIAM Journal on Computing (SICOMP), Vol. 13, Num. 4, pp. 850-864, November 1984.  This paper was the first to formally define the notion of computationally unpredictable sequences, and to show how to deterministically and efficiently generate such sequences.
  3. Goldreich, O., S. Goldwasser, and S. Micali, “How to Construct Random Functions,” Journal of the ACM (JACM), Vol. 33, Num. 4, pp. 792-807, October 1986.  This paper constructs a family of efficiently computable functions whose output values are indistinguishable from those of random functions.
  4. Goldwasser, S., S. Micali, and C. Rackoff; “The Knowledge Complexity of Interactive Proof-Systems,” SIAM Journal on Computing (SICOMP), Vol. 18, Num. 1, pp. 186-200, February 1989.  This paper introduces the notion of interactive proofs, the knowledge complexity of a proof, and the paradoxical notion of zero-knowledge proof.
  5. Goldreich, O., S. Micali and A. Wigderson, “Proofs That Yield Nothing But their Validity, Or, All Languages in NP Have Zero-Knowledge Proofs,” Journal of the ACM (JACM), Vol. 38, Num. 3, pp. 691-729, July 1991.  This paper demonstrates that everything provable can be proved with a zero-knowledge proof.
  6. Goldreich, O., S. Micali and A. Wigderson, “How to Play any Mental Game or A Completeness Theorem for Distributed Protocols with Honest Majority.” Proceedings of the 19th Symposium on Theory of Computing, pp. 218-229, May 1987.  This paper shows the utility of zero-knowledge proofs for cryptographic protocols. It gives an efficient compiler that takes any protocol which is private and secure for honest, reliable parties, and transforms it into one which is private and secure even if a third of the participants are deviating from the protocol in an arbitrary malicious and collaborative manner.
  7. Blum, M., A. De Santis, S. Micali  and G. Persiano, “Non-Interactive Zero-Knowledge,” SIAM Journal on Computing (SICOMP), Vol. 20, pp.1084-1118, December 1991.  This paper introduces the notion of a written (non interactive) zero-knowledge proof, and shows that everything provable has such a proof.
  8. Feldman, P. and S. Micali, “An Optimal Probabilistic Algorithm for Synchronous Byzantine Agreement,” SIAM Journal on Computing (SICOMP), Vol. 26, Num. 4, pp. 873-933, August 1997.  This paper is gives a constant-round protocol for achieving consensus (Byzantine agreement) in a network in which up to 1/3 of the processors may arbitrarily deviate.
  9. Chen, J., S. Micali and P. Valiant, “Leveraging Collusion in Combinatorial Auctions,” Innovations in Computer Science, Beijing, China, January 2010.  This paper suggests that rather than forbidding collusions in auctions (as the law in many countries currently dictates), they should be allowed, and shows that allowing them would actually benefit (rather than harm) the participants!
  10. Diffie, Whitfield and Martin E. Hellman, “New Directions in Cryptography,” IEEE Transactions On Information Theory, Vol. IT-22, Num. 6, November 1976, pp. 644-654.  While not by Micali, this is the paper, mentioned in the essay, that introduced the notion of public-key cryptography.
  11. Rivest, R. L., A. Shamir and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, Volume 21, Num. 2, pp. 120-126, Feb. 1978.This is the paper that introduced the RSA technique for public-key cryptographic systems.