 |
|
|
|
|
CQC
Introductions: Quantum Cryptoanalysis
QUANTUM CRYPTOANALYSIS - INTRODUCTIONby Artur Ekert
- PUBLIC-KEY
CRYPTOGRAPHY
- QUANTUM
FACTORING
- FURTHER
READING
Mathematicians have tried hard to solve the key distribution problem
(see introduction to quantum cryptography). The 1970s brought a clever
mathematical discovery in the shape of ``public key'' systems. In these
systems users do not need to agree on a secret key before they send the
message. They work on the principle of a safe with two keys, one public
key to lock it, and another private one to open it. Everyone has a key to
lock the safe but only one person has a key that will open it again, so
anyone can put a message in the safe but only one person can take it out.
In practice the two keys are two large integer numbers. One can easily
derive a public key from a private key but not vice versa. The system
exploits the fact that certain mathematical operations are easier to
perform in one direction than the other. Public-key cryptosystems avoid
the key distribution problem but unfortunately their security depends on
unproven mathematical assumptions, such as the difficulty of factoring
large integers (RSA - the most popular public key cryptosystem gets its
security from the difficulty of factoring large numbers). An enemy who
knows your public key can in principle calculate your private key because
the two keys are mathematicaly related, however, the difficulty of
computing the private key from the respective public key is exactly that
of factoring big integers.
Difficulty of factoring grows rapidly with the size, i.e. number of
digits, of a number we want to factor. To see this take a number
N with L decimal digits (N  10L) and try to factor it by
dividing it by 2, 3,..., and
checking the reminder. In the worst case you may need approximately =10L/2 divisions to solve the
problem - an exponential increase as a function of L. Now
imagine a computer capable of performing 1010 divisions
per second. The computer can then factor any number N, using
the trial division method, in about /1010 seconds. Take a
100-digit number N, so that N 10100. The computer will factor this
number in about 1040 seconds, much longer than
3.8*1017 seconds (12 billion years) - the currently
estimated age of the Universe!
It seems that factoring big numbers will remain beyond the capabilities
of any realistic computing devices and unless mathematicians or computer
scientists come up with an efficient factoring algorithm the public-key
cryptosystems will remain secure. Or will they? As it turns out we know
that this is not the case; the classical, purely mathematical, theory of
computation is not complete simply because it does not describe all
physically possible computations. In particular it does not describe
computations which can be peformed by quantum devices. Indeed, recent work
in quantum computation shows that a quantum computer can factor much
faster than any classical computer.
Quantum computers can compute faster because they can accept as the
input not a one number but a coherent superposition of many different
numbers and subsequently perform a computation (a sequence of unitary
operations) on all of these numbers simultaneously. This can be viewed as
a massive parallel computation, but instead of having many processors
working in parallel we have only one quantum processor performing a
computation that affects all components of the state vector. To see how it
works let us describe Shor's factoring using a quantum computer composed
of two quantum registers.
MATHEMATICS OF FACTORING - BOX
Quantum factoring of an integer N is based on
calculating the period of the function FN(x) =
ax mod N. The mathematical specification of
the function means: choose a random number a between
0 and N, then raise it to the power
x, divide by N and keep the reminder which
is the value of the function. It turns out that for increasing powers of
a, the remainders form a repeating sequence with a period
which we denote r. Once r is known the
factors of N are obtained by calculating the greatest
common divisor of N and ar/2
+/- 1. Fortunately an easy and very efficient algorithm
to compute the greatest common divisor has been known since 300 BC. The
algorithm is described in Euclid's Elements, the oldest Greek
treatise in mathematics to reach us in its entirety (try your elementary
school textbooks as the reference).
Suppose we want to factor 15 using this method. Let
a=11. For increasing x the function
11x mod 15 forms a repeating sequence 1, 11,
1, 11, 1, 11,... The period r=2 and
ar/2. Then we take the greatest common
divisor of 10 and 15, and of 12 and 15 which
gives us respectively 5 and 3, the two factors of
15. Classicaly calculating r is as difficult as
trying to factor N by the trial division methods i.e. the
execution time of calculations grows exponentially with number of digits
in N. Quantum computers can find r in time
which grows only as a quadratic function of the number of digits in
N.
Consider two quantum registers, each register being composed of a
certain number of two-state quantum systems which we call ``qubits''
(quantum bits). We take the first register and place it in a quantum
superposition of all the possible integer numbers it can contain. This can
be done by starting with all qubits in the 0 states and applying a
simple unitary transformation to each qubit which creates a superposition
of 0 and 1 states:
Imagine a two-qubit register, for example. After
this procedure the register will be in a superposition of all four numbers
it can contain,
where 00 is binary for 0,
01 binary for 1, 10 binary for 2 and finally
11 which is binary for 3.
Then we perform an arithmetical operation that takes advantage of
quantum parallelism by computing the function
FN(x) for each number x in the
superposition. The values of FN(x) are placed in
the second register so that after the computation the two registers become
entangled:
(we have ignored the normalisation constant).
Now we perform a measurement the on the second register. The measurement
yields randomly selected value FN(k) for some k. The state
of the first register right after the measurement, due to the periodicity
of FN(x), is a coherent superposition of all
states  such that x = k, k+r, k+2r,..., i.e. all
x for which FN(x) =
FN(k). The value k is randomly selected
by the measurement therefore the state of the first register is
subsequently transformed via a unitary operation which sets any
k to 0 (i.e. 
becomes  plus
a phase factor) and modifies the period from r to a multiple
of 1/r. This operation is known as the quantum Fourier
transform. The first register is then ready for the final measurement
which yields an integer which is the best whole approximation of a
multiple of 1/r. From this result r and
subsequently factors of N can be easily calculated (see the
Box). The execution time of the quantum factoring algorithm can be
estimated to grow as a quadratic function of L and numbers
100 decimal digits long can be factored in fraction of second!
An open question has been whether it would ever be practical to build
physical devices to perform such computations, or whether they would
forever remain theoretical curiosities. Quantum computers require a
coherent, controlled evolution for a period of time which is necessary to
complete the computation. Many view this requirement as an insurmountable
experimental problem, however, we believe that the technological progress
will sooner or later make such devices feasible. When the first quantum
factoring devices are built the security of public-key crypstosystems will
vanish. The mathematical solution to the key distribution problem is
shattered by the power of quantum computation. Does it leave us without
any means to protect our privacy? Fortunately quantum mechanics after
destroying classical ciphers comes to rescue our privacy and offers its
own solution to the key distribution problem. It is known as ``quantum
cryptography''.
There are several good textbooks on cryptology e.g.
- D. Welsh, Codes and Cryptography (Clarendon Press, Oxford,
1988).
- B. Schneier, Applied cryptography: protocols, algorithms, and
source code in C., (John Wiley & Sons, New York 1994).
- G. Brassard, Modern Cryptology: A Tutorial, (Springer, Berlin
1988).
- D.E. Denning, Cryptography and Data Security,
(Addison-Wesley,1982).
Papers on quantum computation available
via our postal service:
- D. Deutsch, 1985, Proc. R. Soc. London, Ser. A: 400, 97.
- D. Deutsch, 1989, Proc. R. Soc. London, Ser. A: 425, 73.
- D. Deutsch and R. Jozsa, 1992, Proc. R. Soc. London, Ser A:
439, 553.
- R. Jozsa, 1991, Proc. R. Soc. London, Ser. A: 435, 563.
The main reference for this brief account of quantum cryptoanalysis is:
- P.W. Shor, ``Algorithms for quantum computation: Discrete logarithms
and factoring'', in Proceedings of the 35th Annual Symposium on the
Foundations of Computer Science, edited by S. Goldwasser (IEEE
Computer Society Press, Los Alamitos, CA), pages 124-134 (1994).
- P.W. Shor, ``Polynomial-time algorithms for prime factorization and
discrete logarithms on a quantum computer'', SIAM J. Computing
26, pages 1484-1509 (1997).
A comprehensive exposition of Shor's algorithm for factoring on a
quantum computer, together with some relevant background in number theory,
computational complexity theory and quantum computation including remarks
about possible experimental realisations has been prepared for the Review
of Modern Physics by Artur Ekert and Richard Jozsa and can be obtained
both via our electronic (postscript file) and postal service.
Text by Artur Ekert
update March 20, 1995 by K-A S
most
recent update by Wim van Dam (June 1999) |
|
|
|
|
|
