Russell Nelson <[EMAIL PROTECTED]> writes:
> If
> quantum computers make brute-force cryptanalysis tasks easier, don't
> they also make brute-force cryptographic tasks easier as well? Put
> another way, is there something special about quantum computers that
> is different from Intel's next process shrink? That is, apart from
> the havoc it plays with key lifetime expectations?
Quantum computers help cryptanalysis in a couple of specific ways.
They aren't all-purpose speeder-upers.
Shor's algorithm is a fast method for finding discrete logs and prime
factors, in polynomial time.
Grover's algorithm is a fast general-purpose search method. Normally if
you want to try all 2^n keys to see which one decrypts a message, it takes
close to 2^n tries. Grover's algorithm lets you get by with the square
root of that many tries.
Neither of these algorithms seems of much value for encryption.
If quantum computers become practical, dealing with Grover's algorithm
is not a problem. Use 256 bit keys in the AES and you will still have
128 bits of security.
Dealing with of Shor's algorithm is more difficult. There are some public
key techniques that don't rely on discrete logs or factoring: some based
on coding theory; possibly some based on knapsacks/lattices; rumors of
CA based systems. It would be good to have reliable public key systems
which use other methods than the traditional number theory trapdoors.
