QUANTUM CRYPTOANALYSIS - INTRODUCTION

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

1. PUBLIC-KEY CRYPTOGRAPHY

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 (N10^L) and try to factor it by dividing it by 2, 3,..., and checking the reminder. In the worst case you may need approximately =10^L/2 divisions to solve the problem - an exponential increase as a function of L. Now imagine a computer capable of performing 10¹⁰ divisions per second. The computer can then factor any number N, using the trial division method, in about /10¹⁰ seconds. Take a 100-digit number N, so that N10¹⁰⁰. The computer will factor this number in about 10⁴⁰ seconds, much longer than 3.8*10¹⁷ seconds (12 billion years) - the currently estimated age of the Universe!

2. QUANTUM FACTORING

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.

Quantum factoring of an integer N is based on calculating the period of the function F_N(x) = a^x 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 a^r/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 11^x mod 15 forms a repeating sequence 1, 11, 1, 11, 1, 11,... The period r=2 and a^r/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:

Then we perform an arithmetical operation that takes advantage of quantum parallelism by computing the function F_N(x) for each number x in the superposition. The values of F_N(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 F_N(k) for some k. The state of the first register right after the measurement, due to the periodicity of F_N(x), is a coherent superposition of all states  such that x = k, k+r, k+2r,..., i.e. all x for which F_N(x) = F_N(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''.

3. FURTHER READING

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

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

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