**“docs/cs/1955-nash”** links:

`1955-nash-nsacryptography.pdf`

: “Correspondences Regarding Cryptography between John Nash and the NSA”, (1955-01; ):[In 1955, well-known mathematician John Nash was in correspondence with the United States National Security Agency. In these letters, Nash proposes a novel enciphering scheme. He also sets forth an important cryptographic principle that now underpin modern computational complexity theory and cryptography. In particular, he proposes a natural definition for “[security] in a practical sense”—that exponential computational effort is required for an enemy to recovery a secret key. Nash further conjectures that this property holds for any suitable enciphering mechanism.

These correspondences, recently declassified by the NSA [1]; this document is the NSA scan with original images and drawings of Nash’s handwritten letters.]

`1955-nash-typeset.pdf`

: “Correspondences Regarding Cryptography between John Nash and the NSA [typeset version]”, (2012-02-20; ):In 1955, well-known mathematician John Nash was in correspondence with the United States National Security Agency. In these letters, Nash proposes a novel enciphering scheme. He also sets forth an important cryptographic principle that now underpin modern computational complexity theory and cryptography. In particular, he proposes a natural definition for “[security] in a practical sense”—that exponential computational effort is required for an enemy to recovery a secret key. Nash further conjectures that this property holds for any suitable enciphering mechanism.

These correspondences, recently declassified by the NSA [1], have been transcribed and typeset in this document. [Typeset by Mike Rosulek: Department of Computer Science, University of Montana, mikero@cs.umt.edu]

“National Cryptologic Museum Opens New Exhibit on Dr. John Nash”, (2012-01-27):

The National Cryptologic Museum’s newest exhibit, “An Inquisitive Mind: John Nash Letters”, features copies of correspondence between Dr. Nash and the National Security Agency (NSA) from the 1950s when he was developing his ideas on an encryption-decryption machine.

At the height of his career in mathematics, Dr. Nash wrote a series of letters to NSA, proposing ideas for such a machine. While the agency acknowledged his ideas, they were never adopted. The letters were preserved with NSA’s analysis in a collection of unsolicited correspondence received in 1955.

The unclassified letters and the agency’s analysis, portions of which were classified, remained protected in NSA’s records center until 2011, when the entire collection was reviewed and declassified. The entire collection is being formally accessioned to the National Archives and Records Administration and will be available for public viewing later this year.

Copies of Nash’s letters to NSA are on display at the National Cryptologic Museum with complete copies available for review in the museum’s library and on the museum’s web page.

`https://en.wikipedia.org/wiki/Nobel_Memorial_Prize_in_Economic_Sciences`

`2012-johnson.pdf`

: “A Brief History of NP-Completeness, 1954–2012”, (2012-01-01; ):The year 2012 marks the 40

^{th}anniversary of the publication of the influential paper “Reducibility among combinatorial problems” by Richard Karp. This paper was the first to demonstrate the wide applicability of the concept now known as NP-completeness, which had been introduced the previous year by Stephen Cook and Leonid Levin, independently. 2012 also marks the 100^{th}anniversary of the birth of Alan Turing, whose invention of what is now known as the “Turing machine” underlay that concept. In this chapter, I shall briefly sketch the history and pre-history of NP-completeness (with pictures), and provide a brief personal survey of the developments in the theory over the last 40 years and their impact (or lack thereof) on the practice and theory of optimization. I assume the reader is familiar with the basic concepts of NP-completeness, P, and NP, although I hope the story will still be interesting to those with only a fuzzy recollection of the definitions.`http://blog.practical-scheme.net/gauche/20120715-nash-cipherer`

`http://aaronsadventures.blogspot.com/2012/02/amazing-new-declassified-document.html`

`http://agtb.wordpress.com/2012/02/17/john-nashs-letter-to-the-nsa/`

`https://en.wikipedia.org/wiki/Communication_Theory_of_Secrecy_Systems`

`https://en.wikipedia.org/wiki/History_of_cryptography#Modern_cryptography`

`https://en.wikipedia.org/wiki/Computational_complexity_theory`

`2003-fortnow.pdf`

: “A Short History of Computational Complexity”, Fortnow, Lance, Homer, Steve`http://agtb.wordpress.com/2012/02/17/john-nashs-letter-to-the-nsa/#comment-5455`

`http://agtb.wordpress.com/2012/02/17/john-nashs-letter-to-the-nsa/#comment-5465`

`http://agtb.wordpress.com/2012/02/17/john-nashs-letter-to-the-nsa/#comment-5458`

`https://en.wikipedia.org/wiki/Linear_feedback_shift_register`

`https://en.wikipedia.org/wiki/Merkle-Hellman_knapsack_cryptosystem`