- 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.
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.