Cryptography Reference
In-Depth Information
structure). The relaxation times are still within the range of seconds. Don't
laugh: the first computers worked mechanically with punch cards and weren't
much faster.
That was the state of affairs in summer 2000. Meanwhile, one arrived at 7 qubits
and managed to factor the number 15 (
http://www.research.ibm.com/
resources/news/20011219_quantum.shtml
). Many
great developments
began with a 'proof of concept'.
More results won't be long in coming considering the intensive research in this
field. However, the way toward factoring 1024-bit numbers is extremely cum-
bersome. Solving the problem might indeed be more difficult than it appears.
It wouldn't be the first time. For instance, people thought of nuclear fusion
reactors as a future technology forty years ago, whereas things around this
issue are very quiet today. Some researchers bet that the sun would extinguish
before a quantum computer could factor 1024-bit numbers.
Cryptologists should be more careful because they have to invent algorithms
that resist novel types of attack ahead of their time. Grover recalls a contribution
to a discussion in 1949, which read that 'while a computer like the ENIAC is
equipped with 18 000 tubes and weighs 30 tons, computers of the future might
perhaps have only 1000 tubes and weigh only one ton'. Now just imagine how
experts might laugh at our current ideas in 50 years from now
...
Schneier said in an interview that 'quadratic acceleration' as in Grover's algo-
rithm would be rather typical for quantum computers. This would mean that
AES with 256-bit keys might still have the security of a 128-bit algorithm, i.e.,
it would still be invulnerable (see below). Quantum computers are exponentially
faster for special problems only. Unfortunately, this includes the two problems
all current asymmetric encryptions suffer from. And other secure methods are
still not in sight.
So there is need for action. Some studies suggest that quantum computers could,
for example, replace conventional semiconductor technology by the year 2020
once this technology has reached dimensions where quantum effects dominate.
Though we have to be patient, only two mathematical problems identified in the
past twenty years are suitable for public-key cryptography, namely factoring
and computing the discrete logarithm.
And I wouldn't be so sure about symmetric methods. Quantum computers do
not offer faster speeds when running successive operations. But who checks
whether or not symmetric algorithms could be attacked somehow 'differently'?
Hardly a cryptanalyst is in the habit of attacking such methods by means of
