• go to Avi Wigderson's profile page
  • go to Robert Melancton Metcalfe's profile page
  • go to Ronald L Rivest's profile page
  • go to Robert E Tarjan's profile page
  • go to Dr. Jack Dongarra's profile page
  • go to Ivan Sutherland's profile page
  • go to John L Hennessy's profile page
  • go to Edmund Clarke's profile page
  • go to Manuel Blum's profile page
  • go to Leslie G Valiant's profile page
  • go to A. J. Perlis 's profile page
  • go to Charles P. Thacker's profile page
  • go to Juris Hartmanis's profile page
  • go to Sir Tim Berners-Lee's profile page
  • go to Frances Allen's profile page
  • go to Judea Pearl's profile page
  • go to Silvio Micali's profile page
  • go to Leslie Lamport's profile page
  • go to Dennis M. Ritchie 's profile page
  • go to Richard W. Hamming's profile page
  • go to Yann LeCun's profile page
  • go to Richard E Stearns's profile page
  • go to Edgar F. Codd's profile page
  • go to Douglas Engelbart's profile page
A.M. TURING AWARD WINNERS BY...

Shafi Goldwasser DL Author Profile link

United States, Israel – 2012
Additional Materials

Assumptions in Cryptography

There are few algorithms in cryptography that can absolutely be proven secure. The most famous example is a “one-time pad”, where one uses an n-bit key to securely send an n-bit message across a channel that is subject to an eavesdropper.

For most cryptographic tasks, however, we know of no such proof of security. Even if we merely want to use an n-bit key to send an n+1-bit message, we know of no provably secure way of doing this. In fact, if P=NP (a statement we are unable to prove false), then most cryptographic tasks cannot be done securely. Most cryptography security proofs are therefore based on computational complexity assumptions. PNP is not strong enough, and one really needs an average-case version of PNP. One such assumption is that a specific function is “one-way function,” meaning that it can be computed efficiently, but cannot be efficiently inverted on the average. For many tasks, such as public-key encryption, even stronger assumptions are needed. An example of one of these stronger assumptions is that large random integers cannot be efficiently factored.

 


Proofs Probable

Neil Savage, Communications of the ACM, Volume 56 Issue 6, June 2013, Pages 22-24Shafi Goldwasser and Silvio Micali laid the foundations for modern cryptography, with contributions including interactive and zero-knowledge proofs.

Q&A

Leah Hoffman, Communications of the ACM, Volume 56 Issue 6, June 2013, Pages 120-ffTuring Award recipients Shafi Goldwasser and Silvio Micali talk about proofs, probability, and poker.

Interviews

Shafi has done in interesting one-hour interview with Stephen Ibaraki. The transcript text can be found here and you can listen to the audio recording as an MP3 file here.


Watch a brief video about Shafi Goldwasser, Silvio Micali, and the ACM A.M. Turing Award