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,
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 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.
That is awesome.
Reblogged this on My Blog.
unbelievable. comparable to von neumann
just amazing. a mixture of godel + von neumann
“A beautiful mind” indeed. Peace.
Reblogged this on Kalpesh Padia’s Blog and commented:
Clearly John Nash was way ahead of his time… Schizophrenic, but super smart.. Respect!
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.
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?
So does this invalidate any patents due to prior art?
This. All hell will brake loose in 3…2..1..
Not unless it was made available to the public
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.
“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.
“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).
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
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.
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.)
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.
Hey,
I would be very interested in knowing how you did it.
Can you please Elaborate?
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.
Reblogged this on Vcjha's Blog.
“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.
“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.
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.
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/
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
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.
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.
I’ve made a full HTML transcription of the PDF: http://gwern.net/docs/1955-nash
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.
Reblogged this on "Random" thoughts and commented:
Nash and cryptography…
Amazing, Reblogged on my blog
This is amazing.. John Nash’s work has always been an inspiration.
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?
Reblogged this on Code through the Looking Glass.
A nice text, except for this sentence: “Not bad for someone whose ‘best known work is in game theory'”.
Awesome! Did he sent it when he was having delusional problems?
I drop a comment whenever I appreciate a post on a site or I
I actually do have some
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?
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
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?
Great article, great blog!
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!
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.
It was created by a brand new personal fitness educator named Craig Ballantyne from Ontario.
The particular great exercise/activity regarding
consider for pounds burning workouts often is cardio kickboxing.
I am genuinely thankful to the owner of this site who has shared this
fantastic piece of writing at at this place.
Hey There. I found your blog the use of msn. This
is an extremely neatly written article. I will make sure to bookmark it and
come back to learn more of your useful information.
Thank you for the post. I will definitely return.
What! NSA used Nashs’ stuffs without telling him? There must have been some serious security reason. Anyway, now that they have given the work credit to him, there is no complain.
With 20-20 hindsight, one may imagine in the letter the roots of the Feistel cipher: one way functions based on key-driven combinations of simple functions, cascading to arbitrary depth.
Or maybe it’s just my imagination.
Reblogged this on Subhayan Roy Moulick.
It iis not my first time to visit this web site, i amm visiting
this website dailly and obtain fastidious data from here everyday.
I’m contemplating starting my own web site. Can you provide
me with a couple of ideas?
Your website is actually fantastic. Can I follow
you on Google??
Where did you learn to write so well?? I wish to setup my very own website and get started
creating an income from it.
It’s appropriate time to make a few plans for the long run and it is time to be happy.
I’ve learn this submit and if I may I want
to counsel you few fascinating issues or
advice. Maybe you could write subsequent articles referring to this article.
I want to read even more things about it!
There’s definately a great deal to learn about this subject.
I love all the points you’ve made.
I know this if off topic but I’m looking into starting my own blog and was curious what all is required to get set up?
I’m assuming having a blog like yours would cost a pretty penny?
I’m not very internet savvy so I’m not 100% certain. Any recommendations or advice would be greatly appreciated.
Appreciate it
What’s up Dear, are you genuinely visiting this site on a regular basis,
if so after that you will without doubt take nice know-how.
Great write up!
I like reading through a post that will make men and women think.
Also, thank you for allowing me to comment!
very nice
Rest in peace this brilliant man and his wife who helped him so much.
Magnificent website. A lot of useful info here.
I’m sending it to a few pals ans additionally sharing in delicious.
And obviously, thanks for your sweat!
Michael admitted furthermore that he had molested multiple girls in his
neighborhood as a teenager. The series consisted of
thirteen episodes, each of which was forty five minutes in length.
Just as V was a False User, so is Zamorak, and the Dragonkin aim to make you pay the price
for having played a part in the heist.
Thanks for giving outstanding informations. Your web-site is very cool.
I’m impressed by the details that you simply have on this site.
It reveals how nicely you perceive this subject. Bookmarked
this web site, will keep coming back for extra articles.
You, my good friend, ROCK!
Snap – Chat’s Android counterpart is called “Fancy Snap”
and is also rated Medium. It’s hard to say that there is because the situation of different people will have different solutions.
His audience attracts to that and then he throws in his vodka or his shirts in the video so it
is setting into your subconscious.
For instance, the percentage of works are known for having
reasonably. Climb all the way to the top, picking up a handful of useful items along the way if you wish.
) into an intense, and gripping war of the new millennia.
Hi, jjust wanted to ѕay, I loved thіs article.
It was funny. Keeep oon posting!
Yourr way of telling the whole thing in this piece of writing is truly good, ebery one can without difficulty be aware of it, Thanks a lot.
THE BEAUTY OF THE INTERNET FOR INSTANT INFORMATION! NOW THAT IS A GRAND EXPERIMENT! John Nash papers are correct, from 20 years ago to today! I am no scholar, in fact, I have never been to college! I have to announce this today, 25 January 2017. This is James Spellman! I founded BITCOIN in 2006. I spent years researching John Nashs letter. Most letters, i have to say, I was too stupid to understand! I have some good experience in computers and programming though(self taught)! Right now going eye blind. I started cryptography encryption research using C++ and Plython, reading John Nashs whitepapers and basing my Bitcoin creation with his papers and the Blockchain Ledger IN ENCRYPTION & DECRYPTION Technologies. That is what fixed the “Double Spend Problem” of digital currency in bitcoin and fiat credit cards as we enter a new age. Somehow over a course of a year, I decifered the meanings to his papers, taking certain words and researching their meanings and interpretations and from my interest in his theories, I began to research Federal Banking Laws to find out if virtual internet money was even legal. After months of intense reading and interpretation, I concurred a gray area of exploration, upon which I think I could build a platform, legally! I found in discussion in 2008, after asking numerous computer techs for the previous year if they knew cryptography, A Satoshi Nakamoto who not only knew cryptography, but encryption/decryption theories in a Blockchain ledger in March 2008. I couldn’t believe it! A genuine computer genius! The rest is our book of design. I put Bitcoin on a MIT open source license after discussion with a cia agent in my previous travels, to keep our extricating art safe from the evil that lurks, even today! In John Nashs life, he spent time in a institution for mental health that he didn’t have to be. “A Beautiful Mind” might have been a great movie, but like him and I, we think “out of the box” compared to “normal” people. Now after intense thought, theories, and research, we burnout real hard. So intense we need years to recover for new projects. To be great, we are always trying to work on new theories of product designs. The NSA in red ties, who visited him for ideas, I believe were real! He was not imagining things! They are always looking to take from the idealists. I have been approached too! Mr. Nash was genius in 22 whitepapers, published to this day! RIP John Nash! You have 1 strong admirer!
P versus NP is considered one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This incognita was first mentioned in a letter written by John Nash to the National Security Agency in 1955. Since that date, all efforts to find a proof for this huge problem have failed.
I show a solution to that problem as follows:
Given a number x and a set S of n positive integers, MINIMUM is the problem of deciding whether x is the minimum of S. We can easily obtain an upper bound of n comparisons: find the minimum in the set and check whether the result is equal to x. Is this the best we can do? Yes, since we can obtain a lower bound of (n – 1) comparisons for the problem of determining the minimum and another obligatory comparison for checking whether that minimum is equal to x. A representation of a set S with n positive integers is a Boolean circuit C, such that C accepts the binary representation of a bit integer i if and only if i is in S. Given a positive integer x and a Boolean circuit C, we define SUCCINCT-MINIMUM as the problem of deciding whether x is the minimum bit integer which accepts C as input. For certain kind of SUCCINCT-MINIMUM instances, the input (x, C) is exponentially more succinct than the cardinality of the set S that represents C. Since we prove that SUCCINCT-MINIMUM is at least as hard as MINIMUM in order to the cardinality of S, then we could not decide every instance of SUCCINCT-MINIMUM in polynomial time. If some instance (x, C) is not in SUCCINCT-MINIMUM, then it would exist a positive integer y such that y < x and C accepts the bit integer y. Since we can evaluate whether C accepts the bit integer y in polynomial time and we have that y is polynomially bounded by x, then we can confirm SUCCINCT-MINIMUM is in coNP. If any single coNP problem cannot be solved in polynomial time, then P is not equal to coNP. Certainly, P = NP implies P = coNP because P is closed under complement, and therefore, we can conclude P is not equal to NP.
You could read the details in the link below…
https://hal.archives-ouvertes.fr/hal-01509423/document
Hi, sometimes I see a 503 site message when I arrive at your site. Just a heads up, regards
Appreciating the dedication you put into your website and detailed information you offer.
It’s awesome to come across a blog every once in a while that
isn’t the same old rehashed material. Excellent read!
I’ve bookmarked your site and I’m including your RSS feeds to my Google account.
First of all I would like to say fantastic blog! I had a quick question that I’d like to ask if you don’t mind.
I was interested to find out how you center yourself and clear your
thoughts before writing. I’ve had a tough time clearing my mind in getting my ideas out there.
I do enjoy writing but it just seems like the first 10 to 15 minutes tend to be wasted simply just trying to figure
out how to begin. Any suggestions or tips? Kudos!
rslhM2ovK4FZ1OV0nojdIvJVK1Ppn
4/30/2020