Period finding, factoring, and cryptography

Simon's problem (Section 2.5) starts with a subroutine that calculates a function f(x), which satisfies f(x) = f(y) for distinct x and y if and only if y = x ⊕ a, where ⊕ denotes the bitwise modulo-2 sum of the n-bit integers a and x. The number of times a classical computer must invoke the subroutine to determine a grows exponentially with n, but with a quantum computer it grows only linearly.

This is a rather artificial example, of interest primarily because it gives a simple demonstration of the remarkable computational power a quantum computer can possess. It amounts to finding the unknown period a of a function on n-bit integers that is “periodic” under bitwise modulo-2 addition. A more difficult, but much more natural problem is to find the period r of a function f on the integers that is periodic under ordinary addition, satisfying f(x) = f(y) for distinct x and y if and only if x and y differ by an integral multiple of r. Finding the period of such a periodic function turns out to be the key to factoring products of large prime numbers, a mathematically natural problem with quite practical applications.

We illustrate here the mathematics of the final (post-quantum-computational) stage of Shor's period-finding procedure. The final measurement produces (with high probability) an integer y that is within ½ of an integral multiple of 2n/r, where n is the number of Qbits in the input register, satisfying 2n > N2 > r2. Deducing the period r of the function f from such an integer y makes use of the theorem that if x is an estimate for the fraction j/r that differs from it by less than ½r2, then j/r will appear as one of the partial sums in the continued-fraction expansion of x. In the case of Shor's period finding algorithm x = y/2n. If j and r happen to have no factors in common, r is given by the denominator of the partial sum with the largest denominator less than N. Otherwise the continued-fraction expansion of x gives r0: r divided by whatever factor it has in common with the random integer j. If several small multiples of r0 fail to be a period of f, one repeats the whole procedure, getting a different submultiple r1 of r. There is a good chance that r will be the least common multiple of r0 and r1, or a not terribly large multiple of it. If not, one repeats the whole procedure a few more times until one succeeds in finding a period of f.

Secret-key distillation (SKD) is the technique used to convert some given random variables, shared among the legitimate parties and a potential eavesdropper Eve, into a secret key. Secret-key distillation is generally described as a protocol between the legitimate parties, who exchange messages over the public classical authenticated channel as a function of their key elements X and Y, aiming to agree on a common secret key K.

We assume here that the eavesdropper's knowledge can be modeled as a classical random variable. For more general assumptions on the eavesdropping techniques, please refer to Chapter 12.

The quantum transmission is assumed to be from Alice to Bob. In order to be able to specify another direction for secret-key distillation, we use the Claude-and-Dominique naming convention. Here, the random variables X and Y model the variables obtained by Claude and Dominique, respectively, using the quantum channel, and the random variable Z contains anything that Eve was able to infer from eavesdropping on the quantum channel. As detailed in Section 11.3.2, both assignments (Alice = Claude ∧ Bob = Dominique) and (Alice = Dominique ∧ Bob = Claude) are useful.

In this chapter, I first propose a general description of the reconciliation and privacy amplification approach. I then list the different characteristics that a SKD protocol can have. And finally, I overview several important classes of known results and treat the specific case of SKD with continuous variables.

Wonderful news from Copenhagen

Heisenberg and Schrödinger invented mathematical formalisms that provided correct answers to all the various problems of (non-relativistic) quantum theory. It was Bohr who uncovered the underlying significance of the theory; in particular he showed how the profound conceptual difficulties encountered as the theory developed – the so-called wave–particle duality, the totally unclassical nature of the uncertainty principle – could be neutralised by a revision, or more accurately a generalisation, of our use of physical concepts.

Such was the generally accepted view of things from soon after 1927, when Bohr first put forward his ideas on complementarity at an international meeting of physicists at Como, through the 1930s, when it was felt that Bohr destroyed Einstein's contrary opinions, and certainly up to the time of Bohr's death in 1962. Bohr's analysis is usually spoken of as the Copenhagen interpretation of quantum theory, though it is instructive to realise that such a term was frowned upon by those closest to Bohr, since it appears to suggest that the interpretation is just one among (conceivably) many.

Let us examine, for example, the words of Léon Rosenfeld, Bohr's disciple and long-term collaborator, as expounded at a conference in 1957 [52]. Rosenfeld maintained that any idea of ‘interpreting a formalism’ was a ‘false problem’, that in a good theory, the ‘ordinary language (spiced with technical jargon for the sake of conciseness)’ in which it is described, is ‘inseparably united … with whatever mathematical apparatus is necessary’, that ‘we are here not faced with a matter of choice between two possible languages or two possible interpretations, but with a rational language intimately connected with the formalism and adapted to it, on the one hand, and with rather wild, metaphysical speculations … on the other’.

So far, the knowledge of Eve has been modeled by a classical random variable. The aim of this chapter is first to discuss how the previous results apply to QKD, where Eve's action may not necessarily be classically described by the random variable Z. Then, we explain the equivalence between BB84 and so-called entanglement purification protocols as a tool to encompass general eavesdropping strategies. Finally, we apply this equivalence to the case of the coherent-state protocol GG02.

Eavesdropping strategies and secret-key distillation

In Chapters 10 and 11, I analyzed the security of the protocols with regard to individual eavesdropping strategies only. In this particular case, the result of Alice's, Bob's and Eve's measurements can be described classically and the results of Section 6.4 apply. Let us review other kinds of eavesdropping strategies and discuss how the concepts of Chapter 6 can be applied.

Note that the individual eavesdropping strategy, the simplest class of strategies, is still technologically very challenging to achieve today in an optimal way. Nevertheless, we do not want the security of quantum cryptography to rely only on technological barriers. By considering more general eavesdropping strategies, we make sure quantum cryptography lies on strong grounds.

Following Gisin et al. [64], we divide the possible eavesdropping strategies into three categories: individual attacks, collective attacks and joint attacks.

In the history of cryptography, quantum cryptography is a new and important chapter. It is a recent technique that can be used to ensure the confidentiality of information transmitted between two parties, usually called Alice and Bob, by exploiting the counterintuitive behavior of elementary particles such as photons.

The physics of elementary particles is governed by the laws of quantum mechanics, which were discovered in the early twentieth century by talented physicists. Quantum mechanics fundamentally change the way we must see our world. At atomic scales, elementary particles do not have a precise location or speed, as we would intuitively expect. An observer who would want to get information on the particle's location would destroy information on its speed – and vice versa – as captured by the famous Heisenberg uncertainty principle. This is not a limitation due to the observer's technology but rather a fundamental limitation that no one can ever overcome.

The uncertainty principle has long been considered as an inconvenient limitation, until recently, when positive applications were found.

In the meantime, the mid-twentieth century was marked by the creation of a new discipline called information theory. Information theory is aimed at defining the concept of information and mathematically describing tasks such as communication, coding and encryption. Pioneered by famous scientists like Turing and von Neumann and formally laid down by Shannon, it answers two fundamental questions: what is the fundamental limit of data compression, and what is the highest possible transmission rate over a communication channel?

Albert Einstein and relativity

If I were to ask a number of people in the street what they think was the most important new theory in physics in the twentieth century, and who has been the greatest physicist, I am fairly sure that – of those able to express an opinion at all – a substantial majority would say that relativity has been the greatest theory, and Einstein the greatest physicist.

Indeed Albert Einstein has probably achieved the remarkable feat of not just becoming the best-known practitioner of any branch of science among the general public, but retaining that position for 85 years, 50 of those years since his death in 1955.

It was in 1905, when he was 26, that Einstein astonished the scientific community by producing four pieces of work of the very highest quality. These included his first paper on relativity, in which he introduced what is now called the special theory of relativity (a term I shall explain in Chapter 3). The three other papers will be referred to in due course. What was astonishing was not just the quality of the work, but that the author was not an academic of note, or even of promise, but was working as a patent inspector after rather a mediocre student career. (A recent pleasantly written biography of Einstein is that of Abraham Pais [1], himself a well-known physicist; Pais gives references to many other accounts of Einstein's life. Another, more recent, biography is that by Fölsing [2].

In this chapter, I will discuss some important aspects of universal families of hash functions. I will not remain completely general, however, as we are only interested in universal families of hash functions for the purpose of privacy amplification of QKD-produced bits. In the first section, I explain my motivations, detailing the requirements for families of hash functions in the scope of privacy amplification. I then give some definitions of families and show how they fit our needs. Finally, I discuss their implementation.

Defined in Section 6.3.1, the essential property of an ∈/|B|-almost universal family of hash function is recalled in Fig. 7.1.

Requirements

For the purpose of privacy amplification, families of hash functions should meet some important requirements. They are listed below:

• The family should be universal (∈ = 1) or very close to it (∈ ≈ 1).

• The number of bits necessary to represent a particular hash function within its family should be reasonably low.

• The family should have large input and large output sizes.

• The evaluation of a hash function within the family should be efficient.

The first requirement directly affects the quality of the produced secret key. The closer to universality, the better the secrecy of the resulting key – see Section 6.3.1.

The second requirement results from the fact that the hash function will be chosen randomly within its family and such a choice has to be transmitted between Claude and Dominique. It is not critical, however, because the choice of the hash function need not be secret. A number of bits proportional to the input size is acceptable.

This book aims at giving an introduction to the principles and techniques of quantum cryptography, including secret-key distillation, as well as some more advanced topics. As quantum cryptography is now becoming a practical reality with products available commercially, it is important to focus not only on the theory of quantum cryptography but also on practical issues. For instance, what kind of security does quantum cryptography offer? How can the raw key produced by quantum cryptography be efficiently processed to obtain a usable secret key? What can safely be done with this key? Many challenges remain before these questions can be answered in their full generality. Yet quantum cryptography is mature enough to make these questions relevant and worth discussing.

The content of this book is based on my Ph.D. thesis [174], which initially focused on continuous-variable quantum cryptography protocols. When I decided to write this book, it was essential to include discrete-variable protocols so as to make its coverage more balanced. In all cases, the continuous and discrete-variable protocols share many aspects in common, which makes it interesting to discuss about them both in the same manuscript.

Quantum cryptography is a multi-disciplinary subject and, in this respect, it may interest readers with different backgrounds. Cryptography, quantum physics and information theory are all necessary ingredients to make quantum cryptography work. The introductory material in each of these fields should make the book self-contained. If necessary, references are given for further readings.

Structure of this book

The structure of this book is depicted in Fig. 0.1. Chapter 1 offers an overview of quantum cryptography and secret-key distillation.