Turing Year

Yesterday was the first meeting in Cambridge in the sixth month workshop devoted to the legacy of Alan Turing. The talks were all introductory in nature; and rather than discuss here what they were about I thought it might be worth looking at Turing's legacy in Crypto somewhat.

The first thing the layman would think of is the second world war work on Enigma. In this Turing took the early work of the Polish cryptographers and helped design (with Welchman) the Bombe. This was an electro-mechanical machine used for finding wheel settings of the Enigma machines. It was not a computer! The key to breaking Enigma was that the Enigma machine never encrypted the same letter to itself, and if (for a particular setting) A encrypted to E, then E would encrypt to A. This last property is what made the Welchman diagonal board on the Bombe improve the Bombe's performance.

The layman also often confused Enigma with Tunny (a.k.a. Lorenz). The breaking of Lorenz was by far the most impressive bit of work done by Bletchley Park. The initial mathematics being done by Bill Tutte and the design of the resulting machine, Colossus, being the work of Tommy Flowers. However, Colossus was a real computer; it was digital, had input and output devices, an "ALU" and could be programmed (sort of). Thus whilst Turing may not have had a hand in the design of Colossus one can see that Colossus follows on from Turing's early paper on the decision problem.

In fact it is Turing's work on the decision problem which has had the most lasting impact on cryptography. In the paper he wrote Turing imagined a computing machine (now called a Turing machine) which was able to perform any computational task. The key idea was that there was one machine, now called the Universal Turing Machine, which could be "programmed" to perform any specific computational task. This is quite revolutionary idea; it is the reason why you only need buy one computer and it can do word-processing, games, internet access etc. The computer is "general purpose". Compare this to your kitchen where you have a toaster for toasting, a kettle for boiling water, a stove for boiling saucepans, and an oven for baking.

Imagine if you needed to buy a different device for each computational task you wanted to do. For example one device to read books (a Kindle), one device to play games (an XBox), one device to listen to music (an iPod). Hmmm, we seem to be going backwards these days!!!

Anyway back to the plot. The Turing machine is not only important as it is basically what a modern computer is; it is also important as it models what an arbitrary computer can do. Thus in cryptography we always consider our adversaries to be Turing machines; or more specifically probabilistic Turing machines whose run-times are bounded by some polynomial function of the length of their input (a PPT, or Probabilistic Polynomial-time Turing machine).  I would say Turing's name is mentioned more often than any other name in cryptographic talks; even if it is just by the TLA of a PPT.

Finally, there is one other philosophical contribution Turing made to cryptography in my opinion. The "Turing Test" in Artificial Intelligence is about whether someone can tell the difference between a real human and a computer by simply asking questions via a remote link. In this test the computers goal is to simulate the human so that an observer is unable to tell the difference between a human and the simulator. The is exactly what we do in many security proofs in cryptography. For a specific algorithm (having access to some special bit of information or functions) we define a simulator (which does not have access to the information or functions). We can then argue that if someone cannot tell the difference between the simulator and the real algorithm, then the algorithm is "secure".

Anyway, welcome to the Turing Year of 2012