Nash and the NSA

By now most of you have heard about Nash's recently released letters to the NSA (press release, letters). Not only did John Nash think about computation and cryptography, there are many ideas in these letters that were a bit ahead of their time when Nash sent these letters in 1955.

• Expressing a cryptographic process as a Boolean function with input bits. 
• Breaking the cryptographic system as a function of the key length.
• Exponential in key length as computationally hard and polynomial in key length is computationally easy.

His conjecture is quite striking.

For almost all sufficiently complex types of enciphering, especially where the instruction given by different portions of the key interact complexly with each other in the determination of their ultimate effects on the enciphering, the 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 become more sophisticated the game of cipher breaking by skilled teams, etc. should become a thing of the past.

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. 

Nash's conjecture, even for a specific cipher, would imply P ≠ NP, 16 years before Cook defined the problem, and the significance resonates with the Diffie-Hellman article written 21 years later

Theoretical developments in information theory and computer science show promise of providing provable secure cryptosystems, changing this ancient art into a science.

Given Nash's insights, why did the NSA react so cautiously to these letters.

• This was not a letter from Nobel Laureate Nash but from Assistant Professor Nash.
• There is a strong positive correlation between people who claim they are not a crank and those that are.
• Nash's arguments didn't apply that well to the relatively slow digital computers of the time.
• Nash didn't give a particularly useful cryptosystem.
• I don't even believe Nash's conjecture: There are plenty of complex enciphering techniques, such as the Engima machine, which the NSA did know how to break. Hard to break cryptosystems come from more structured ciphers based on algebraic properties like AES and RSA.