From: Hal Finney (hal@finney.org)
Date: Sat Aug 31 2002 - 14:56:56 MDT
There are two known algorithms which would allow quantum computers to
threaten cryptographic systems in widespread use today. Shor's algorithm
can factor numbers and find discrete logs; and Grover's algorithm can
speed up general search problems.
Most cryptosystems in use today are hybrids, where a relatively slow
public key operation like RSA is combined with a fast symmetric algorithm
like the new AES. RSA is used to encrypt the AES key, which is then
used to encrypt the rest of the message. Quantum crypto could attack
both of these parts.
RSA relies on the hardness of factoring, and Shor's algorithm provides
a fast way to factor. Note that you need more qubits (quantum bits)
than the size of the RSA key, due to error correction. Estimates I have
seen vary from around a factor of 10 to a factor of 1000 more qubits
than bits in the RSA key. Typical RSA key sizes are around 1000 bits,
so we will need 10,000 to 1,000,000 qubit quantum computers in order to
attack such keys.
Symmetric algorithms like AES aren't affected by Shor's algorithm,
but breaking them can be considered a search (trying all the keys and
see which leads to a good decryption), and Grover's algorithm reduces
general search times to the square root of the number of operations.
The effect on symmetric ciphers is to effectively halve the key length;
a 128 bit AES key has only 64 bits of strength against a quantum computer.
Anticipating the possible introduction of quantum computers, AES is
specified to operate with up to 256 bit keys. Against a quantum computer
such a key would have 128 bits of strength, which is very strong.
So we have a good solution for the symmetric ciphers; just use a
256 bit key. For the public key algorithms the situation is harder.
Shor's algorithm can be used against a variety of problems that involve
finding the period of group generators. This is what leads to a solution
for factoring, but it can also be used against discrete log systems,
and that apparently includes elliptic curves.
There are some public key systems which are based on other problems than
factoring or discrete logs. The most widely used today is probably the
NTRU system, which is based on finding shortest vectors in a lattice.
NTRU is patented, so it is not used in freeware, but the company that
owns the patent sells software that uses the cryptosystem. As far as I
know, this problem is not believed to be affected by quantum computers.
Conceivably it could be cast as a search so that Grover's algorithm would
apply, but at most that might require increasing the key sizes slightly
as with AES.
The NTRU patent will expire in the 2010s or thereabouts, so it would
probably be an acceptable fallback assuming quantum computers take at
least another decade or so to be developed, if they are workable at all.
Hal
This archive was generated by hypermail 2.1.5 : Sat Nov 02 2002 - 09:16:35 MST