I think that incremental progress is very much the norm as you say; it might be informative to compile a list of exceptions.
In cryptanalysis, a problem that the cipher designers believed was 2^256 complexity can turn out to be 2^24 or less. However, this rarely happens with ciphers that have been around a long time.
Nuclear bombs were far more powerful than any bomb that preceded them; destruction in war certainly counts as a problem that has got a lot of attention over a long time.
I think this is a good thing to compile a list of. Paul and I started one on the AI impacts site, but have only really got into looking into the nuclear case. More examples welcome!
Could you tell me more about the cipher example? Do you have particular examples in mind? Does the practical time of solving something actually decrease precipitously, or are these theoretical figures?
The example I had in mind was “Differential Cryptanalysis of Nimbus”. The author of Nimbus believed that the cipher could not be broken with less work than a brute force attack on all 2^128 keys. The cryptanalysis broke it with 256 chosen plaintexts and 2^10 work. However, the gap between publication and break was less than a year.
Regarding cryptanalysis. yes it is known to happen that various proposed and sometimes implemented systems are found to be trivially breakable due to analysis not foreseen by their inventors. Examples are too numerous, but perhaps something like differential cryptanalysis might be something to look into.
I think that incremental progress is very much the norm as you say; it might be informative to compile a list of exceptions.
In cryptanalysis, a problem that the cipher designers believed was 2^256 complexity can turn out to be 2^24 or less. However, this rarely happens with ciphers that have been around a long time.
Nuclear bombs were far more powerful than any bomb that preceded them; destruction in war certainly counts as a problem that has got a lot of attention over a long time.
I think this is a good thing to compile a list of. Paul and I started one on the AI impacts site, but have only really got into looking into the nuclear case. More examples welcome!
Could you tell me more about the cipher example? Do you have particular examples in mind? Does the practical time of solving something actually decrease precipitously, or are these theoretical figures?
The example I had in mind was “Differential Cryptanalysis of Nimbus”. The author of Nimbus believed that the cipher could not be broken with less work than a brute force attack on all 2^128 keys. The cryptanalysis broke it with 256 chosen plaintexts and 2^10 work. However, the gap between publication and break was less than a year.
Regarding cryptanalysis. yes it is known to happen that various proposed and sometimes implemented systems are found to be trivially breakable due to analysis not foreseen by their inventors. Examples are too numerous, but perhaps something like differential cryptanalysis might be something to look into.