Shafi Goldwasser

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. P ≠ NP is not strong enough, and one really needs an average-case version of P ≠ NP. 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