MIT and Weizmann Institute of Science
Cryptography without (Hardly) Any Secrets
Abstract: The absolute privacy of the secret-keys associated with cryptographic algorithms has been the corner-stone of modern cryptography. Still, in practice, keys do get compromised at times for a variety of reasons. A particularly disturbing loss of secrecy is as a result of side channel attacks. These attacks exploit the fact that every cryptographic algorithm is ultimately implemented on a physical device and such implementations enable 'observations' which can be made and measured on secret data and secret keys. Indeed, side channel observations can lead to information leakage about secret keys. Traditionally, such attacks have been followed by ad-hoc 'fixes' which make particular implementation invulnerable to particular attacks, only to potentially be broken anew by new examples of side-channel attacks.
In recent years, several general theories of physical security against a large class of families of side channel attacks have been proposed. Examples of such families include (1) the 'computation but only computation' (of Micali and Reyzin) attacks where one assumes that computation proceeds in steps and the only portions of secret memory which may leak during a computational step are those which effect its outcome, and (2) the 'Memory-attacks' proposed (of Akavia, Goldwasser, and Vaikuntanathan) that assumes that any function of the entire secret memory may leak as long as its output is of bounded length.
Provably secure cryptographic constructions, under standard cryptographic intractability, have been proposed in the above attack model. These include constructions of encryption scheme, digital signatures schemes, pseudo random number generators, and even general computations under the additional assumption of the existence of simple secure one-time memory.
The talk will survey highlights of these exciting developments.
Biography: Shafi Goldwasser is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel. She is a member of the Theory of Computation group at MIT Computer Science and Artificial Intelligence Laboratory.
Goldwasser's research areas include complexity theory, cryptography and computational number theory. She is the co-inventor of zero-knowledge proofs, which probabilistically and interactively demonstrate the validity of an assertion without conveying any additional knowledge, and are a key tool in the design of cryptographic protocols. Her work in complexity theory includes the classification of approximation problems, showing that some problems in NP remain hard even when only an approximate solution is needed.
Goldwasser has twice won the Gödel Prize in theoretical computer science: first in 1993 (for "The knowledge complexity of interactive proof systems"), and again in 2001 (for "Interactive Proofs and the Hardness of Approximating Cliques"). She won the RSA Award in Mathematics (1998) for outstanding mathematical contributions to cryptography. In 2001 she was elected to the American Academy of Arts and Sciences, in 2004 she was elected to the National Academy of Science, and in 2005 to the National Academy of Engineering. She was selected as an IACR Fellow in 2007.