A.M. TURING CENTENARY CELEBRATION WEBCAST
  • go to Kenneth E. Iverson 's profile page
  • go to Edwin Catmull's profile page
  • go to A J Milner 's profile page
  • go to Frances Allen's profile page
  • go to Dana S Scott's profile page
  • go to Charles W Bachman's profile page
  • go to Raj Reddy's profile page
  • go to Sir Tim Berners-Lee's profile page
  • go to Douglas Engelbart's profile page
  • go to Judea Pearl's profile page
  • go to William Kahan's profile page
  • go to John Backus 's profile page
  • go to Alan Kay's profile page
  • go to Herbert A. Simon's profile page
  • go to Edward A Feigenbaum's profile page
  • go to A. J. Perlis 's profile page
  • go to Charles P. Thacker's profile page
  • go to Fernando Corbato's profile page
  • go to Ivan Sutherland's profile page
  • go to Maurice V. Wilkes's profile page
  • go to Pat Hanrahan's profile page
  • go to Butler W Lampson's profile page
  • go to Edgar F. Codd's profile page
  • go to Michael Stonebraker's profile page
A.M. TURING AWARD WINNERS BY...
Shafi Goldwasser

PHOTOGRAPHS

Shafi Goldwasser DL Author Profile link

United States, Israel – 2012
Short Annotated Bibliography
  1.  Goldwasser, S. and S. Micali, “Probabilistic Encryption,” Special issue of Journal of Computer and Systems Sciences, Vol. 28, Num. 2, pp. 270-299, April 1984.This paper defines “semantic security” for public-key encryption systems, and gives an example based on a quadratic residuosity assumption.
  2. Chor, B., S. Goldwasser, S. Micali, and B. Awerbuch, “Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults,” Proceedings of 26th Annual Symposium on the Foundations of Computer Science (FOCS 1985), pp. 383-395, October 1985.This paper discusses how to share a secret in a way such that the participants cannot cheat.
  3. Goldwasser, S. and J. Kilian, “Almost All Primes Can be Quickly Certified,” Proceedings of the 18th Annual ACM Symposium on the Theory of Computing (STOC 1986), pp. 315-329, Berkeley, CA, May 1986.This paper shows that for most prime numbers, we can efficiently find a proof that the number really is prime.
  4. Goldreich, O., S. Goldwasser and S. Micali, “How to Construct Random Functions,” Journal of the ACM, Vol. 33, Num. 4, pp.792-807, October 1986.This paper defines what it means to pseudorandomly generate a function, and shows how to do this starting with a pseudorandom number generator.
  5. Goldwasser, S., S. Micali and R. Rivest, “A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attack,” SIAM Journal of Computing, Vol. 17, Num. 2, pp. 281-308, April 1988.This paper defines the now-standard notion of security for digital signatures, and provides a construction using common assumptions.
  6. Goldwasser, S., S. Micali and C. Rackoff, “The Knowledge Complexity of Interactive Proof Systems,” SIAM Journal of Computing, Vol. 18, Num. 1, pp. 186-208, January 1989.This paper introduces the notion of “zero-knowledge interactive proof,” and gives some examples involving quadratic residuosity.
  7. Goldwasser, S. and M. Sipser, “Private Coins versus Public Coins in Interactive Proof Systems,” Randomness and Computation, Vol. 5 of Advances in Computing Research, JAI Press, 1989.This paper shows that private coins are no more powerful than public coins in interactive proofs.
  8. Ben-Or, M., S. Goldwasser, and A. Wigderson, “Completeness Theorems for Non-Cryptographic Fault Tolerant Distributed Computation,” Proceedings of 20th Annual ACM Symposium on Theory of Computing (STOC 1988), Chicago, Illinois, pp. 1-10, May 1988. Also invited to appear in a special issue of Journal of Computer Science and Systems.This paper shows how to do secure multiparty function evaluation without assumptions, in the setting of secure channels between every two parties.
  9. Ben-Or, M., S. Goldwasser, J. Kilian, and A. Wigderson, “Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions,” Proceedings of 20th Annual ACM Symposium on Theory of Computing (STOC 1988), Chicago, Illinois, pp. 113-122, May 1988.This paper introduces the notion of multi-prover interactive proofs, and shows that they are capable of giving zero knowledge proofs for every NP language, without needing an assumption.
  10. Feige, U., S. Goldwasser, L. Lovasz, S. Safra and M. Szegedy, “Interactive Proofs and the Hardness of Approximating Cliques,”. Journal of the ACM, Vol. 43, Num. 2, pp 268-292, March 1996.This paper uses multi-prover proofs to show that maximum clique size is hard to approximate, unless there are efficient algorithms for all NP languages.
  11. Bellare, M., S. Goldwasser, C. Lund and A. Russell, “Efficient Probabilistically Checkable Proofs with Applications to Approximation,” Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC93), San Diego, CA, May 1993.This paper improves Probabilistically Checkable Proofs (PCPs) to obtain new hardness of approximation results.
  12. Golderich, O. and S. Goldwasser, “On the Limits of Non-Approximability of Lattice Problems,” Journal of Computer and System Sciences, Vol. 60, Num. 3, pp. 540-563, June 2000.This paper uses interactive proofs to show that a lattice assumption needed for cryptography probably is not NP-hard.
  13. Golderich, O., S. Goldwasser and D. Ron, “Property Testing and its Connection to Learning and Approximation,” Journal of the ACM, Vol. 45, Num. 4, pp. 653-750, July 1998.This paper introduced the area of “property testing” for combinatorial properties, where one examines an object (such as a graph) in a small number of places (for example, a constant number of edges), in order to tell if it has a certain property (such as possessing a large cut) or if it is far from any object having that property.
  14. Akavia, A., S. Goldwasser and S. Safra, “Proving Hard-Core Predicates Using List Decoding,” Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003), pp. 146-157, Cambridge, MA, October 2003.This paper gives a powerful technique for proving, from the assumption that computing a certain string is hard, that computing certain bits of that string is hard.
  15. Goldwasser, S., Y. Tauman Kalai, and G. Rothblum, “Delegating Computation: Interactive Proofs for Muggles,” 40th ACM Symposium on Theory of Computing (STOC 2008), pp. 113-122, Victoria, (BC), Canada, May 2008.This paper shows a way that a user can efficiently delegate a huge computation to an untrusted “cloud”, and be convinced that the answer is correct.
  16. Goldwasser, G., Y. Tauman Kalai and G. N. Rothblum, “One-Time Programs,” 28th International Cryptology Conference (CRYPTO 2008), pp. 39-56, Santa Barbara, CA, July 2008.This paper shows how to create a program that can only be run once, assuming a special kind of hardware.
  17. Akavia, A., S. Goldwasser and V. Vaikuntanathan, “Simultaneous Hardcore Bits and Cryptography against Memory Attacks,” In Omer Reingold, editor, Theory of Cryptography, 6th Theory of Cryptography Conference (TCC 2009), San Francisco, CA, volume 5444 of Lecture Notes in Computer Science, pp. 474-495, 2009. Springer.This paper shows a way of doing public-key cryptography where memory is protected from side-channel attacks.
  18. Goldwasser, S., Y. Tauman Kalai, V. Popa, V. Vaikuntanathan and N. Zeldovich, “Succinct Functional Encryption and Applications: Reusable Garbled Circuits and Beyond,” In IACR Eprint Archive, and to appear in Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC2013), Palo Alto, CA, June 2013.This paper gives new results on “functional encryption” and introduces a new paradigm for general function obfuscation called “token-based obfuscation”.
  19. Boyle, E., S. Goldwasser, A. Jain and Y. Tauman Kalai, “Multiparty Computation Secure Against Continual Memory Leakage,” In Proceedings of the 44th ACM Symposium on Theory of Computing (STOC2012), pp. 1235-1254, New York, NY, May 2012.This paper shows how a group of people can compute a function of their inputs, such that an adversary who controls some parties gets no additional knowledge, even after receiving a small amount of leakage from the others.
  20. Goldreich, O., S. Goldwasser and D. Ron, “On the Possibilities and Limitations of Pseudodeterministic Algorithms,” In ITCS 2013: Innovations in Theoretical Computer Science, pp. 127-138, Berkeley, CA, January 2013.This paper introduces and proves basic theorems about “pseudodeterministic algorithms,” which randomly find a desired object (such as a group generator) that is likely to be unique.