Shared publicly  - 
The National Security Agency (NSA) has recently declassified an amazing letter that John Nash sent to it in 1955. It seems that around the year 1950 Nash tried to interest some US security orga...
Kevin McCurley's profile photo
The connections between computational efficiency and cryptanalysis were already becoming apparent in the time of Babbage, but that predates any hypotheses on lower bounds as far as I can tell. It's unfortunate that Nash's early formulation is for a key recovery attack, which overlooks the possibility of recovering plaintext without recovering the key. It's probably most interesting in his suggestion of an exponential lower bound - are there any other hypotheses about exponential separation between the time of Turing and 1955?

I really like the way he crossed out information and wrote instructions instead. Shannon's paper was declassified in 1949, so maybe he wanted to distinguish the information-theoretic approach from the complexity-theoretic approach.
Add a comment...