A.M. TURING AWARD WINNERS BY...

Manuel Blum

United States – 1995
Short Annotated Bibliography

The following is a list of the publications mentioned in the main essay.

  1. Blum, M., "A Machine-Independent Theory of the Complexity of Recursive Functions," Journal of the ACM, Vol. XIV, No. 2, Apri11967, pp. 322-336.
  2. Blum, M., Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest and Robert E. Tarjan, "Linear Time Bounds for Median Computations," Proceedings of the 4th Annual ACM Symposium on Theory of Computing, Denver, Colorado, May 1972, pp. 119-124.
  3. Blum, M., "Coin Flipping by Telephone: A Protocol for Solving Impossible Problems," Proceedings of the Compcon 82 Conference, San Francisco, February 1982, pp. 133-137. (also in Advances in Cryptology: Report on CRYPTO’81, pp. 11-15.)
  4. Blum, M. and S. Micali, "How to Generate Cryptographically Strong Sequences of Pseudo Random Bits," SIAM Journal on Computing, Vol. 13, No.4, November 1984, pp. 850-864.
  5. Blum, M., L. Blum and M. Shub, "A Simple Unpredictable Pseudo-Random Number Generator," SIAM Journal on Computing, Vol. 15, No.2, May 1986, pp. 364-382.
  6. M. Blum, S. Goldwasser, "An Efficient Probabilistic Public Key Encryption Scheme which Hides All Partial Information," Proceedings of Advances in Cryptology - CRYPTO '84, pp. 289-299, Springer Verlag, 1985.
  7. Blum, M. and S. Kannan, "Designing Programs That Check Their Work," in Proceedings. of the 21st Annual ACM Symposium on Theory of Computing, May 1989, pp. 86-97; and in Journal of the ACM (with M. Luby, and R. Rubinfeld), Vol. 42, No.1, pp. 269-291, 1995.
  8. Blum, M., Luis von Ahn, Nicholas J. Hopper and John Langford, “CAPTCHA: Using Hard AI Problems for Security,Advances in Cryptology - EUROCRYPT 2003, Lecture Notes in Computer Science Vol. 2656, Springer, pp. 294 - 311, 2003.