John Nash's Letter to the NSA

« STOC 2012 accepted papers

Summer school on algorithmic economics »

John Nash’s Letter to the NSA

February 17, 2012 by Noam Nisan

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:

In this letter I make some remarks on a general principle relevant to enciphering in general and to my machine in particular.

He tries to make sure that he will be taken seriously:

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 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, $ar^2$ or $ar^3$ , 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 Neumann also 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.

ht: 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.

Edit: Ron Rivest has implemented Nash’s cryptosystem in Python. I wonder whether modern cryptanalysis would be able to break it.

About these ads

Posted in Uncategorized | 41 Comments

41 Responses

on February 18, 2012 at 2:35 am | Reply Amit C

That is awesome.
on February 18, 2012 at 6:11 am | Reply G'Day

Reblogged this on My Blog.
on February 18, 2012 at 7:20 am | Reply Anonymous

unbelievable. comparable to von neumann
on February 18, 2012 at 7:22 am | Reply me

just amazing. a mixture of godel + von neumann
on February 18, 2012 at 9:00 am | Reply Whitecorp

“A beautiful mind” indeed. Peace.
on February 18, 2012 at 11:09 am | Reply kalpeshpadia

Reblogged this on Kalpesh Padia’s Blog and commented:
Clearly John Nash was way ahead of his time… Schizophrenic, but super smart.. Respect!
on February 18, 2012 at 12:39 pm | Reply David Morris

Does that mean that NSA had this before the english guy Clifford Cocks invented it at GCHQ in 1972:

At GCHQ, Cocks was told about James H. Ellis’ “non-secret encryption” and further that since it had been suggested in the late 1960s, no one had been able to find a way to actually implement the concept. Cocks was intrigued, and invented, in 1973, what has become known as the RSA encryption algorithm, realising Ellis’ idea. GCHQ appears not to have been able to find a way to use the idea, and in any case, treated it as classified information, so that when it was reinvented and published by Rivest, Shamir, and Adleman in 1977, Cocks’ prior achievement remained unknown until 1997.
(From the Clifford Cocks article on Wikipedia)

or were NSA still stuck in the “no one had been able to find a way to actually implement the concept”.

“That both Nash and Goedel passed through Princeton may imply that these ideas were somehow “in the air” there.” I love the thought that an idea can live “in the air”, be dropped, almost forgotten, hinted at, rediscovered and finally resolved in an institution like Princeton.
on February 18, 2012 at 6:51 pm | Reply Anonymous

Re: David Morrris

You’re referring to the invention of asymmetric (public key) cryptography right? Does Nash’s letter have anything at all to do with public key cryptography?
on February 18, 2012 at 7:44 pm | Reply Dr. Kenneth Noisewater

So does this invalidate any patents due to prior art?
- on February 18, 2012 at 8:53 pm | Reply me
  
  This. All hell will brake loose in 3…2..1..
- on February 19, 2012 at 4:36 am | Reply Anonymous
  
  Not unless it was made available to the public
on February 18, 2012 at 10:34 pm | Reply Markus Kroetzsch

Some caution is needed here. As always when interpreting historic writings, one is naturally tempted to use a modern perspective, based on knowing the current state of affairs. In addition, it is tempting to attribute such phenomenal foresightedness to a well-established genius.

After reading the letter, it seems clear to me that Nash *did* foresee important ideas of modern cryptography. This is great and deserves recognition.

However, it seems also very clear that he did not foresee (in fact: could not even imagine) modern complexity theory. Why else would he say that he does not think that the exponential hardness of the problem could ever be proven? It is true that the computational hardness of key tasks in modern cryptography is an unsolved problem, but we have powerful tools to prove hardness results in many other cases. So if Nash had anticipated complexity theory as such, then his remark would mean that he would also have foreseen these difficulties. To foresee this, however, he would not only have to understand the development of complexity theory in great detail, but also to anticipate the principles of today’s encryption mechanisms. It seems reasonable to assume that he would have shared the latter in his letter if he had really had this insight.

Overall, it seems clear that a prediction of complexity theory or its current incapacity with respect to cryptographic problems cannot be found in this text, which does by no means diminish the originality of the remarks on cryptography. One could also grant him a certain mathematical intuition that some computational problems could be inherently hard to solve, although I don’t see any hint that he believes that such hardness could ever become a precise mathematical property. What he suggests is really close to the pragmatic approach of modern cryptography, but not to modern complexity theory.
- on February 20, 2012 at 1:46 am | Reply Greg
  
  “t is true that the computational hardness of key tasks in modern cryptography is an unsolved problem, but we have powerful tools to prove hardness results in many other cases.”
  
  Not really— we’ve only proven things to be hard if and only if P!=NP. This is useful, but we’ve still not actually proven anything to be hard at all— only proven that there are a set of things which if any of them turn out to be easy a whole bunch of other things must be ‘easy’ too.
  - on February 20, 2012 at 12:21 pm Markus Kroetzsch
    
    “we’ve only proven things to be hard if and only if P!=NP.”
    
    Regarding the class NP you are of course right. But our modern tools do not end at NP. For example, we know that ExpTime is strictly harder than P, and we have shown many problems to be hard for ExpTime. At Nash’s time, ExpTime and NP would largely be synonyms (I have not traced back the exact history of these notions, but at least the letter seems to mix both concepts).
  - on February 20, 2012 at 8:58 pm Alex Ogier
    
    Just to clarify, Markus is separating Complexity Theory, where we have plenty of solid hardness results, from Cryptography, where basically every assumption of hardness boils down to an unproven conjecture.
    
    The point being that this letter provides no evidence that Nash foresaw any of the structure that would allow proofs of hardness for any problem, and since this structure is foundational in complexity theory, it is reasonable to conclude that he didn’t foresee complexity theory in any meaningful way.
    
    In other words, while Nash saw the negative side of complexity theory — that mathematics would find it difficult to reason about the reversibility of one-way functions — he didn’t have any particular insight into the positive side of complexity theory, that there would exist structure to classify the computational difficulty of many other problems
on February 19, 2012 at 12:41 am | Reply Tom

It’s interesting that, to conceal a message, you make it look like noise, and to get a message through a noisy channel, you do the same thing.
- on February 22, 2012 at 10:58 pm | Reply Maia
  
  Like when you hear the sounds (or see the motions of) words and decode them. (I know too little to understand whether that is accurate or dumb.)
on February 19, 2012 at 5:47 am | Reply Philonus Atio

Regarding ” I wonder whether modern cryptanalysis would be able to break it.”

I broke it in about 1 hour and I’m no expert in cryptanalysis. It is weak.
- on February 22, 2012 at 10:40 pm | Reply John Smith
  
  Hey,
  
  I would be very interested in knowing how you did it.
  Can you please Elaborate?
  - on February 24, 2012 at 2:24 am Phionus Atio
    
    Sure. Here is a brief outline of strategy for how I broke it. Nash’s machine is essentially a linear feedback shift register (LFSR).
    
    http://en.wikipedia.org/wiki/Linear_feedback_shift_register
    
    The LFSR operates as a weak pseudo-random number generator which is exclusive-ORed (XOR) with the plaintext to produce ciphertext. All you need to do is predict the output of the generator. It cycles in less than 256 bits (i.e. the period). I used ‘known plaintext attacks’ to analyze the behavior of the LFSR. I created an equivalent LFSR using a variation on the Berlekamp-Massey algorithm. Nash’s machine is weak and easy to predict because it is linear.
    
    The rest is left as an exercise for the reader (there are a few minor wrinkles). Happy cracking.
on February 19, 2012 at 1:49 pm | Reply vcjha

Reblogged this on Vcjha's Blog.
on February 19, 2012 at 9:03 pm | Reply Daniel

“It seems reasonable to assume that he would have shared the latter in his letter if he had really had this insight.”

No, it’s fundamentally irrational to assume that. You’re correct that the letter needs to be evaluated within the context on his time; it also needs to be evaluated with author’s purpose in mind. There is nothing in that letter that even hints that his purpose was to “foresee” anything or to give a complete theoretical overview of the subject he was discussing. The author’s purpose is to send a practical note to a government agency in order to generate interest in his ideas because he thinks he can help the country with them. His concern is that no one at the NSA will take him seriously, a concern that in hindsight seems well-founded. It’s grossly unfair in that context that you then come along and criticize him decades later for not being complete enough. It’s a handwritten letter for crying out loud, not a phd thesis.
- on February 20, 2012 at 12:32 pm | Reply Markus Kroetzsch
  
  “it’s fundamentally irrational” … “It’s grossly unfair in that context that you then come along and criticize him”
  
  I think this discussion should not be that emotional I am far from criticizing Nash for writing a letter decades ago. All I am saying is that the letter does not seem to provide evidence for him anticipating computational complexity theory as suggested in the original post. You could be right that his letter does not provide the best basis for judging this (since there can be many reasons for him to not write all that he knew in all detail). Then all we can do is to wait for more conclusive historic material to appear.
on February 20, 2012 at 3:41 am | Reply Geoffrey Watson

This is very interesting as a historical document, but not sure that it supports the interpretations being put on it.

It is not noteworthy that people working in the field anticipate ideas that only later become standard theories (look at the history of any advance in maths or science). From Goedel’s 1956 letter and this Nash letter (with its reference to Prof. Huffman working towards similar objectives) a reasonable historical conclusion is that these ideas were just going around in the usual way.

The “conjecture” is a pretty muddled bit of thinking. It presumably means that Nash thinks that there are such exponentially hard cyphers, but to convert “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” into a prescient anticipation of complexity theory is a big ask.
on February 20, 2012 at 8:32 am | Reply Nuclear Risk

Markus Kroetzsch and Geoffrey Watson make important points in their earlier posts, and I’d encourage people to read them. It’s hard to know exactly what Nash was thinking from just these letters, but it impressed me as similar to some of my own early thoughts on cryptography — but before I had really invested significant time and come up with good results.

In addition to Kroetzsch and Watson’s caveats, I’ll note what appears to be another: Breaking a simple substitution cipher takes a constant amount of time — not dependent on the key size (if one even can think of it as having a variable key size).

If anyone thinks I’ve missed something, please chime in. I read the letters fairly quickly and might have missed a hidden gem.

Martin Hellman
http://www-ee.stanford.edu/~hellman/
on February 20, 2012 at 2:55 pm | Reply ali

i want to share my chapter in artificial organs
i have another chapter in liver cells

any one interested to invite me for his/or her book
on February 20, 2012 at 9:21 pm | Reply unruh

P, NP are really completely irrelevant for crypto. All crypto systems have a small finite key, and the breaking of them is constant (as Hellman points out for substitution cyphers). A problem could go as constant for key lengths less than 10^(10^10) and exponential therefter. It would be “exponential” as far as P, NP,… were concerned, but for crypto it would be useless and would go as a constant since we are never going to use keys that long. Or the key could go as r^(10^10) and the problem would be considered polynomial, but it would be far far stronger then almost any exponential problem as far as crypto is concerned. That the NP hard problems we have looked at easily happen to also be something like exponential for small key lengths is more the “drunk and the lightpost” than anything having to do with the inherent features of the problem. Thus, even if P=NP, it would make no difference to crypto, unless that proof also showed how all P problems could be reduces to , say, linear P problems with small coefficients.
on February 22, 2012 at 11:02 pm | Reply Gennady

Noam, thank you very much for sharing this information in an interesting, annotated form. Ronald Rivest’s implementation of Nash’s Cryptosystem is indeed quite intricate and very well coded and commented, clear to understand.
on February 22, 2012 at 11:07 pm | Reply gwern

I’ve made a full HTML transcription of the PDF: http://www.gwern.net/docs/1955-nash
on February 25, 2012 at 8:17 am | Reply cr8s

It’s comforting to know that in today’s day and age, people of this caliber of genius can just start a blog / Facebook page / YouTube channel about their amazing mathematical ideas and how Ed Harris won’t stop following them around.
on February 25, 2012 at 11:17 am | Reply Shashank Vatedka

Reblogged this on "Random" thoughts and commented:
Nash and cryptography…
on February 25, 2012 at 11:19 am | Reply Shashank Vatedka

Amazing, Reblogged on my blog
on March 13, 2012 at 1:23 am | Reply Vinay

This is amazing.. John Nash’s work has always been an inspiration.
on March 15, 2012 at 6:43 pm | Reply luay

Reblogged this on Luay Baltaji's blog and commented:
A fascinating letter from John Nash to the NSA in 1955: can he prove that “conjecture” security is computationally unbreakable?
on April 13, 2012 at 9:44 pm | Reply chinmaylokesh

Reblogged this on Code through the Looking Glass.
on April 29, 2012 at 3:09 am | Reply Anonymous

A nice text, except for this sentence: “Not bad for someone whose ‘best known work is in game theory’”.
on December 20, 2012 at 9:23 pm | Reply Pranesh

Awesome! Did he sent it when he was having delusional problems?
on December 30, 2012 at 9:12 pm | Reply Ronny

I drop a comment whenever I appreciate a post on a site or I
have something to contribute to the conversation. It’s triggered by the sincerness displayed in the post I looked at. And after this post John Nash�s Letter to the NSA � Turing’s Invisible Hand.
I was excited enough to drop a thought I actually do have some
questions for you if it’s okay. Could it be just me or do a few of the responses look as if they are written by brain dead visitors? And, if you are posting at other online social sites, I would like to follow you. Would you list every one of all your community pages like your twitter feed, Facebook page or linkedin profile?
on February 1, 2013 at 8:39 pm | Reply Thomas Rivera

Great article, great blog!
on February 27, 2013 at 9:00 pm | Reply www.edomovina.net

Wow that was unusual. I just wrote an very long comment but after I clicked submit my comment
didn’t show up. Grrrr… well I’m not writing all that over again.

Anyway, just wanted to say wonderful blog!
on May 2, 2013 at 7:10 pm | Reply Car Insurance

Do you have a spam problem on this site; I also am a
blogger, and I was wondering your situation; many of us have developed some nice practices and we are looking to trade methods with others, be sure to shoot me an email if interested.