2012 Turing Award Goes to Cryptographers

The Turing Award (a kind of Noble Prize for Computer Science) has been awarded for 2012 to two cryptographers; Shafi Goldwasser and Silvio Micali. The announcement of this award came last week and is for their pioneering work on the foundations of cryptography. Over the years the list of Turing Award winners reads like a who's who of famous computer scientists (Hamming, Dijkstra, Knuth, Ritchie etc etc) and has included prior work in cryptography; Andrew Yao (2000) and Rivest, Shamir and Adleman (2002).

Goldwasser and Micali's work forms the foundation of almost everything that modern cryptographers do. In a ground breaking series of papers in the 1980's they defined the notion of semantic security, this is the de-facto modern security definition for encryption schemes. They also presented the first encryption scheme which met this definition (the Goldwasser-Micali scheme). This public key scheme is not very efficient, but the ideas behind it's construction form the basis of all modern encryption algorithms.

With Rivest they produced the GMR security definition for digital signature schemes, otherwise known as universal forgery under chosen message attack (UF-CMA). This definition again forms the basis of all modern constructions of digital signatures; such as the ones used to verify the validity of digital certificates in your browser or chip-and-pin cards.

However, their most interesting contribution is the idea of zero-knowledge. In many areas of computer science one is interested in a computer learning some information; say about a data set in biology etc. Areas such as Machine Learning try to develop algorithms which take data and learn from that data. In security we are interested in the opposite to some extent; namely we want to know that an algorithm cannot learn certain information (for example a secret key). To formalise this notion Goldwasser and Micali introduced the notion of zero-knowledge; i.e. they formally defined what it means for an algorithm or process to learn nothing. 

This has important practical importance. When you go into a shop to purchase something with your chip-and-pin card, the card is used to authenticate you to the shop, it also is used to authenticate the transaction. These authentication steps require using the secret key embedded into the card. However, we do not want the shop to learn the underlying secret even if it sees a large number of transactions performed with your card. This is where zero-knowledge protocols come in. They gaurantee that no matter how many transactions are seen by the merchant, the merchant cannot use these to validate an invalid transaction. They also form the basis behind protocols used in electronic locks; for example the key fob for opening your car door.

These three topics (semantic security, GMR security and zero-knowledge) form the basis of the cryptography teaching at Bristol University, and none of this would have been possible without the ground breaking work of Goldwasser and Micali. It is also fitting that the 2012 award should go to cryptographers; after all 2012 was the 100th anniversary of the birth of Alan Turing, and in a previous blog post we have discussed Turing's central contributions to cryptography.