Amazing new declassified document

Its been a long time since I've posted on this blog, but along comes a great opportunity. Michael Kearns (tipped off by Ron Rivest) pointed me to a document this morning: http://courses.csail.mit.edu/6.857/2012/files/H03-Cryptosystem-proposed-by-Nash.pdf

What this is, is a recently declassified correspondence between John Nash and the NSA from January 1955. In it, John Nash makes the distinction between polynomial time and exponential time, conjectures that there are problems that -cannot- be solved faster than in exponential time, and uses this conjecture as the basis on which  the security of a cryptosystem (of his own design) relies. He also anticipates that proving complexity lower bounds is a difficult mathematical problem:

"The nature of this conjecture is such that I cannot prove it, even for a special type of cipher. Nor do I expect it to be proven. But this does not destroy its significance. The probability of the truth of the conjecture can be guessed at on the basis of experiencing with enciphering and deciphering"


These letters predate even Godel's letter to Von Neumann, which goes into much less detail about complexity, and yet has also been taken to anticipate complexity theory and the P vs. NP problem.

Finally, an amusing aspect of this document is that it contains the NSA's internal notes on the correspondence. After a page or so of explanation as to why they are rejecting Nash's proposed system, they include the following offhand remark before finishing:

"An interesting pamphlet on Non-Cooperative Games, written by Mr. Nash was also sent to this Agency by the author for our information."