A Fascinating Letter

I’ve mentioned here before the close connection between mathematics and cryptography, especially the public key cryptography that is used, among other things, as the basis for the SSL/TLS protocols that secure Internet commerce.   The security of the system depends on the use of a “one way” function; that is, a function that is easy to compute, but whose inverse is very difficult to compute.  For example, finding the product of two large prime numbers is relatively easy, but factoring the resulting product to find the original primes is believed to be computationally infeasible, provided the numbers are large:  2048 bits or more.  The analysis of the minimum effort required to solve problems like this is the focus of computational complexity theory, which emerged in the 1960s and 1970s as the merger of ideas from computer science and mathematics.

The New Scientist reports that the  US National Security Agency [NSA] has recently declassified some fascinating correspondence [PDF], centering on a letter it received from John Nash in 1955, on the subject of encryption systems.  Readers may recognize the name; John Nash was the brilliant mathematician and game theorist, subject of Sylvia Nasar’s  1998 biography, A Beautiful Mind, and the 2001 film  of the same name.  He made very important contributions to game theory, especially, and was one of the winners of the 1994 Nobel Memorial Economics Prize on the basis of that work.  Unfortunately, as related in the biography, he struggled with schizophrenia most of his adult life.

Apparently, Nash had written to predecessor agencies of the NSA (formed in 1952) back in 1950, describing a cipher machine he had designed.  The 1955 letter was an attempt to re-start that conversation.  The letter, written in longhand, appears at first glance more like something written by a high-school student (with not very good penmanship), rather than by one of the most brilliant living mathematicians.  It has a fair sprinkling of misspelled and crossed-out words.  Nash himself writes:

I hope my handwriting, etc. do not give the impression I am just a crank or circle-squarer.  My position here is Assist. Prof. of Math.  My best known work is in game theory (reprint sent separately).

(He was at MIT at the time, although he subsequently spent most of his time at Princeton.  It is also somewhat amusing that the reprint, enclosed almost as an afterthought, was of the work that won a Nobel Prize.)

What is striking about the letter is that Nash anticipates the core of computational complexity, a decade or two before it made a public appearance.  He proposes that the security of an encryption system is founded on the difficulty of the computation required to break it.

So a logical way to classify enciphering processes is by the way in which the computation length for the computation of the key increases with increasing length of the key. This is at best exponential and at worst probably at most a relatively small power of r, ar², or ar³, as in substitution ciphers.

He conjectures that, with a sufficiently complex encryption function, the computation can be made of exponential difficulty.  Why does this matter?  He explains that, if the computation is difficult enough, the encryption can be made extremely secure as long as the key is long enough.

The significance of this general conjecture, assuming its truth, is easy to see.  It means that it is quite feasible to design ciphers that are effectively unbreakable.

He says that he can’t prove the conjecture, and in fact expresses doubt that it is provable.  (So far, he’s right about that.)  But it seems clear that he grasped the essence of the problem quite a while before it was generally realized.  I was very glad when I heard that he had won the Nobel Prize; he did not have an easy life, and his contributions deserved recognition.  I’m similarly glad to see this work emerge from the shadows.