Shared publicly  - 
16
14
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...