bradbury@aeiveos.com, Robert J. Bradbury, writes:
> Question: Does anyone know if there is an encryption
> methodology that will work if QC cracks the factoring problem?
Quantum computers threaten cryptography in two known ways, so far. They greatly speed up factoring and the related problem of finding discrete logs, which are the basis for the standard public key cryptography algorithms in wide use today. They also accelerate key search for "conventional" secret-key ciphers like DES, so that you need to use twice the key lengths that you would otherwise.
This second attack is not too troublesome, in that we can solve it by going to larger keys. This is why the in-development Advanced Encryption Standard (AES) specifies keys up to 256 bits in size. The only reason to use such large keys is in case quantum computers work, in which case they would then have the equivalent strength to 128 bit keys today, which is extremely strong.
The first attack, against public key cryptography, would be a larger problem. RSA, DSA, and elliptic curve variants would all be hit, and it is not clear that going to larger keys would help. However, there are some alternative public key systems which are not used much today but which might be practical. There were a number of systems devised in the early days of PKC based on the knapsack problem, most of which were broken; I think the last remaining variant fell last year. But perhaps with some further looking this method could be brought back. There is also a system from McEliece based on coding theory, which has very cumbersome keys but uses different mathematical principles. Some Chinese groups have worked on finite automata based public key systems but I don't know much about them.
So if large quantum computers become practical, researchers do have a few alternatives to fall back on. They have not generally been well studied though so no doubt there would be many cracks and new systems developed as people focus on these areas. In the end I imagine that it would still be possible to use cryptography as we have it today, but it would be more expensive and difficult.
Hal