Quantum Cryptoanalysis - Introduction

by Artur Ekert



  1. PUBLIC-KEY CRYPTOGRAPHY
  2. QUANTUM FACTORING
  3. FURTHER READING



1. PUBLIC-KEY CRYPTOGRAPHY

Mathematicians have tried hard to solve the key distribution problem (see introduction to quantum cryptography). The 1970s brought a clevermathematical 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,...,√N and checking the reminder. In the worst case you may need approximately √N=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 √N/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*1017seconds (12 billion years) - the currently estimated age of the Universe!


2. QUANTUM FACTORING

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 |x> 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. |k> becomes |0> 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''.


3. FURTHER READING

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).