From: hal@finney.org
Date: Thu Jul 08 1999 - 11:08:52 MDT
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
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 15:04:25 MST