[sorry if this is way out of it, I haven't had time to keep up with my c-punks mail lattely] Duncan writes
It's easier to make an omlette out of eggs than to make eggs out of an omlette so encryption should remain well ahead of decryption.
As I'm sure somebody else has pointed out somewhere along this thread, the ability to simultaneously analyze a superposition of an arbitrarilly large subset of all possible imputs (as our theoretical quantum cryptanalytic device might) implies to ability to solve, in polynomial time, any exponential time problem. [Its easy to consider a device which, given a superposition of a subset of all numbers less than 2^n, delivers as output a confirmation or denial that one of the numbers in the subset is a factor of the input modulus. Such a device can factor in order n time complexity simply by playing higher lower games and guessing one bit at a time] I want to take issue Duncan's analogy here however. It starts off well:
"It's easier to make an omlette out of eggs than to make eggs out of an omlette"
This is like saying entropy always wins, which it does. It will always be easier to take apart and destroy than to create. Then he continues:
So encryption should remain well ahead of decryption
Which process is increasing order and which process is increasing entropy? I think an encrypted message is a highly ordered construct. In its natural state, information can be read by everyone. Upon this state encryption imposes order. It allows a specific subset of all entities to read the information. In the total cyberspatial system, none of the original information has been lost, yet new information has been added. I look at encryption as the tool that will allow us to build up an orderly society within the natural anarchy of cyberspace. Encryption is an artifact of order. And as such I would expect science to eventually uncover a mechanism that makes it easier to breakdown this order than to create it in the first place. I suppose it is plausible that there exists a class of Quantum-Hard problems, but it is difficult for me to conceptualize such a class of problems. It seems like quantum computation is capable of decreasing the time complexity of any problem to its logarithm an arbitrarilly large number of times. [Not that I believe for one moment that it is likely that quantum cryptanalytic machines will be developed that are sufficiently fault tolerant (if the term can even be applied to a system like this) to overcome the coupling between the quantum computer and the surrounding environment in the next couple of decades.] Cheers, Jason W. Solinsky