John Nash’s Letter to the NSA The National Security Agency (NSA) has recently declassified an amazing letter that John Nash sent to it in 1955. It seems that around the year 1950 Nash tried to interest some US security organs (the NSA itself was only formally formed only in 1952) in an encryption machine of his design, but they did not seem to be interested. It is not clear whether some of his material was lost, whether they ignored him as a theoretical professor, or — who knows — used some of his stuff but did not tell him. In this hand-written letter sent by John Nash to the NSA in 1955, he tries to give a higher-level point of view supporting his design. He then goes on to put forward an amazingly prescient analysis anticipating computational complexity theory as well as modern cryptography. In the letter, Nash takes a step beyond Shannon’s information-theoretic formalization of cryptography (without mentioning it) and proposes that security of encryption be based on computational hardness — this is exactly the transformation to modern cryptography made two decades later by the rest of the world (at least publicly…). He then goes on to explicitly focus on the distinction between polynomial time and exponential time computation, a crucial distinction which is the basis of computational complexity theory, but made only about a decade later by the rest of the world.

John Nash’s Letter to the NSA

The National Security Agency (NSA) has recently declassified an amazing letter that John Nash sent to it in 1955.  It seems that around the year 1950 Nash tried to interest some US security organs (the NSA itself was only formally formed only in 1952) in an encryption machine of his design, but they did not seem to be interested.  It is not clear whether some of his material was lost, whether they ignored him as a theoretical professor, or — who knows — used some of his stuff but did not tell him.  In this hand-written letter sent by John Nash to the NSA in 1955, he tries to give a higher-level point of view supporting his design:

He then goes on to put forward an amazingly prescient analysis anticipating computational complexity theory as well as modern cryptography.  In the letter, Nash takes a step beyond Shannon’s information-theoretic formalization of cryptography (without mentioning it) and proposes that security of encryption be based on computational hardness — this is exactly the transformation to modern cryptography made two decades later by the rest of the world (at least publicly…).  He then goes on to explicitly focus on the distinction between polynomial time and exponential time computation, a crucial distinction which is the basis of computational complexity theory, but made only about a decade later by the rest of the world:

So a logical way to classify enciphering processes is by t he 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, or , as in substitution ciphers. He conjectures the security of a family of encryption schemes.  While not totally specific here, in today’s words he is probably conjecturing that almost all cipher functions (from some — not totally clear — class) are one-way:

Now my general conjecture is as follows: for almost all sufficiently complex types of enciphering, especially where the instructions given by different portions of the key interact complexly with each other in the determination of their ultimate effects on the enciphering, the mean key computation length increases exponentially with the length of the key, or in other words, the information content of the key.

He is very well aware of the importance of this “conjecture” and that it implies an end to the game played between code-designers and code-breakers throughout history.  Indeed, this is exactly the point of view of modern cryptography.

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.  As ciphers become more sophisticated the game of cipher breaking by skilled teams, etc., should become a thing of the past.

He is very well aware that this is a conjecture and that he cannot prove it.  Surprisingly, for a mathematician, he does not even expect it to be solved.  Even more surprisingly he seems quite comfortable designing his encryption system based on this unproven conjecture.  This is quite eerily what modern cryptography does to this day: conjecture that some problem is computationally hard; not expect anyone to prove it; and yet base their cryptography on this unproven assumption.

The nature of this conjecture is such that I cannot prove it, even for a special type of ciphers.  Nor do I expect it to be proven. All in all, the letter anticipates computational complexity theory by a decade and modern cryptography by two decades.  

Not bad for someone whose “best known work is in game theory”.  It is hard not to compare this letter to Goedel’s famous 1956 letter to von Neumannalso anticipating complexity theory (but not cryptography).  That both Nash and Goedel passed through Princeton may imply that these ideas were somehow “in the air” there.

This declassified letter seems to have been picked up by Ron Rivest who posted it on his course’s web-site, and was then blogged about (and G+ed) by Aaron Roth.