17 February 2012
We know that Kurt Gödel, unhappy with having only completeness and incompleteness theorems named after him, also essentially invented the P vs NP question in a 1956 letter to John Von Neumann. Unfortunately, there were no blogs back then, so we had to wait until the 1980s to read it, and Cook, Karp & co. had to reinvent the question from scratch.
What we didn’t know until a few days ago (I personally discovered it today via Aaron Roth) is that in 1955, one year before Gödel’s letter, John Nash also had something to say on the topic, in a few letters to NSA. Gödel and Nash independently made strikingly similar remarks, starting from completely different points of view. While Gödel’s perspective was that of a logician (his letter was about the length of proofs in first-order logic), Nash was interested in cryptography, and wrote about the security of cryptographic systems.
NSA’s press release about the declassification of Nash’s letters was apparently made on 27 January 2012; here is a PDF containing Nash’s letters and the replies he got from NSA. I’ll only focus on the second letter here, leaving a cryptoanalysis of the system he proposed in the third one to someone more knowledgeable than me on the topic.
I assume Nash was familiar with Shannon’s work Communication theory of secrecy systems (1949), so he already knew that the only mathematically unbreakable cipher is one-time pad. Hence, in order to discuss practical encryption systems, he invented the principles of modern cryptography about 20 years in advance:
If [the computation required in order to recover the key from the ciphertext], although possible in principle, were sufficiently long at best then the process could still be secure in a practical sense.
Here is some computational complexity, 8 years before Hartmanis and Stearns:
The most direct computation procedure would be for the enemy to try all 2r possible keys, one by one. Obviously this is easily made impractical for the enemy by simply choosing r large enough.
Apparently Nash already knew quite well (“obviously”, “easily”) that exponential time is too much.
And here is how one can classify cryptosystems (but also general computation problems) according to him. I think you can read essentially the same paragraph in all modern complexity theory and cryptography books.
So a logical way to classify enciphering processes is by the 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 a relatively small power of r, ar2 or ar3, as in substitution ciphers.
Nash also conjectures that many problems cannot be solved in polynomial time. In hindsight, there is some naivety here about the design of good ciphers, but this is still very interesting:
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, with the information content of the key. 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 became more sophisticated the game of cipher breaking by skilled teams, etc., should become a thing of the past.
All in all, this seems to me a truly magnificent historical document, possibly on par with the aforementioned letter by Gödel. I’d really like to know what people working in cryptography think about this.
These “Lost Letter” discoveries also make me wonder what further treasures may be hidden in NSA’s cardboard boxes, or in private correspondence collections. What if there exists a “Fermat’s Lost (Last?) Letter” along the lines of “Here’s the proof that didn’t fit in the margin”, or a “Russell’s Lost Letter” that he sent to Whitehead to tell him “I found a proposition that can’t be proved nor refuted in Principia Mathematica”?