Université de Montréal

Towards a formal definition of security for quantum protocols

par

Jeroen van de Graaf

Département d’Informatique et de Recherche Opérationnelle Faculté des Arts et des Sciences

Thèse présentée à la Faculté des études supérieures

en vue de l’obtention du grade de

Philosophiæ Doctor (Ph.D.) en Informatique

Décembre 1997

\begin{matrix}c \\ ◯ \end{matrix}Jeroen van de Graaf, 1997

Université de Montréal Faculté des études supérieures

Cette thèse intitulée

Towards a formal definition of security for quantum protocols

présenté par:

Jeroen van de Graaf

a été évalué par un jury composé des personnes suivantes:

\underline{Michel Boyer} (président rapporteur)

Claude Crépeau (directeur de recherche)

Gilles Brassard (co-directeur) \underline{Geňa Hahn}

(membre du jury)

\underline{Joe Kilian} (examinateur externe)

David London (représentant du doyen)

Thèse acceptée le: \underline{29 mai 1998.}

Summary

This thesis presents a formal model for quantum protocols, that is, cryptographic protocols based on quantum mechanics. It also develops a definition of security (which includes notions such as privacy and correctness) for quantum protocols.

First, existing classical (non-quantum) definitions of security are studied. There are essentially two approaches: one based on Turing Machines and simulation, the other using information theory. Both approaches are explored in detail and compared, then a particular variation of the first approach is chosen. Security is defined by introducing an interface (also called a simulator) which is capable of translating an attack on protocol 1 into an attack on protocol 2. The profile of a protocol is a stochastic variable, defined as the output of the participants and the view of the adversary who performs the attack. If an interface exists such that the profile of protocol 1 is indistinguishable from the profile of protocol 2 with the help of this interface, then protocol 1 is at least as secure as protocol 2. An absolute notion of security is obtained by comparing the protocol implementation with its ‘ideal’ equivalent.

In this approach, and in classical cryptography in general, indistinguishability of probability distributions is a crucial tool. The meaning of this notion is explored in the context of density matrices, the mathematical formalism which is used to describe the state of a quantum system. Various measures of distinguishability of quantum states relevant from a cryptographic point of view are investigated: probability of error, trace norm (related to the Kolmogorov distance), overlap (related to the Bhattacharyya coefficient) and Shannon distinguishability (defined through the mutual information). It is shown that if we require that the distinguishability between two families of quantum states vanish exponentially fast, these four distinguishability measures are equivalent.

Along the way upper and lower bounds for the Shannon distinguishability are obtained. This is a very useful result, because explicit computation of the Shannon distinguishability between two quantum states is often difficult (it requires solving a transcendental equation), whereas the other distinguishability measures, in particular the trace norm, are usually much easier to compute.

In the last chapter the two previous topics are combined. A formal model for quantum protocols is formulated. It uses Quantum Turing Machines to represent the participants, who communicate through a quantum channel. The different nature of quantum information as opposed to classical information is explored in detail, including the implications this has for the definition. As in the classical case, we introduce an interface to compare the security of two protocols for the same task. Subsequently some consequences of the proposed definition are investigated. In particular, strong evidence is given that one classical technique often used in proofs of security for classical protocols, called rewinding, is impossible in the quantum setting.

Key words: cryptographic protocols, zero knowledge protocols, quantum information theory, quantum cryptography.

Résumé

La question générale posée dans cette thèse est la suivante: qu’est-ce qu’un bon modèle formel pour des protocoles cryptographiques basés sur la mécanique quantique, et qu’est-ce qu’une définition raisonnable de la sécurité pour de tels protocoles quantiques?

On s’intéresse d’abord à cette question pour des protocoles classiques, en particulier pour des protocoles de calcul privé multi-partie. Pour un tel protocole, n participants veulent calculer ensemble une fonction f(x_{1}, x_{2}, ..., x_{n}), où x_{i} est une entrée pour chacun d’eux. Personne ne veut révéler d’information à propos de son entrée, sauf ce qui peut être logiquement déduit de la sortie. Par exemple, un vote de majorité effectué sur Internet lorsqu’aucun participant ne jouit de la confiance de tous les autres. Trouver une définition pour des protocoles de calcul privé multi-partie est étonnamment difficile, même pour des protocoles à deux parties relativement simples, comme le transfert inconscient, ou l’évaluation d’une porte ET. Nous n’envisagerons que les protocoles à deux participants.

Les modèles existants peuvent être divisés en deux groupes. La première approche est basée sur les machines de Turing, qui sont étendues à partir d’un ruban dédié à l’envoi et à la réception des messages. Ce ruban partagé sert à modéliser la communication entre les participants d’un protocole. La sécurité est définie par l’introduction d’une interface (aussi appelé simulateur) qui est capable de traduire une attaque sur le protocole réel en une attaque sur une version idéalisée du même protocole. On définit une variable stochastique, le profil d’un protocole, comme les sorties des participants et la vue de l’adversaire qui effectue l’attaque. Si une interface existe telle que le profil du protocole réel est indistingable, comparé à celui du protocole idéalisé au travers de cette interface, alors le protocole est dit sécuritaire.

Une deuxième approche utilise aussi les machines de Turing, mais sa définition de la sécurité est basée sur la théorie de l’information. La définition proposée traite séparément la confidentialité (aucune information erronée à propos de l’entrée d’une autre partie est obtenue) et la correction (la sortie de la fonction ne peut être influencée par une partie malhonnête). Bien que valable dans quelques cas spéciaux, il existe des exemples dans lesquels cette séparation est fatale, dans le sens où des protocoles non-sécuritaires satisfont ces deux aspects. Nous modifions cette approche pour résoudre ce problème et montrons qu’elle contient la première approche comme cas particulier. Néanmoins, nous développons des critères pour comparer les deux approches et choisissons la première dans la suite de la thèse.

Dans la conception des protocoles cryptographiques on définit souvent une famille de protocoles, indexée par un paramètre de sécurité. Ce dernier peut indiquer par exemple la taille d’une chaîne, le nombre d’étapes dans un protocole, ou le nombre de photons. Une notion centrale en cryptographie classique est l’indistingabilité exponentielle de deux distributions de probabilité. Cette notion exprime que la distance entre deux distributions converge vers zéro de manière exponentiellement rapide quand le paramètre de sécurité augmente; cette distance est habituellement prise au sens de Kolmogorov.

Donc, si on veut modéliser et analyser la sécurité des protocoles quantiques on a besoin d’une notion de distance entre deux états quantiques. L’état d’un système quantique est décrit par une matrice de densité, mais plusieurs notions de distance sont possibles. Nous étudions quatre mesures de distingabilité d’états quantiques pertinentes pour la cryptographie: probabilité d’erreur, norme de la trace (reliée à la distance de Kolmogorov), “overlap” (relié au coefficient de Bhattacharyya), et distingabilité de Shannon (définie à travers l’information mutuelle).

Ces mesures ont leur origine dans les mesures classiques d’indistingabilité des distributions de probabilité, à partir desquelles un ensemble d’inégalités peut être obtenu. Nous démontrons que ces inégalités sont aussi valables dans le modèle quantique, et obtenons des bornes supérieures et inférieures pour la distingabilité de Shannon. Ceci est important, car un calcul explicite de la distingabilité de Shannon est souvent difficile (il faut résoudre une équation transcendantale), alors que les autres mesures de distingabilité sont plus faciles à évaluer. En particulier, nous dérivons une expression simple d’une borne supérieure de la distingabilité de Shannon en fonction de la norme de la trace.

Comme dans le cas quantique, l’indistingabilité exponentielle de deux familles d’états quantiques peut être définie : on demande que la distingabilité entre deux familles s’annule exponentiellement vite. Il résulte que l’indistingabilité exponentielle est indépendante de la mesure spécifique choisie dans la définition: les quatre différentes définitions apparaissent donc équivalentes.

Dans le dernier chapitre nous présentons notre modèle pour des protocoles quantiques à deux parties, et donnons une définition de la sécurité. Nous nous restreignons aux protocoles avec des entrées et sorties classiques uniquement. Nous expliquons en détail comment un ordinateur quantique peut émuler les observations d’un état quantique, le fait que l’information quantique ne peut être copiée, et décrivons le principe qui nous empêche d’extraire une quelconque information d’un système quantique sans perturber l’état de celui-ci. Mais malgré le fait que l’information classique peut être considérée comme un cas particulier de l’information quantique, nous montrons que pour une bonne définition de la sécurité, les deux types d’information doivent être considérées séparément.

Après une discussion informelle, nous présentons notre modèle de façon formelle. Nous utilisons les machines de Turing quantiques pour les parties A et B, qui communiquent à travers un canal quantique modélisé par un ruban de communication quantique. Comme dans l’approche classique, nous utilisons une interface pour définir la sécurité d’un protocole relativement à un autre: on exige que le profil du premier protocole soit exponentiellement indistingable comparé au profil obtenu par un adversaire qui attaque le deuxième protocole à travers cette interface. Une notion absolue de sécurité est obtenue en comparant un protocole réel à son équivalent idéalisé. Finalement nous présentons des arguments convaincants sur l’impossibilité de la technique classique de retour en arrière (“rewinding”) d’une machine de Turing dans notre modèle quantique.

Contents

1 Introduction 1 1.1 Classical cryptography . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Quantum cryptography . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Classical and quantum indistinguishability . . . . . . . . . . . . . . 8 1.4 Security for quantum protocols . . . . . . . . . . . . . . . . . . . . 10 1.5 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Classical definitions of protocol security 12

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.1 Brief historical overview . . . . . . . . . . . . . . . . . . . 13 2.1.2 Problems with defining security . . . . . . . . . . . . . . . 16

2.2 The definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.1 Cryptographic tasks . . . . . . . . . . . . . . . . . . . . . 20 2.2.2 Cryptographic protocols . . . . . . . . . . . . . . . . . . . 22 2.2.3 Comparing the security of protocols . . . . . . . . . . . . . 25 2.2.4 Sequential composition of protocols . . . . . . . . . . . . . 28 2.2.5 Ideal protocols . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.6 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2.7 Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.3 Comparison with other definitions . . . . . . . . . . . . . . . . . . 34 2.3.1 Oracles, simulators, etc. . . . . . . . . . . . . . . . . . . . 34 2.3.2 The relation between S and E . . . . . . . . . . . . . . . . . 35

2.4 Simulatability and security . . . . . . . . . . . . . . . . . . . . . . 40 2.4.1 Physical assumptions . . . . . . . . . . . . . . . . . . . . . 40 2.4.2 Protocol security . . . . . . . . . . . . . . . . . . . . . . . 41

2.5 Another approach: using information theory . . . . . . . . . . . . . 43 2.5.1 The definition . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.5.2 Modifying the definition; awareness . . . . . . . . . . . . . 46

2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3 Distinguishability of quantum states 49 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.2 Probability distributions . . . . . . . . . . . . . . . . . . . . . . . . 52 3.3 Density matrices and measurements . . . . . . . . . . . . . . . . . 53 3.4 Measures of distinguishability . . . . . . . . . . . . . . . . . . . . 59

3.4.1 Probability of error . . . . . . . . . . . . . . . . . . . . . . 59 3.4.2 Kolmogorov distance . . . . . . . . . . . . . . . . . . . . . 61 3.4.3 Bhattacharyya coefficient . . . . . . . . . . . . . . . . . . . 63

3.4.4 Shannon distinguishability . . . . . . . . . . . . . . . . . . 65 3.5 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.6 Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.7 Exponential indistinguishability . . . . . . . . . . . . . . . . . . . 72 3.8 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

4 A model for quantum protocols 81 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.2 Qubits and unitary transformations . . . . . . . . . . . . . . . . . . 83 4.3 Emulating classical computation and measurements by a quantum

computer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.3.1 Deterministic and random bits . . . . . . . . . . . . . . . . 86 4.3.2 Measurements . . . . . . . . . . . . . . . . . . . . . . . . 87 4.3.3 Partial knowledge about entangled systems . . . . . . . . . 90

4.4 Quantum protocols informally . . . . . . . . . . . . . . . . . . . . 92 4.4.1 The quantum channel . . . . . . . . . . . . . . . . . . . . . 92 4.4.2 Dealing with classical information . . . . . . . . . . . . . . 93 4.4.3 Information and disturbance . . . . . . . . . . . . . . . . . 94 4.4.4 Redefining the view . . . . . . . . . . . . . . . . . . . . . 98 4.4.5 Comparison with other work . . . . . . . . . . . . . . . . . 101 4.4.6 Protocol tasks . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.5 Formal definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

4.5.1 The Quantum Turing Machine . . . . . . . . . . . . . . . . 103 4.5.2 Protocol, output, view, profile, the adversary . . . . . . . . 105 4.5.3 Comparing the security of protocols; interface . . . . . . . . 108 4.5.4 Ideal protocols and absolute security . . . . . . . . . . . . . 109

4.6 Rewinding the adversary . . . . . . . . . . . . . . . . . . . . . . . 110 4.7 Extensions and open problems . . . . . . . . . . . . . . . . . . . . 114

5 Conclusion 117

Acknowledgments 119

List of Tables

2.1 A comparison of various definitions of security. . . . . . . . . . . . 40 3.1 Classical and quantum notions of indistinguishability. . . . . . . . . 68

List of Figures

2.1 Task for Bit Commitment. . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Task for Two-Party Computation. . . . . . . . . . . . . . . . . . . . 21 2.3 Task for Proof of Knowledge. . . . . . . . . . . . . . . . . . . . . . 21 2.4 E attacks protocol [A, B]. . . . . . . . . . . . . . . . . . . . . . . . . 24 2.5 Modified ideal protocol for Bit Commitment. . . . . . . . . . . . . 31 2.6 E attacks the ideal protocol [A, B] through S. . . . . . . . . . . . . . 32

3.1 2 min\{x, 1 − x\} ≤ H_{2}(x) ≤ 2(x(1 − x))^{\frac{1}{2}} . . . . . . . . . . . . . . 71 3.2 Equation 3.26 for the parity bit. . . . . . . . . . . . . . . . . . . . . 80 3.3 Equation 3.27 for the parity bit. . . . . . . . . . . . . . . . . . . . . 80

4.1 A measurement interpreted as an interaction with another system. . 88 4.2 Quantum Key Distribution. . . . . . . . . . . . . . . . . . . . . . . 97

List of Acronyms

bc  Bit Commitment  see page 20.

bcjl Reference [BCJL93 ] bms Reference [BMS96 ] epr Reference [EPR35 ]

got  Generalized Oblivious Transfer  see page 43.
mpc  Multi-Party Computation  see page 2.
ot  Oblivious Transfer  usually (_{1}^{2})-ot is meant.
(_{1}^{2})-ot  One-out-of-Two Oblivious Transfer  see page 20.
pok  Proof of Knowledge  see page 21.
povm  Positive Operator-Valued Measure  see page 57.
pvm  Projection Valued Measurement  see page 57.
QTM  Quantum Turing Machine  see page 103.
TM  Turing Machine  see page 103.
tpc  Two-Party Computation  see page 20.

Chapter 1

Introduction

Mathematics belongs to man, not to God. [...]

If God has mathematics of his own that needs to be done,

let him do it himself. Errett Bishop

1.1 Classical cryptography

Suppose the board of directors of IACR (the International Association of Cryptographic Research) suddenly wants to hold a confidential vote on some sensitive issue (something related to its former editor-in-chief, say). Since its members work and live all around the world, one solution could be to use a trusted party, to whom everybody sends his vote, who counts the tallies and broadcasts them.

However, in cryptography there is no such thing as mutual trust: if all the parties involved in a protocol trust each other there would be no need for cryptography, and we could all go to the beach. Another presupposition is that the parties in a protocol are spatially separated, but can communicate through some channel. The challenge of cryptography is to design protocols which reduce trust to the minimum. In this ballot example, the question is whether the same functionality can be obtained without a trusted party. That is, whether the members of the board are able to hold their ballot while they are all connected through the internet, say, running some very clever Java-application, without relying on a trusted party.

This question was addressed, and answered affirmatively (at least theoretically) in the years 1985, ’86, ’87; it was then among the most exciting topics in cryptographic research. Not only secret voting was studied, but also other cryptographic tasks: how to play poker (or any other card game), how to resolve the millionaires’ problem (two millionaires want to find out who is richest without revealing their wealth), or the match-making problem (boy and girl want to find whether they would be interested in dating each other, but if one party is not interested, he or she cannot find out what the other wanted).

All these tasks can be regarded as instances of a more general cryptographic task known as Multi-Party Computation (mpc): n participants want to compute together a function y = f(x_{1}, x_{2}, ..., x_{n}) with the x_{i} being their inputs. Nobody wants to reveal information about his input except what can be logically deduced from the output, y. Observe that the match-making problem is just a disguised form of an evaluation of an and gate.

If the participants of a cryptographic protocol for mpc do not want to put their trust in one person (or organization), they must agree on (and put their trust in) some other assumption. For most cryptographic protocols, this falls in one of three categories:

Participants are computational restricted: it is assumed that all the participants have only restricted computational resources and that computationally hard problems exist. For instance, they can assume that factoring large integers is hard.

The majority of participants is honest: If we assume that a reliable broadcast channel exists, that each pair of participants has a private communication channel and that more than \frac{2}{3}n (later improved to \frac{1}{2}n) participants are honest, then there exist protocols for multi-party computations [CCD88 , BGW88 , RB89, Be89 , Be91b ].

Participants are connected by error-prone channels: Usually it is assumed that when two participants communicate, the transmission of bits is errorless: a bit sent by one party equals the bit received by the other. (In practice error-correcting codes are applied to guarantee this property.) However, we can abandon this assumption and use this error-property (the fact that a communication channel may lose or invert its bits) in favor of cryptography. For instance, in the erasure channel (also called Rabin Oblivious Transfer [Ra81 ]) a positive fraction of the bits transmitted by the sender disappear; the receiver sees a “?” instead of 0 or 1 some of the time. Another example is the Noisy Channel, in which a bit gets inverted during transmission with a certain probability. Both Oblivious Transfer and Noisy Channel are strong enough primitives to construct a protocol for mpc. Until October 1995 the Quantum Channel was believed to fall in this same category, but this turned out to be false. More on this subject later.

Since 1985 several protocols for mpc have appeared in the literature, for an overview with references, see [Gr95 ] or [Fr93 ]. But even though many protocols have been presented in these papers, hardly any of these papers contains a rigorous proof of their security. Often these papers present a protocol, and with some handwaving and a sketchy proof the protocols are claimed to be secure.

But this situation is unsatisfactory. History has shown us too many examples where encryption schemes were claimed to be secure, until a cleverer person came along and broke it. It was only during the Second World War that many mathematicians got involved in breaking the enemy’s cryptosystem, and started to wonder about a mathematical basis for designing cryptosystems. By now, any encryption scheme or protocol should (ideally) be accompanied by a mathematical proof of its security. Similarly, we would like to accompany each proposed protocol for mpc with a proof of its security.

However, before one can prove something, a definition is needed, and this is where the problem lies. Above, in the context of Multi-Party Computation, we used the phrasing that “no party can learn anything about the other inputs, except from what can be logically deduced from its own input and output”. Although intuitively very clear as such, this phrasing is not sufficiently precise. Finding a suitable and pleasant definition for the security of mpc is surprisingly difficult, even for relatively simple primitives as the match-making protocol (i.e. the and ) or Oblivious Transfer.

This is where this thesis begins. In Chapter 2 we will see why defining security of mpc is difficult. Then we discuss and compare in more detail the approaches taken by Beaver, Micali-Rogaway, Canetti et al, and Brassard-Crépeau. The first three have many features in common, and some of the differences will be of no concern for this thesis. At the end of the first chapter we adopt one approach, after having discussed the criteria for making this choice.

1.2 Quantum cryptography

The world is quantum!

Even though it is not apparent from our daily perceptions, the laws that describe the phenomena (including particles and radiation) of which our universe is constructed, are the laws of quantum mechanics.

Computation and communication are inherently physical processes. The Church-Turing thesis is a physical assumption about what we can compute. Turing’s formalization of a computer was based on what a clerk following simple instruction could compute. (Even though Turing knew enough about quantum mechanics, it apparently did not occur to him that it could be used for computation.) And Cover and Thomas say the following about communication [CT91]:

What do we mean when we say that A communicates with B? We mean that the physical acts of A have induced a desired physical state in B. This transfer of information is a physical process and therefore is subject to the uncontrollable ambient noise and imperfections of the physical signaling process itself. The communication is successful if the receiver B and the transmitter A agree on what was sent.

Since cryptography is founded on computation and communication, which are both physical, and since physics is essentially quantum, it becomes natural to base cryptography on quantum physics. To put it more precisely: quantum cryptography is the endeavor to build secure cryptographic protocols whose security is based on quantum mechanics.

What does this mean? In the preceding subsection we remarked that any encryption scheme or protocol should (ideally) be accompanied by a mathematical proof of its security. For instance, for a scheme based on the assumption that factoring integers is hard, one wants to prove the following theorem: “if someone can break this protocol, it must imply s/he has found an efficient algorithm for factoring”; Since the latter is considered unlikely, at least using a classical algorithm, the protocol is considered secure.

In quantum cryptography we want to design protocols together with proofs of the following statement: “if someone can break this protocol, it must imply s/he has found a contradiction with the laws of quantum mechanics as we know them.” This feat would be even more surprising than finding an efficient way to factor; indeed, it would be a scientific revolution.

Quantum cryptography has a short but turbulent history. Apart from some early work by Wiesner, it started to evolve when Bennett and Brassard [BB84] defined a coding scheme (that is, they associated specific quantum states with the bits 0 and 1), usually called BB84, and invented a protocol to do key distribution. Then, after they built a prototype and published these results in the Journal of Cryptology and the Scientific American [BBBSS92 , BBE92 ] quantum cryptography attracted a lot of attention. It began to stimulate, and be stimulated by, its two neighbors: quantum information theory and quantum computing.

Though no person has serious doubts about the security of the quantum key exchange protocol, getting the formal proof right turns out to be fairly complicated. In the initial analysis of the Quantum Key Distribution protocol, in which Alice sends quantum particles to Bob, it was said that eavesdropping was impossible because of Heisenberg’s Uncertainty Principle. Apart from the fact that some physicist dislike the words ”uncertainty principle” (and for good reasons), the early proof considered only intercept/resend attacks, in which Eve does a complete (von Neumann) measurement on the particle and replaces it by a new one.

However, instead of fully destroying the state of a quantum system, nature allows much more subtle kinds of measurements: Positive Operator-Valued Measures, in which Eve disturbs the state just a bit (which decreases her chance of being detected) and in which she only gets partial information about the state of the particle sent from Alice to Bob. So qualitatively Eve is faced with the following choice: a high disturbance, which means she obtains much information and has a high chance of being caught, or low disturbance, which means little information but low chance of being caught, and all the gradations in between. Information versus disturbance is the physical principle on which Quantum Key Distribution is based, but it plays a role in other quantum protocols as well, as we will see.

Of course, people started to look for applications of quantum cryptography other than Key Distribution. Classical cryptography offers a wide range of tasks, so it is plausible to search for quantum variants for each of them. This seemed to work well: protocols were proposed for Bit Commitment (bc ) but finding a protocol with a proof for Oblivious Transfer seemed rather difficult, and finding a quantum signature scheme almost impossible (signatures seem to make an inherent use of one-way functions).

Functionally (i.e. as a task), Bit Commitment is not different from writing a 0 or 1 on a piece of paper, putting the paper in an envelope, sealing the envelop and putting it on the table. Then, in a later stage, A says: “I was committed to 0 (1),” and she proves this by opening the envelope and showing its contents to B. Though this may not be obvious, bc is an extremely powerful primitive: by combining large quantities of bc s one can construct powerful and beautiful protocols [BCC88 ].

The sequence of events related to Quantum Bit Commitment was dramatic:

(a) In 1993 Brassard, Crépeau, Jozsa and Langlois proposed a quantum protocol for Quantum Bit Commitment (qbc ) including a proof of its security [BCJL93 ].

(b) Attempts by Mayers and Salvail to find a quantum protocol for Oblivious Transfer without additional assumptions never succeeded.

(c) In September 1995, Yao announces he has found a protocol for Oblivious Transfer assuming error-less quantum transmission.

(d) In October 1995, Mayers decided to look critically at the proof of bcjl and discovered the wrong statement was proven (see Section 4.4.6 for details). In addition, he realized that not only the proof was wrong, but that the protocol could not work. Independently, Lo and Chau had come to the same conclusion.

(e) During that winter alternative protocols for quantum bc were proposed, which were subsequently broken.

(f) In March 1996 Mayers presented convincing arguments that no protocol for qbc can exist.

Let us look a little closer at the last point. Initially, the hope was that cryptographic protocols could be developed whose security would be based solely on the laws of quantum mechanics. This turns out to be impossible for bc , thus casting doubts on the existence of quantum protocols for other tasks. For instance, given a protocol for Oblivious Transfer we can make a protocol for bc , so it follows that no protocol for quantum Oblivious Transfer can exist. It must be realized that this is a purely theoretical result. The security requirements applied are very strict; in other words, theoretically dishonest parties are supposed to have all kind of resources and master technological skills that in reality may not (and may never) exist. Nevertheless, the result is disappointing, in the sense that the idea of having quantum analogues for all existing classical protocols, without any computational assumption, turned out to be futile.

Clearly, Mayers’s arguments led to much discussion. Part of the problem was that no one ever defined a proper model for what a quantum protocol exactly is, making the details of the proof somewhat hard to verify. Even today there is in my opinion no paper that clearly states the model with all its underlying assumptions properly explained, followed by a simple stepwise proof why qbc is impossible. The fact that recently two people have tried to advocate that qbc is possible [Bo97 , Ke97 ] seems to confirm this point.

The last chapter of this thesis develops a formal model for quantum protocols. It also presents a definition of security. However, from a quantum model to a definition of security there is a big step, and to ease the transition we have to deal with another subject first.

1.3 Classical and quantum indistinguishability

In classical cryptography, many definitions of protocol security use the notion of indistinguishability. In the design of cryptographic protocols, we often actually define a family of protocols parameterized by a security parameter n (for instance denoting the length of some string, the number of rounds, or the number of photons). Typically, we require that the probability of cheating for each participant vanishes exponentially fast, i.e. is of the order O(ε^{n}), where ε is between 0 and 1.

A common technique to define protocol security is to compare the protocol implementation (the family of protocols) with the ideal protocol specification and to require that these two become exponentially indistinguishable. We want to use this same technique, but before being able to do so, we must know how this indistinguishability notion generalizes to quantum theory. This is what Chapter 3 is about.

Classically, the objects we want to compare are probability distributions; for which several distance measures are known. Quantumly, the objects we deal with are density matrices. A density matrix is the complete description of what we know about the state of a quantum system (observe the “we know”: a density matrix is actually subjective, an issue we have to deal with). Mathematically, it is a matrix to which we apply another matrix, describing the measurement applied to the quantum system. The resulting mathematical object is a probability distribution, associating a probability to each possible measurement outcome.

When studying the literature one finds that there are actually various (more or less) natural measures of distance between quantum states, i.e. between density matrices. Fortunately, when we study these notions in the context of families of quantum states and require that the distance between pairs vanish exponentially fast, it turns out that they are equivalent. In other words, even though there are various notions of distance between quantum states, there is only one obvious notion of exponential quantum indistinguishability.

Somewhat coincidentally, the work in Chapter 3 has also found another application. Along the way inequalities on quantum distinguishability measures were obtained, which have not appeared in the literature before. Moreover, the distinguishability notion based on the Shannon information is notoriously difficult to compute, but we show that it can be bounded by the trace norm (the equivalent of the Kolmogorov distance or variational distance), which is much easier to handle. This bound plays an important role in an improved proof of the security of Quantum Key Distribution [BBBGM98 ]. This subject, however, is not discussed in this thesis, though qkd will be used as an example to illustrate some points in Chapter 4.

1.4 Security for quantum protocols

The main objective of this thesis is to present a formal model for quantum protocols, and to develop a definition of security (which includes privacy and correctness) for them. Most of the proofs for quantum protocols were somewhat ad hoc; having a more general framework for security is desirable.

In the classical case, many protocols are proven secure as follows: suppose that A (Alice) is convinced that B (Bob) is always able to generate (simulate) by himself, in probabilistic polynomial time, all the messages that he sees during the execution of the protocol, without access to A’s secret input. Then this protocol cannot leak any knowledge (= polynomially computable information) to B, neither about the secret nor about anything else. Such a protocol is called Zero Knowledge [GMR85 , GMR89 ]. The question is how this notion translates in the quantum setting.

Before we can answer this question, we first need a proper model for quantum protocols. We examine in detail the differences between classical and quantum information, and the consequences this has for adapting the classical definition of security to the quantum setting. We will see that a quantum computer can emulate measurements and (classical) probabilistic computations. But despite the fact that classical computation can be seen as a special case of quantum computation, we argue that for a proper definition of security the two types of information must be kept separate. This is related to the fact that generally quantum information cannot be copied, whereas classical information can.

As a model of computation we use Quantum Turing Machines for A and B, and describe their quantum channel by means of a quantum communication tape. We define the output, view and profile of a quantum protocol, and use a quantum interface (simulator) to compare the security of two protocols. It is at this point that we need the results of Chapter 3 about exponential indistinguishability of quantum states. After the formal definition of security, we present strong evidence that in our model the classical technique of rewinding is impossible.

1.5 Structure

The structure of the thesis is extremely simple. Chapter 2 describes definitions of security for classical protocols, which make inherent use of the notion of exponential indistinguishability for probability distributions. In Chapter 3 this notion is extended to exponential indistinguishability for density matrices. Chapter 4 follows the definition proposed in Chapter 2, extended to the quantum scenario. Consequently, this last chapter often refers to Chapter 2, whereas the first two main chapters are almost independent of each other.

The subject of this thesis lies on the boundary between cryptography and physics. I have approached the subject from a cryptographer’s point of view, trying to provide ample explanation concerning the underlying physical principles. Although many notions are explained in the text, familiarity with the following topics is helpful: state vector, Hilbert space, pure state, mixed state, superposition, entanglement, epr -pairs, von Neumann measurement, bra and ket notation, density matrix, tensor product, partial tracing (also tracing out). A very brief introduction to most of these notions can be found in the appendix of [BCJL93 ]; otherwise [Is95 ] is highly recommended. Other helpful references are [Su86 , Pe93 , Hu89 ].

As a final remark: this thesis extends various existing notions to a quantum setting, and the adjective ‘classical’ should be interpreted as ‘non-quantum’.

Classical definitions of protocol

security

Reality resists imitation through a model. Erwin Schrödinger

In a protocol for Multi-Party Computation n participants want to compute together a function f(x_{1}, x_{2}, ..., x_{n}) with the x_{i} being their respective inputs. Nobody wants to reveal information about his input except what can be logically deduced from the output. An example is, for instance, a majority vote held on the Internet, without a trusted party. Finding a definition of security for Multi-Party Computation is surprisingly difficult, even for relatively simple two-party protocols as (_{1}^{2})-ot, or evaluating an and gate.

In this chapter we explore what exactly these difficulties are. We present a definition, which is a minor variation on Beaver’s approach, and compare it with the works of Micali and Rogaway and Canetti, Feige, Goldreich and Naor, which have similarities in underlying philosophy.

We also compare with the approach of Brassard and Crépeau, whose definition is based on information theory. In particular, we show that a protocol which is secure according to the newly proposed definition, is also secure under their definition (but not the other way around).

The primary purpose of this chapter is not to present a complete formal model of security for protocols for Multi-Party Computation, but to survey the current literature on the subject. The goal of this thesis is to study definitions of security for quantum protocols, and this chapter serves to prepare the stage for this definition in Chapter 4, and to justify the choices made there.

2.1 Introduction

2.1.1 Brief historical overview

Traditionally, cryptology can be regarded as the sum of cryptanalysis (the breaking of cryptosystems) and cryptography, the art of secret writing. In the last 50 years, and especially in the last few decades, we have seen an effort to change cryptography from an art to a science: a proposal for a new cryptosystem or protocol should nowadays be accompanied by a mathematical proof of its security in order to be accepted in the scientific community. In practice, however, it is hardly true that every protocol in use today has been certified with such mathematical rigor, and (hopefully) sound engineering principles were applied.

It was before and during the Second World War that mathematicians in England and the United States became involved in information theory and cryptology. The first formal proof of security of a cryptosystem was published by Shannon [Sh48 , Sh49 ]. In the first paper he defines the notion of (mutual) information, in the second paper he uses it to show that the one-time pad is perfectly secure.

At first glance information theory might seem the ultimate tool to defining security, but this is not always true. A major problem with the information-theoretic approach is that it cannot provide a meaningful definition of security in systems whose security rely on the hypothesis that some problems are computationally intractable. For instance, many pseudo-random number generators, public-key cryptosystems and protocols rely on the assumption that it is practically impossible to factor an integer N that is the product of two large (say 200 digits) prime numbers P and Q. When one party announces his integer N, then from an information-theoretic point of view he also announces the factors P and Q, and that’s the end of the security discussion. To put it differently, information theory is only concerned with mathematical existence, not with computability, and in this sense an eavesdropper is considered to have unlimited computational resources. Although this thesis is not primarily concerned with computational cryptography, these issues have influenced the field enormously.

For example, a tremendous contribution to dealing with the issue of defining computational security was given by Goldwasser, Micali and Rackoff [GMR85 , GMR89 ], who defined the notion of zero knowledge. The intuition is as follows: suppose that A (Alice) is convinced that B (Bob) is always able to generate (simulate) by himself, in probabilistic polynomial time, all the messages that he sees during the execution of the protocol, without access to A’s secret input. Then this protocol cannot leak any knowledge (= polynomially computable information) to B, neither about the secret nor about anything else.

Their definition gave enormous impetus to the field. It was the first example of a definition of security that applied to a class of protocols, not just one specific protocol in particular. Apart from more technical (but nevertheless crucial) issues as rewinding/resetting the simulator and auxiliary input (which we discuss in more detail later on), it also led to a long discussion about what a definition of security should exactly include. This, however, also depends strongly on the context in which the protocol is used.

For instance, if a protocol for Proofs of Knowledge is used, in which A convinces another party B that she knows a witness of some statement in NP, then any amount of knowledge leaked about the witness is too much. But on the other hand, if the protocol is used as a signature scheme, leaking some bits of information is not necessarily disastrous, as long as the large majority of the bits cannot be forged. To deal with these issues the notions of witness hiding and witness indistinguishability were defined [FS90], but they are completely inadequate for our purposes.

Soon after the introduction of zero knowledge, people started to study the question whether Multi-Party Computation could be done. Suppose m participants want to compute together a function f(x_{1}, x_{2}, ..., x_{m}) with the x_{i} being their respective inputs. Let their respective outputs be defined as f_{i}. Nobody wants to reveal more information than is strictly necessary. That is, nobody party wants to reveal any information about his or her input except what can logically be deduced from one’s input and the output. The question was whether protocols exist that implement this task. This was an important question, because many protocols, including the millionaires problem [Ya82a ], digital voting [Ch81 ], coin flipping [Bl82 ], oblivious transfer [Ra81 ] and mental poker [SRA81 ] are just special cases of this.

We now know that such protocols indeed exist; in fact there are various ways to implement mpc based on different assumptions. For a short overview see [Gr95 ], but for a more thorough comparison, Chapter 2 of Franklin’s thesis [Fr93 ] is highly recommended. One common feature of these protocols is that most of them employ some sort of Bit Commitment or Secret Sharing schemes that each participant must use in order to provide his input, thus implicitly defining what the input of each participant is.

Another common feature is that many (if not all) approaches use the circuit representation of the function f, and show how individual gates (e.g. not and and) can be implemented. The question: “Which are the minimum cryptographic primitives needed to implement Two-Party Computation?” was answered by Kilian [Ki88]. He showed that if a protocol for Oblivious Transfer between each pair of participants exists, then they can evaluate any function f. The reduction from Multi-Party Computation to Oblivious Transfer was done by Beaver and Goldwasser [BG89].

A more efficient reduction from mpc to ot using coding theory can be found in [CGT95 ].

Nevertheless, despite the abundance of papers on the subject of Multi-Party Computation, and even though the security of all the proposed protocols is commonly believed to be true, most of them lack a rigorous mathematical proof. Even worse, they lack a proper definition. This is probably due to the fact that covering all the security aspects of mpc in a definition turns out to be much more complicated than one might expect.

2.1.2 Problems with defining security

Covering all the security aspects of a cryptographic task in a definition has turned out to be a quite difficult endeavor (many researchers speak about a project taking years). For instance, we have to consider the following security aspects:

Correctness: when all participants are honest, the output of the protocol is the same as the function it is emulating.

Privacy: no coalition of m′ participants can learn information about the input of an honest participant if he does not cooperate, except from what can be deduced logically from the coalition’s inputs and the output.

Honesty: no coalition of m′′ participants can make an honest participant accept an output that is inconsistent with the inputs of all the other participants.

Fairness: each participant should learn its output, i.e. no participant should be allowed to learn its output and quit before other participants have learned their output.

Resilience: this reflects the protocol’s ability to complete the computation of f if several participants stop cooperating during the protocol.

There are two major problems with this approach. In the first place, all these security aspects mentioned above seem to have a somewhat ad hoc character: how can we be sure whether we have covered all security aspects? Secondly, it can be shown that proving a protocol private and correct does not necessarily lead to a secure protocol. In other words, the simple conjunction of all security aspects is not always secure. The counterexample below (here adopted to a two-party setting) is due to Micali and Rogaway [MR91].

This counterexample uses the notion of a Bit Commitment. Intuitively this cryptographic task can be compared to A writing a 0 or 1 on a piece of paper, putting it in a strong-box, closing the strong-box and giving the strong-box to B, while keeping the key. This is the commit phase. In the open phase A gives the key to B, who opens the strong-box and sees the bit.

Counterexample: Let x and y be the inputs of A and B respectively. The function g they want to evaluate jointly is defined as

g_{A}(x, y) = g_{B}(x, y) := \{ \begin{matrix}0x & if lsb(y) = 0 \\ 1y & if lsb(y) = 1, \end{matrix}

where lsb(y) stands for the least significant bit of y, and where juxtaposition serves as the concatenation operator. Consider now the following protocol implementation:

(1) Both A and B use some perfectly secure Bit Commitment scheme to encrypt their input bits.

(2) B opens lsb(y).

(3) On the value of the bit opened, either A or B completely opens her or his input string, which is output by both parties.

(4) A sends x to B.

Clearly this protocol implementation leaks more information than it should because of step (4): according to the specification B learns A’s input x only when the lsb(y) = 0, whereas in the implementation B learns the value of x always.

Nevertheless, this protocol is private and is correct, when these notions are defined independently. Intuitively, the argument is as follows.

To see that the protocol is correct for both A and B is easy: obviously both parties output what they are supposed to. The fact that the protocol does more in step (4) is true, but is irrelevant as far as correctness is concerned; B can just ignore this information.

To see why the protocol is private for B, one must realize that for a dishonest B, who wants to maximize his information about x, the protocol allows for a perfectly honest strategy in which he always learns x: choose lsb(y) = 0. Thus, according to the protocol, A opens x in step (3), and when receiving x again in step (4) B doesn’t learn anything he didn’t know already. That the protocol is also private for A is obvious.

The function g is not as far-fetched as it seems; simple Boolean functions as and and or allow B a choice of input in which he always learns A’s input, making any definition of security that defines privacy and correctness separately void. Observe that the counterexample also works if A does not receive the output of g (though we have to be more creative to find a protocol implementation of this task).

This point is crucial if we want to use sub-protocols as building blocks for designing larger protocols, in the same way as subroutines are used to write large computer programs. Suppose we design a cryptographic task, which consists of several subtasks. To obtain a protocol implementation we would like to take an implementation for each subtask and combine them. But this implies we need that this sub-protocol acts as a black box, implementing the task it was designed for and providing the same security aspects as a black box. Having such a notion of “black box security” seems highly desirable if one wants to obtain a modular approach to protocol design. In other words, using terminology from complexity theory, we want to reduce the security of one protocol to some other protocol (or primitive).

Micali and Rogaway [MR91] were among the first to present formal definitions of mpc, using simulators in a way analogous to the definition of zero knowledge. This work continues the approach taken by Crépeau in [Cr90 ], which studies reductions between various flavors of Oblivious Transfer. Another approach was taken by Beaver [Be90 , Be91b ]. Though from a global point of view his approach seems similar, it differs significantly in some of the technical details. More recently Canetti, Feige, Goldreich and Naor [Ca96 , CFGN96 ] drawing inspiration from these results, have come up with another variation. In particular, their approach deals with mpc in a computational setting, which for a long time was considered to be difficult, but which makes it also less relevant here.

A completely different avenue was pursued by Crépeau and Brassard [Cr94 , BCS96 , BC97], who give a definition of One-out-of-Two Oblivious Transfer purely in terms of information theory.

The goal of this chapter is not to present a complete formal model of security for protocols for mpc, with formal proofs of all composition theorems etc.; this could easily be the subject of a thesis in itself. Instead, we want to emphasize the ideas behind the various definitions that exist, in order to prepare the stage for definitions of security for quantum protocols, the subject of Chapter 4. We do this by proposing a definition which is a minor variation on Beaver’s approach. Then we compare this approach with Micali and Rogaway’s, and Brassard and Crépeau’s, and argue why the choice made here is preferable.

So as not to complicate matters too much, we restrict ourselves to the task of Two-Party Computation. Consequently, many of the difficulties that arise when defining security of protocols for Multi-Party Computation are, interesting as they might be, eventually ignored. From now on, x and y will denote A’s and B’s input, while f_{A} and f_{B} are their respective outputs. As usual, A is feminine, B masculine, but E, the adversary, is referred to as a thing (contrary to the convention of calling it Eve).

2.2 The definition

2.2.1 Cryptographic tasks

It is important to make a distinction between a protocol specification and a protocol implementation, just as software engineering teaches us to do the same for programs. When talking about “a protocol for coin flipping” it is not immediately clear whether we refer to an abstract protocol for coin flipping (i.e. the protocol specification) or whether we refer to a specific implementation. In this thesis, and certainly in this chapter, we want to be precise about this distinction. Therefore we call a protocol specification a cryptographic task (or just task); for simple tasks (like bc or ot ) also the word primitive is used. On the other hand, protocol actually means a protocol implementation.

There are many conceivable ways of specifying a task, for instance simply by giving a specific protocol implementation, by specifying what would happen if some (or all) of the participants were honest, or by referring to some everyday procedure, like flipping a coin. A more uniform way is obtained by introducing a neutral party, called the trusted host, who serves as an intermediary to accomplish the task. For instance, Figure 2.1 and 2.2 specify the tasks for Bit Commitment and for Two-Party Computation, which are denoted as bc and tpc _{f} respectively. It is sometimes argued that tpc , or rather its generalization mpc, is so general that it comprises every cryptographic task conceivable. In a computational setting this may be true, but in a setting without computational assumptions this is not obvious at all. For instance, given a primitive for mpc it is not clear how to build a signature scheme.

One-out-of-Two Oblivious Transfer, denoted (_{1}^{2})-ot, is a special case of tpc _{f}. Let x be a string consisting of two bits, so x = x_{0}x_{1}, let y consist of one bit, and let f_{B} be the selection function: f_{B}(x_{0}x_{1}, y) := x_{y}. Furthermore, A’s output is the empty string, i.e. f_{A} = Λ.

[figure: A; TH; B; x∈{0, 1}; ‘bc received’]

[figure: A; TH; B; ‘open bc ’; x]

Figure 2.1: Task for Bit Commitment. First the commit phase, possibly followed by the open phase. The trusted host is the same.

[figure: A; TH; B; x∈X; y∈Y; f_{A}(x, y); f_{B}(x, y)]

Figure 2.2: Task for Two-Party Computation of f(x, y).

[figure: A; TH; B; x, w s.t. x∈L; x ∈ L]

Figure 2.3: Task for Proof of Knowledge.

Figure 2.3 specifies the task for a Proof of Knowledge. Observe that, apart from sending x, the prover A also sends the witness w to the trusted host. This point is overlooked in [Be90 ]. In the first place it is logical to assume that the trusted party is restricted to probabilistic polynomial time only; otherwise the trusted host could be asked to perform tasks that are hard to compute or not computable at all (as deciding whether two graphs are isomorphic or deciding whether two programs always have the same output). Moreover, if A does not send w as well, then B could use the trusted host as an oracle [Be96 ].

2.2.2 Cryptographic protocols

In the context of this chapter an honest party (including a trusted host, to be introduced later) is supposed to have access to a probabilistic polynomial time program which is entirely dedicated to running a protocol. We model this program as a Turing Machine to have an explicit way to specify the parties’ input and output. For a precise description of this model we make some minor modifications to the one presented by Crépeau [Cr90 ], in order to obtain a model that easily extends to quantum protocols, the subject of Chapter 4.

Apart from the input tape, work tape, random tape and output tape these Turing Machines, A and B, are equipped with one shared tape, the communication tape. Auxiliary inputs are dealt with by quantifying over all possible stochastic variables (see the remark following Definition 2.1), hence no auxiliary input tape is required. The parties take turns using this tape to send each other messages, and do not have simultaneous access to it. This is accomplished as follows: When a party does not have access to the tape, her/his tape head is in the start position. When a party gets access to the tape, s/he reads the message until the end marker and returns the head to the initial position. At a later stage this party sends a message by writing it on the tape finishing with an end marker. Then s/he returns the head to the start position, and gives a signal to activate the other party.

Both machines use some pre-agreed alphabet (for instance ASCII) and message format (for instance assigning special characters to act as field delimiters or end-of-message markers). Various choices are possible and have been presented in various places in the literature (see [Be91b , MR91]), but supplying such details hardly contributes to clarity of exposition. The main point is that the reader be convinced that, given a specific choice of an alphabet and a message format, the stochastic variables introduced in the next paragraphs are well-defined. Without loss of generality we can assume they are defined over {0, 1}^{∗}.

A protocol proceeds in steps; we assume that A starts. The input of a party is the contents of her/his input tape. Observe that the definition ensures that the operation of each program depends only on its input, its random bits, and on the message received, so that any additional information an honest party may possess does not influence program execution. The messages sent include meta-messages such as abort. If neither party aborts, then they end the protocol by sending each other accept messages and entering a halting state.

Let A and B denote the programs that A and B run when they execute protocol Π = [A, B]. Let [A, B](x)(y) denote the pair containing A’s and B’s output when they execute this protocol on input x and y. This is a stochastic variable because of the random tapes. By taking the first or second component we obtain a party’s individual output, denoted as [A, B]_{P}(x)(y).

We assume that each party devotes one track of its work tape for logging purposes only: we assume s/he makes a copy of each symbol it reads from the input tape, the random tape and the communication tape. S/he also makes copies of symbols sent off through the communication tape, and puts special markers when a new step begins. Thus the final state of the work tape of P includes the finite part of P’s random tape that s/he has read to obtain random bits, and the messages sent back and forth between A and B during the execution of [A, B] on x and y. This defines another stochastic variable which is usually called P’s view of protocol [A, B], denoted as [A, B]_{P}^{∗}(x)(y).

Attacks are modeled through an adversary, denoted E, who runs a Turing Machine E. The adversary can be more powerful than A and B: it is allowed unlimited computational resources, and has the capacity to corrupt parties. The latter means that when a party has been corrupted, E completely dominates and dictates this party’s behavior. In particular, E sees all the coin tosses generated by P, sees all the incoming messages received by P, defines the outgoing messages to be sent by P, etc. It is E’s objective to disrupt the honest execution of Π in one way or another, for instance obtaining partial information about the input of an honest party, or influencing the function’s output.

    [figure: A; B; E]

Figure 2.4: E attacks protocol [A, B].

In the special case of two parties, E corrupts either A, either B, or no one (needed for correctness). The case that E corrupts both is less interesting, since no honest party is left whose security interests have to be protected (but in a multi-party setting with a dynamic adversary it is interesting [Be91b ]). E cannot eavesdrop on the communication between A and B without corrupting either, so when corruption happens we may assume this takes place before the protocol started (conceptually in step 0), because a corruption during step r of the protocol is equivalent to the same party being corrupted from the beginning, but following the honest protocol up to step r.

Now we can extend the definition of protocol output and view to the situation where an adversary E running program E is present. Let [A, B: E]_{P}(x)(y) denote the stochastic variable that describes the output obtained by P when executing the protocol [A, B] in the presence of an adversary E who attacks either A or B. The view of a party is written as [A, B: E]_{P}^{∗}(x)(y), where P can be A, B or E.

In the definition in the next section we are interested in the triple consisting of the output of A, the output of B, and the view of E resulting from the same run of a protocol. We call this the profile of the protocol:

[A, B: E]^{‡}(x)(y) =^{def} ⟨[A, B: E]_{A}(x)(y), [A, B: E]_{B}(x)(y), [A, B: E]_{E}^{∗}(x)(y)⟩ (2.1)

Let X be a stochastic variable on the set X, the set of A’s allowed inputs, and let Y be defined similarly for B. We assume that A, B and E know the joint stochastic variable ⟨X, Y ⟩ on the set X ×Y. That is, for each run of the protocol we assume that a sample ⟨x, y⟩ is drawn from ⟨X, Y ⟩ and that x and y are subsequently written on A’s resp. B’s input tape. Note that a corrupted player can completely ignore its input tape, E may supply an alternative input if it desires so. We can replace x and y (the instances) with X and Y (the stochastic variables) in the definitions of output and view in the previous paragraphs. The stochastic variables thus obtained, written as [A, B]_{P}(X)(Y) etc., are again well-defined.

In the design of cryptographic protocols, we often actually define a family of protocols parameterized by a security parameter, n (for instance denoting the length of some string, the number of rounds, or the number of photons used). So, instead of obtaining one stochastic variable, we obtain a family of stochastic variables, parameterized by a security parameter. We say that two families of stochastic variables {Z_{1}^{(n)}} and {Z_{2}^{(n)}} are exponentially indistinguishable (which is denoted as {Z_{1}^{(n)}} ≈ {Z_{2}^{(n)}}) if they converge to each other exponentially fast:

∑_{z∈{0,1}^{∗}} |Prob[Z_{1}^{(n)}=z] − Prob[Z_{2}^{(n)}=z]| ≤ ε^{n}  (2.2)

for some ε between 0 and 1. This notion is discussed in more detail in Section 3.7 of this thesis. In the remainder of this chapter we will not explicitly include the security parameter in the notation or the definitions; its presence is implicitly understood.

2.2.3 Comparing the security of protocols

For a detailed analysis of the security of cryptographic protocols we need a method to compare the security of two protocols. For instance, in a computational setting one could imagine some protocol Π_{1} based on the assumption that the Schnorr identification protocol [Sc91 ] is secure. Formally this statement means that each attack on Π_{1} implies that there exists an attack on Schnorr’s scheme. In other words, we can say that Π_{1} is at least as secure (as difficult to break) as Schnorr’s scheme.

More generally we can define what it means for protocol Π_{1} to be at least as secure as Π_{2}, when we assume that Π_{1} and Π_{2} implement the same task. (Later, in Subsection 2.2.7, we discuss the situation when Π_{1} and Π_{2} implement different tasks.) Suppose that an attack E on Π_{1} exists. As in the previous paragraph, we require that any attack on Π_{1} implies an attack on Π_{2}. This requirement can be enforced by demanding the existence of an algorithm, S, capable of translating any enemy E_{1} attacking Π_{1} into an enemy E_{2} attacking Π_{2}. Let us define this more formally, following the terminology used in [Be91b ] but the notation introduced in [BCS96 ].

Let E_{1} be the set of possible Turing Machines E representing valid attacks on protocol Π_{1}; define E_{2} similarly. We say that S is an interface between Π_{1} and Π_{2} if for all E_{1} ∈ E_{1} we have that S(E_{1}) ∈ E_{2}. That is, S translates any valid attack on Π_{1} into a valid attack on Π_{2}. The purpose of the interface is to make protocols comparable. On one side of the interface the adversary E is situated, who thinks it attacks protocol Π_{1}. On the other side we have Π_{2}. It is the interface’s responsibility to let E talk ‘smoothly’ to Π_{2}, if necessary by modifying or creating messages.

As an elementary example, Π_{1} and Π_{2} could be two identical protocols, except that the message formats used are different. In this case the interface just has to translate the messages from one format to the other. The result is that an E attacking protocol Π_{1} is translated into S(E_{1}) attacking protocol Π_{2}, so S(E_{1}) is an adversary in its own right.

From the interface’s point of view, E is regarded as the code of some Turing Machine, and S can take “snapshots” of E’s configuration. This mechanism is called universal simulation; even though we have modeled E so far as Turing Machine, the existence of a Universal Turing Machine makes this choice reasonable. The rationale for this choice is discussed later in Section 2.3, but the idea is to allow S capabilities similar to an operating system like suspend, dump, resume, etc. We also require that the time S(E_{1}) needs to attack protocol Π_{2} is bounded polynomially by the time it takes E to attack Π_{1}. Observe that [Be91b ] uses black box access, and poses no time restriction on S.

Even though we assume here only two parties and corruptions right from the start, it is important to mention the following point: Another restriction we impose on the interface is that it translates corruption requests faithfully, i.e. instantaneously and to the same party. In particular, an interface is not allowed to issue a corruption request on its own (without a corresponding request from E). If such interfaces were allowed there would be no guarantee that both protocols behave the same in the absence of an adversary, thus jeopardizing the correctness-part in the definitions that follows.

The following definition formalizes the intuition presented in the first two paragraphs of this section, and is very similar to the one in [Be91b ]. Note that in the equation below, the third component of the profile [A_{2}, B_{2}: S(E)]^{‡}(X)(Y) stands for E’s view in protocol Π_{2}, not S(E)’s view. Recall that the first and the second component stand for A’s resp. B’s output. Consequently, the definition implies that the protocols Π_{1} and Π_{2} implement the same task.

2.1 Definition Protocol Π_{1} = [A_{1}, B_{1}] is at least as secure as Π_{2} = [A_{2}, B_{2}] if there exists an interface S from [A_{1}, B_{1}] to [A_{2}, B_{2}] such that for all E ∈ E_{1} and for all possible ⟨X, Y ⟩ which are joint stochastic variables on X ×Y:

[A_{1}, B_{1}: E]^{‡}(X)(Y) ≈ [A_{2}, B_{2}: S(E)]^{‡}(X)(Y).  (2.3)

By choosing X and Y to range over all possible stochastic variables, we deal with the problem of auxiliary information, such as information obtained from previous protocols. This issue is crucial in order to prove that the concatenation of secure protocols remains secure. To see why the definition presented here is equivalent to one where the universal quantifier ranges over all possible input and auxiliary input (see for instance [GMR89 , GO94, Cr94 , Be91a ]), observe the following: from A’s point of view, the variable X given an (arbitrary) auxiliary input can be regarded as another stochastic variable X′; its corresponding probability distribution is simply a readjustment of the probability distribution on X using the rules of conditional probabilities.

2.2.4 Sequential composition of protocols

One of the main objectives when defining security of protocols for Multi-Party Computation is to obtain a composition theorem: if we compose two arbitrary protocols which are secure, we want the sequential composition to be secure as well. (As an aside, note that the notion of security discussed in [BCC88 ], minimum disclosure, cannot meet this objective. A minimum disclosure protocol Π_{1} does not leak any information about the secret, but may leak other information. This other information could be vital in the breaking of another minimum disclosure protocol Π_{2}.)

First we make a small modification of a Turing Machine’s behavior at the end of the protocol: each symbol on the track of the work tape not used for logging purposes is moved (copied and erased) to the logging track, ended with a special protocol separator symbol. So all the information is moved to the logging track while the non-logging track is empty.

Let concatenation be denoted by juxtaposition. Then [A′A′′, B′B′′] stands for the execution of protocol [A′, B′] followed by [A′′, B′′]. A special symbol is used by A in order to separate the two inputs x′ and x′′ to both protocols. Note that it is permitted that x′′ depends on A’s output of [A′, B′]. Similar arrangements apply to B’s input, both parties’ output, and likewise for E. For simplicity we follow the convention that an abort in the first protocol means an abort of the whole protocol. The definition of the output of A and B, the view of E and therefore the profile of the composite protocol [A′A′′, B′B′′] should now be clear. We can now state the following protocol composition theorem.

2.2 Theorem Let [A′_{1}, B′_{1}] be as secure as [A′_{2}, B′_{2}], and let [A′′_{1}, B′′_{1}] be as secure as [A′′_{2}, B′′_{2}]. Then Π_{1} = [A′_{1}A′′_{1}, B′_{1}B′′_{1}] is as secure as Π_{2} = [A′_{2}A′′_{2}, B′_{2}B′′_{2}]

Proof: We have to show that there exists an interface S from Π_{1} to Π_{2} which satisfies equation (2.3) for any adversary E.

Suppose E corrupts neither party. Then S corrupts neither party, and (2.3) is fulfilled almost trivially.

Suppose E corrupts one party. Then S runs S′ until the end of Π′ is encountered, which can be recognized because of the accept messages sent. Then S runs S′′ until the end. To see why S indeed satisfies equation (2.3), observe that S can simulate Π′ correctly because S′ can. Similarly, S can simulate Π′ correctly; the auxiliary information possibly obtained in Π′ cannot change this, because Definition 2.1 ranges over all possible joint stochastic variables ⟨X, Y ⟩. Since for both Π′ and Π′′ a simulator must exist by hypothesis, S is an interface between Π_{1} and Π_{2}. □

This proof can be extended to the sequential composition of poly(n) protocols, where n is the security parameter. Recall that we defined S to be restricted to polynomial time in E, with the possibility to rewind. In sequential composition, if simulation of a sub-protocol fails, we can go back to the state before the sub-protocol had begun (because we had taken a snapshot), and try again. This technique is called rewinding, and we will discuss it later on. Even though it means that S needs more time the overall time only expands polynomially, as long as the probability of success is non-negligible. However, in parallel composition this does not work, because our probability of successful simulation is now exponentially small in n if rewinding is necessary.

2.2.5 Ideal protocols

An ideal protocol is the implementation of a task T in the presence of a trusted host. An ideal protocol is not the same as a task, though they look very much alike. A task is merely a specification of what a protocol is supposed to achieve. In contrast, in an ideal protocol A and B (when corrupted by the adversary E) can be dishonest and deviate from the protocol in any way they like. To put it differently, an ideal protocol is supposed to deal with all the eventualities of cheating or noncooperating parties. For instance, in Bit Commitment a cheating A could send a bit string instead of a bit, or just have sent nothing after some timer has expired. When this happens the trusted party sends the message not-cooperating to B and aborts.

A trusted host is by definition incorruptible and always cooperating. Observe that an adversary attacking an ideal protocol, even though limited, has some power nevertheless: it can force a corrupted player to supply different inputs than s/he is supposed to, or refuse to cooperate in the middle of the protocol.

The way the trusted host handles the irregularities it detects is always specified and is known to both A and B. A party who sends an input value outside the domain (X or Y) is cheating; when this occurs the trusted party could either report cheating and abort, or report and set the input to some default value known to A and B, or even set the input to some default value without reporting at all. The last two possibilities might be more relevant in a multi-party setting; in a two-party setting we assume that once cheating has been detected, any cooperation is broken off forever, so we choose the first possibility. We also suppose that in the ideal protocol the channel from an honest participant to a Trusted Party cannot be eavesdropped by E.

After this (intuitive) description of the trusted party’s behavior, the ideal protocol for a particular task is essentially unique. Ideal protocols will be written with calligraphic letters. It seems not difficult to extend the tasks presented in Section 2.2.1, such that ideal protocols for the tasks of bc , (_{1}^{2})-ot, tpc and pok are obtained.

However there is a subtle problem here with bc : in the ideal protocol a trusted host can detect a cheating A who commits to rubbish already in the commit phase, but in most (if not all) implementations this is discovered in the open phase. This seems an inherent consequence of the fact that bc is a two-phase task, as opposed to the other examples. One (maybe inelegant) way to modify the definition of an ideal Bit Commitment, is to specify that cheating which occurs during the commit phase is only reported during the open phase. Though this can hardly be called ‘ideal’, it seems a better reflection of what protocol implementations can achieve in reality. The modified ideal task for bc , written BC, is given in Figure 2.5.

[figure: A; TH; B; x∈{0, 1, cheating}; ‘bc received’]

[figure: A; TH; B; ‘open bc ’; x]

Figure 2.5: Modified ideal protocol for Bit Commitment. The trusted host does not report cheating during the commit phase, but during the open phase.

It can be argued that the distinction between a task and an ideal protocol is somewhat artificial. This is partially intentional; we defined a task to resemble an ideal protocol. The main issue is that the ideal protocol defines properly the trusted host’s behavior when it detects cheating. And it seems convenient to be able to say that an ideal protocol, for instance BC, is a particular implementation of the task bc .

2.2.6 Security

The ideal protocol provides us the perfect yardstick for expressing the security of a cryptographic protocol: we expect that a secure implementation of some task provide at least the same security as (is at least as difficult to break as) the ideal protocol for that task, thus comparing a situation without trust with one where there is trust. This is summarized in the following definition, which combines the definition of relative security with the notion of an ideal protocol.

2.3 Definition Let Π_{1} = [A, B] be the protocol implementation of a cryptographic task T, while Π_{2} = [A, B] is the ideal protocol for T. Then [A, B] is a secure protocol for T if [A, B] is as secure as [A, B].

  [figure: A; TH; B; S; E; A; B]

Figure 2.6: E attacks the ideal protocol [A, B] through S. The dotted line indicates what ‘image’ S is supposed to show to E. Compare this with Figure 2.4.

Figure 2.6 depicts the intuition behind this definition.

Note that there exist various other ways to express this definition. Some people would say that the protocol [A, B] is simulatable with the help of the ideal protocol [A, B]. For the special case of joint function evaluation, i.e. mpc, the ideal protocol is also called a function oracle. One could also say that the protocol [A, B] reduces to the ideal protocol [A, B].

Correctness and privacy can now be seen as special cases of this definition. Correctness (and honesty) is obtained by restricting the two profiles (triples) in Equation (2.3) to their first two components, A’s and B’s output. Privacy is obtained by restricting to the last component, E’s view.

Let us now return to our Counterexample on page 17, and argue that the protocol presented there does not pass this new definition. Let [A, B] be the protocol implementation using Bit Commitments and let [A, B] be the ideal protocol for Two-Party Computation of the function g. Consider an adversary E that corrupts B but that is otherwise honest. Such an adversary, representing an honest-but-curious B, is perfectly well-defined, and we show that there cannot exist an interface which satisfies definition 2.1.

Recall that the interface S, with the help of [A, B], must provide a profile indistinguishable from the profile of [A, B], for any distributions on the inputs x and y. Suppose that lsb(y) = 1. If the interface S passes y to [A, B] unmodified, it will not learn x. Therefore, except with negligible probability, S cannot simulate step (4) of [A, B], and E’s view in [A, B] will almost always differ from its view in [A, B]. Alternatively, S could modify the least significant bit of y to 0, in order to learn x. But this will also modify A’s output in [A, B] to 0x, whereas in [A, B] A’s output equals 1y. We conclude that whichever value S chooses as the least significant bit of y as input to [A, B], the profiles of [A, B] and [A, B] are always different.

2.2.7 Reductions

The composition of ideal protocols does not automatically yield an ideal protocol. The problem is that for each sub-protocol (primitive, black box) a different Trusted Party is used, but there is no “overall” trusted party who verifies that inputs and outputs from sub-protocols are indeed consistent. In other words, even though the protocols themselves are guaranteed to be honest, their input and output do not have to be. This can be solved by imposing extra conditions on the input of sub-protocols. For instance, in the reduction from BC to (_{1}^{2})-OT , the protocol is performed n times in parallel [Ki90], or (more efficiently) an error correcting code is imposed on the inputs to (_{1}^{2})-OT . Note that this is a one stage reduction: input are given to many copies of (_{1}^{2})-OT , and many outputs result.

Things become even more complicated in multi-stage reduction, where the output of one ideal protocol is used as input for the next protocol. For instance, the ideal protocols could represent the and , or and not gates of a circuit to be evaluated. Only Beaver’s methods [Be90 , Be91a ] seem sufficiently developed to give a formal proof that Two- and Multi-Party Computation can be built from such primitives. The details of these techniques are beyond the scope of this thesis.

2.3 Comparison with other definitions

The discussion so far has mostly followed the approach presented in [Be91b ]. First we compare it briefly with similar approaches. Then we elaborate on the computational power of S and its access to E.

2.3.1 Oracles, simulators, etc.

Besides [Be91b ], definitions of security have been proposed by Micali and Rogaway [MR91] and Canetti, Feige, Goldreich and Naor [CFGN96 ]. In spirit, all three approaches are similar. It is in technical details and in terminology that differences occur. The issues are the following:

(a) An interface in [Be91b ] corresponds to a simulator in [MR91] and [CFGN96 ]. Similarly, an ideal protocol in [Be91b ] corresponds to an oracle in [MR91] and [CFGN96 ]. Let us restate the intuition behind [Be91b ]: protocol Π_{1} is as secure as the ideal protocol Π_{2} if each attack on Π_{1} can be converted into an attack on Π_{2}: an attack on the whole implies an attack on its components. The intuition behind [MR91] and [CFGN96 ] is an extension of the intuition behind zero knowledge: protocol Π_{1} is secure if the adversary can simulate its view of the protocol with the help of an oracle which represents the ideal protocol. In the original definition of zero knowledge no oracle was necessary, since the fact that x is in L is, by assumption, exactly the information conveyed by this protocol. To a large extent both intuitions are valid and interchangeable, they just are different ways of seeing the same problem, the simulator paradigm probably preferred by people who are more familiar with the original definition of zero knowledge. Indeed, Figure 2.6 supports both point of views. But it seems that the approach of [Be91b ] is somewhat crisper, making it easier to derive precise definitions, especially when the exact powers of the interface (simulator) and the ideal protocol (oracle) have to be specified. Moreover, in situations such as the example given at the beginning of Section 2.2.3 (a protocol as secure as Schnorr’s identification protocol) the simulator paradigm seems less appropriate.

(b) In [Be91b ] the notion of relative security and the notion of an ideal protocol are introduced separately, and absolute security is obtained by using the ideal protocol as just another protocol implementation. In [MR91] and [CFGN96 ] these two notions are intertwined in one definition, which makes it less general.

(c) In [Be91b ] the protocol task could be anything, whereas [MR91] and [CFGN96 ] restrict themselves to Multi-Party Computation (i.e. evaluation of a function f). For instance, a definition of security for bc does not follow immediately; though not difficult, some minor adjustments seem necessary.

(d) In [Be91b ] the profile is used to compare protocols, whereas the condition in [MR91] (definition (3.10)) gets rather complicated, reason why we prefer the first. We return to this point in Section 2.5.2. In [CFGN96 ] the approach of [Be91b ] is adopted.

2.3.2 The relation between S and E

In this section we return to the discussion about the computational strength of the interface S, and its access to the adversary program E, as was mentioned in Section 2.2.3. Though at first glance this may seem a minor technical point, it turns out that the choices made here significantly influence the notion of security obtained. This is already true for the classical definition; but is also of crucial importance in the quantum setting, as we will see in Chapter 4.

Much of what is discussed in this section goes back to the definition of zero knowledge. As has been mentioned already, the intuition behind the definition of zero knowledge is as follows: suppose that a participant is always able to reproduce by himself all the messages that he sees during the execution of the protocol. Thus this protocol cannot leak any knowledge (= polynomially computable information) about the secret nor about anything else.

Even though the intuition is clear, there are various ways to formalize it. The most important issues are listed below; they are interrelated.

(a) The order of the quantifiers. In the original definition of zero knowledge as presented in [GMR85 ], it is required that for all adversaries E (verifiers) there exists an interface (simulator) S that reproduces the conversation with (almost) the right probability distribution. However, in [BC89] it is argued that, certainly in the original context of computational protocols for proofs of knowledge, this seems unreasonable. For example, suppose that such an S exists, but that it is computationally infeasible to find. This implies that for a polynomial-time interface it would be easier to find the secret (the witness proving that x ∈ L) in order to provide a simulation, than to find the simulator. Therefore it seems impossible to maintain that E has gained nothing from the interaction. A possible alternative, put forward in [BC89], is to reverse the quantifiers in the definition: there exists an interface (simulator) S such that for all adversaries E the conversation can be reproduced. This line of thinking is also adopted by [Be91b ] and [MR91]. (The manuscript of [MR91] seems to contain reminders to the authors to devote a paragraph to the order of the quantifiers; unfortunately none have been written. In his thesis [Ro91 ], Rogaway makes the same choice, but does not discuss the issue either.)

(b) The computational power of the interface. The interface should never be more powerful than the adversary, since it would imply that the combined adversary S(E) is much stronger than E alone. Consequently, the definition would proclaim Π_{1} as secure as Π_{2}, even though the first one is attacked by a much weaker adversary. Note that this can happen inadvertently. For instance, even if E_{1} includes unbounded adversaries programs E, the quantifier for all includes also computationally limited E. If S needs to work very hard (say exponential time) in order for S(E) to be an attack against Π_{2}, the same argument applies. As an example, take Π_{1} to be a (non-cryptographic) protocol in which A sends a string to B; while in Π_{2} the same string is ‘encoded’ as the solution of some NP-complete problem. We will return to this point below and justify our choices.

(c) The extent to which the interface can influence the adversary. In all definitions S takes E as an input. However, there are several conceivable ways this can be done. The following two ways are the most important ones.

(i) S gets the code of the algorithm E, for instance as a program for a universal Turing Machine. This is called universal simulation by Oren [Or87 ], and is also preferred in [BC89]. Of course, S is not granted any powers that are considered infeasible, but it seems reasonable to allow S powers similar to an operating system running a specific program. In particular, we could allow S to make a complete ‘snapshot’ of the program E, i.e. a dump of all its memory and program counters, to run several copies of this process maybe using different inputs, to suspend or to kill such processes, etc. Note that it explicitly includes the capacity to rewind E, i.e. to make E go back to an earlier state. This can be done by making snapshots during the computation, and to erase any trace of a computation that went “too far”.

(ii) S gets E as a resettable black box. This means that S has no knowledge about, nor control over what is going on inside the program E. However, S is allowed read/write access to all E’s tapes, including its random tape. In other words, it is somewhat like universal simulation though without the ability to make snapshots, but including the ability to start all over again, using different bits on the input and random tapes. Resetting gives the interface S the power to rewind E. The idea is that S can restart E from its initial configuration and halt it when it reaches the desired configuration. Note, however, that this implies that the randomness is provided to E by means of a random tape. As soon as E gets its randomness from an internal random source (for instance, by pushing a button or really tossing a coin), S’s capability to rewind E is revoked.

The history of these notions is as follows. The original definition of zero knowledge [GMR85 ] contained a flaw: it lacked the desired property that the sequential composition of zero knowledge protocols was again zero knowledge. This was observed by several researchers independently, including the authors. It is resolved by requiring that, even when given arbitrary side information, usually called auxiliary input, the real and the simulated conversation are indistinguishable.

Oren [Or87 ] showed that black box zero knowledge implies universal simulation zero knowledge, which in its turn implies auxiliary input zero knowledge. Moreover, even though the black box definition seems restrictive, it turns out that all proofs in fact used a reasoning equivalent to black box simulation to show that such a simulator exist. To some extent this has led to black box zero knowledge having been accepted as the de facto standard; for example, in Oren’s final paper, together with Goldreich [GO94], no mention of universal simulation is made. This is unfortunate, because it somehow precludes any discussion about the rationale behind the black box definition. It seems that the following fundamental question often has been side-stepped: What is the significance of the existence of an adversary E_{1} which attacks Π_{1}, in an attack against Π_{2}? We believe that the following guidelines should be taken into account, though do not claim to have the ultimate answer to all the issues discussed in the previous subsections.

(a) The interface S and the adversary program E are ‘friends’. They cooperate in attacking Π_{2} (or in providing the optimal simulation, if you prefer this paradigm). There is no reason why E hides something from S, on the contrary.

(b) The manner in which the attack against Π_{2} is modeled given E should be ‘constructive’. Merely mathematical existence of S still does not mean that an entity which wants to construct S given E is capable of doing so. Observe that our ‘universe’ is full of mathematical notions which can be defined perfectly, but which are irrelevant since they are not computable. (Chaitin’s number Ω, a real number that encodes the Halting probability, is an example; see for instance [LV93] for discussion.) This is why we prefer that there exists an interface S for all adversaries E which can reproduce the same distribution.

(c) The computational effort it takes to attack Π_{2} should bear some reasonable relation to the computational effort it takes E. This means that S should not be given powers that are computationally infeasible. We believe that universal simulation is a good approximation of what in reality S can achieve, which includes the making of ‘snapshots’. In addition, we require that the total time it takes S to attack protocol Π_{2}, which includes the time it takes to run E as a procedure, is polynomially bounded by the time it takes E to attack Π_{1}.

The following table presents an overview of the choices made by several authors on the issues discussed in this section. However, the reader must be warned that more differences in the models and definitions exist, in particular with respect to the notion of indistinguishability used. The model referred to in the last line is quite different, and is the topic of Section 2.5.

paper  order  computational computational simulation
quantifiers power of E  power of S  ( S’s access to E)
[GMR89 ]  ∀E ∃S     BPP  BPP  auxiliary input
[Or87 , GO94] ∀E ∃S     BPP  BPP  black box
[CFGN96 ]  ∀E ∃S     BPP  BPP  black box
[BC89]  ∃S ∀E     BPP  BPP  universal simulation
[MR91]  ∃S ∀E  non-computable unrestricted TM black box
[Be91a ]  ∃S ∀E  unrestricted TM unrestricted TM black box
here  ∃S ∀E  unrestricted TM BPP  universal simulation
[BCS96 ]  ∀E ∃S  (the equivalent of) E and S can be non-computable

Table 2.1: A comparison of various definitions of security.

2.4 Simulatability and security

2.4.1 Physical assumptions

It must be emphasized that the preceding definitions hide some physical assumptions. For instance, the choice to extract the randomness of a Probabilistic Turing Machine by putting random bits on a dedicated tape and then using a Deterministic Turing Machine is one such assumption. If the randomness came from some internal, non-resettable source instead (or if we simply assumed that the tape is read-only and cannot be tampered with), then the simulation fails and many existing proofs of security for protocols completely collapse.

Next it must be realized that the view of a party is also something physical. In particular, the view is what a party sees on the tapes of his Turing Machine, to be compared with what he sees when using envelopes, playing cards, etc. Moreover, the fact that the interface S can create or modify the incoming messages of the adversary E is also a physical assumption. If A and B use pieces of paper to transmit their bits, with unforgeable signatures on the reverse side, the interface will almost always fail to satisfy E.

The previous paragraph, together with the definition of ideal Bit Commitment BC by means of a trusted host, implies that the interface can trivially open a bit commitment anyway it likes. It simply ignores the bit sent by B in the open phase and replaces it by the bit it needs. In the terminology of [BCC88 ] the ideal BC protocol is chameleon, i.e. it can be opened by the interface in either way. Note that this simulation does not significantly differ from the way Kilian simulates the (_{1}^{2})-ot [Ki90, p. 104]. The point is that in this model the view of a party is limited to what is written on his communication tape; who puts incoming messages on it is invisible to him. The tape acts as a barrier, beyond which any party, including the adversary, cannot penetrate.

Such a barrier is also present in what is probably the first indistinguishability test in computer science: the Turing test. In this well-known procedure, a human must distinguish another human from a computer generating human-like conversation. The interaction takes place through a keyboard and screen, which act as the barrier. In the every-day context of cryptography this barrier is not unreasonable: my physical view is limited to the wire that connects my computer to the socket in the wall, beyond it there is a network of which I know nothing, apart from the bits coming in and out.

2.4.2 Protocol security

Simulation, that is, an interface having to satisfy E, seems so far the only general method of defining security for protocols. However, it can be argued that for individual protocols, defined for a specific task, this need not be the case. For instance, the definition of a secure Bit Commitment protocol is possible without necessarily using simulatability. But this raises the following two questions:

(a) Do we believe that BC, and a physical implementation of bc , e.g. using an envelope or a strong-box, provide exactly the same security?

(b) If the answer to (a) is yes, can we freely interchange one for the other in the context of a larger protocol, without affecting security?

The first question can, in my opinion, never be answered mathematically, only by common sense, since the two models are inherently incompatible. In my opinion, the answer to this question must be ‘yes’. In the first place it seems easy to verify that whatever A and B can do in one protocol, it can also do in the other. Moreover, the definition of BC is completely based on our (classical) physical intuitions about what envelopes can achieve; if there was a mismatch it would mean that our definition of BC did not capture the right notion and we would have to adjust it. Answering ‘no’ would be to reject the definition. Indeed, the definition of many protocol tasks, and the kind of security it should provide, are based on the functionality of physical objects, such as envelopes, playing cards, signatures, unreliable mail service, elections, etc. Cryptographic protocols try to model this functionality.

With regard to the second question: if we believe that an envelope provides the same security as a strong-box, then using one as a primitive for a larger protocol or the other should not make any difference. However, if we extend this reasoning to BC, we suddenly get a feature that envelopes and strong-boxes don’t have: since E does not know where a bit sent to it comes from, S can open any BC either as a 0 or as a 1. This is a simple consequence of the different physical model used, but leads to some puzzling questions.

To conclude, my opinion is that simulatability is not a feature that reality gives us, but always depends on the way we model reality. If we change the model, we may be able to simulate more, or less. The latter seems to be the case for quantum protocols. On the other hand, no alternative ‘paradigm’ seems available, at least not at the moment. Information theory does not provide a way out, as we will see in the next section.

2.5 Another approach: using information theory

2.5.1 The definition

In [Cr94 ] and [BCS96 ], Brassard and Crépeau follow a different approach to obtain a suitable definition of security for the particular task of One-out-of-Two Oblivious Transfer. This approach is extended in [BC97] to Generalized Oblivious Transfer (got ). This protocol is an extension of of (_{1}^{2})-ot: B gets only one bit of information about the two bits put in by A. However, in got B’s bit can be any Boolean function on the two input bits of A at B’s choosing. Again, A receives no output. So A’s input consists of two bits, x_{0} and x_{1}, B’s input consists of a predicate y from the set of all possible predicates (functions) from {0, 1}^{2} to {0, 1}. Then B receives y(x_{0}, x_{1}) while A receives nothing.

Below we have “naively” extended the definition of security for got from [BC97] to secure evaluation of an arbitrary function f(x, y), that is, to tpc . So when we take the definition below and substitute f=got , X ={0, 1} and Y={p : {0, 1}^{2} → {0, 1}} we obtain their definition, the definition is downwards compatible. Then we compare this new definition with the one we presented earlier, Definition 2.3, and explain why we call the extension naive.

2.4 Definition (Naive extension of [BC97] – correctness part) Protocol [A, B] is correct for Two Party Computation of the function f(x, y) if

(a) for all x ∈ X , y ∈ Y

[A, B](x)(y) ≈ f(x, y);  (2.4)

(b) for any program Ã there exists a program Ã′ such that for all x ∈ X , y ∈ Y

[Ã, B]_{B}(x)(y)|B accepts ≈ [A, B]_{B}(Ã′(x))(y)|B accepts  (2.5)

(c) for any program B̃ there exists a program B̃′ such that for all x ∈ X , y ∈ Y

[A, B̃]_{A}(x)(y)|A accepts ≈ [A, B]_{A}(x)(B̃′(y))|A accepts  (2.6)

Condition (2.4) expresses that, when both participants are honest, the protocol indeed performs the task it has been designed for. Condition (2.5) expresses that the best cheating A can do in order to influence B’s outcome is always equivalent to her calculating an alternative input Ã′(x) and otherwise being honest during protocol execution, something which she can do anyhow. We assume that Ã′ has access to Ã. By the way, observe that the right hand side can also be replaced by f_{B}(Ã′(x), y) because of the first condition. Condition (2.6) is similar to (2.5) with the roles of A and B reversed.

The preceding definition constituted the correctness part. For expressing privacy we use the Shannon entropy function, denoted H (see [CT91] for a definition, for instance).

2.5 Definition (Naive extension of [BC97] – privacy part) Protocol [A, B] is private for Two Party Computation of the function f(x, y) if

(a) for any joint stochastic variable ⟨X, Y ⟩ over X ×Y and for any program Ã there exists a stochastic variable X̃ over X such that

H(Y |[Ã, B]_{A}^{∗}(X)(Y), f_{A}(X̃, Y)) ≈ H(Y |f_{A}(X̃, Y))  (2.7)

(b) for any joint stochastic variable ⟨X, Y ⟩ over X ×Y and for any program B̃ there exists a stochastic variable Ỹ over Y such that

H(X|[A, B̃]_{B}^{∗}(X)(Y), f_{B}(X, Ỹ)) ≈ H(X|f_{B}(X, Ỹ))  (2.8)

The right hand side of condition (2.7) denotes A’s uncertainty about Y, given one run of the ideal protocol to which she can supply an alternative input X̃. The left hand side of (2.7) reflects that in the real protocol A potentially gains additional information through her view of the protocol. Nevertheless, the equality expresses that the additional information A gains about B’s input through her view is negligible, so the real protocol is as private as the ideal one. Using mutual information (I) instead of entropy (H) the last two conditions can be written more succinctly.

Expressed in this way, however, the comparison between the ideal protocol and the real implementation becomes more evident.

Typically the stochastic variable X̃ depends on Ã and on X (which includes dependence on auxiliary input). In this definition only the mathematical existence of X̃ is required, it need not be computable. So with this information-theoretic definition of privacy protocols can exist which are private against an all-knowing and infinitely powerful entity, but not against a party with limited resources.

In the model presented in Section 2.2 the role of X̃ (providing the ideal protocol with a suitable input) is taken care of by the interface. Its other responsibility, providing a proper simulation of the protocol [A, B] to B̃ (corresponding to the adversary), is implied by equation (2.7). The fact that A gains no information about Y from her view f_{A}(X̃, Y) means that in a way she ‘knew’ it already, so it can be written as a function: [Ã, B]_{A}^{∗}(x)(y) = V (f_{A}(x̃, y)). As with X̃, the function V is not necessarily efficiently computable.

The most significant differences between Definitions 2.4 and 2.5 together, contrasted to Definition 2.3 presented earlier, are the following:

(a) Here correctness and privacy are defined separately, and the same problem with the Counterexample occurs. It is argued in [BCS96 ] that in the special case of (Generalized) Oblivious Transfer this is not a problem because A receives no output.

(b) The order of the quantifiers is reversed. This issue was already discussed in the previous section.

(c) The computational powers of the interfaces differ: here X̃ and V can be any function, while in Definition 2.3 they have been combined in one algorithm S which is restricted to probabilistic polynomial time.

2.5.2 Modifying the definition; awareness

Now we will modify Definitions 2.4 and 2.5, so that the result resembles Definition 2.3 more closely. The following definition reverses the order of the quantifiers, and requires that A′ used for correctness and privacy be identical. But it does not resolve the issue about V being possibly non-computable, so the equivalence of the two approaches cannot be established.

2.6 Definition Protocol [A, B] is secure for Two Party Computation of the function f(x, y) if

(a) for all x ∈ X and for all y ∈ Y

[A, B](x)(y) ≈ f(x, y);  (2.9)

(b) there exists a program Ã′ such that for any program Ã, for all joint stochastic variable ⟨X, Y ⟩ over X ×Y, and for all x ∈ X , y ∈ Y

[Ã, B](x)(y)|B accepts ≈ f(Ã′(x), y)  (2.10)

and

I(Y; [Ã, B]_{A}^{∗}(X)(Y)|f(Ã′(X), Y)) ≈ 0  (2.11)

(c) as (b), with the roles of A and B reversed

This definition resembles definition (3.10) of [MR91]. There Micali and Rogaway explicitly require that the cheating party can compute the alternative input; they call this input awareness. The function Ã′ is the adversary input function, for which they insist that the same function be used in both the privacy and the correctness part. Indeed, it is easy to see that the Counterexample no longer passes the definition, because the B̃ that would pass the privacy condition (the reverse of (2.11)) cannot simultaneously satisfy the correctness condition (the reverse of (2.10)).

The last definition also captures the notion of output awareness, through a small modification that could easily escape the reader’s attention. The original correctness condition (2.5) expressed that only the honest party (B in this case) gets the same output (it is subscripted with B). The new correctness condition (2.10) requires however that all parties, including the cheating party, get the same output.

The crucial point, observed in [MR91], is that even if a party is corrupted, we have to worry about its output being well-defined as a result of the protocol. In the ideal protocol, a cheating party gets the output from the trusted host; this should also be reflected in the real protocol. Moreover, for a solitary protocol we may not have to care about the output of a cheating party. But if we want to prove a theorem about protocol composition, we need the outputs of all parties to be well-defined. Otherwise, in the case where the input of a protocols depends on the output of a preceding protocol, the adversary runs in trouble.

This additional requirement is captured by output awareness: the adversary should be able to compute a cheating party’s output as a function of all the messages it sees. Awareness stands for both input awareness and output awareness. Definition 2.4 covers input awareness, but careful inspection reveals that a cheating B̃, for instance, does not necessarily learn what output he obtains from the protocol. The same objection applies to the earlier definitions for security of (Generalized) Oblivious Transfer, so in this respect these definitions are inadequate.

2.6 Conclusion

In the last section we have seen how subtle and complicated the definition based on information theory has become. We had to realize that correctness and privacy must be coupled, and the notion of (input and output) awareness had to be introduced. On the other hand, observe that these two constraints are natural derivatives of Definition 2.3.

Note added in proof: After this thesis was handed in, Joe Kilian pointed out that there is an additional complication with definition 2.4, which also applies to its earlier versions. Suppose that there exists an Ã who always tries to cheat, and that she succeeds doing so with exponential small probability. If she fails B always rejects. In this case equation 2.5 will not be fulfilled, even though the protocol ‘should’ pass the definition. It is very difficult to argue that such an Ã does not exist, so the definition rejects many protocols that may be considered secure.

Indeed, the pleasing aspect of Beaver’s approach is its intuitive appeal: we may have to worry about the exact relation between interface and adversary, but otherwise it seems quite convincing that all security aspects are incorporated. Moreover, composition theorems are relatively easy to prove. It is for this reason that we abandon the information-theoretic approach here, and adopt the interface (simulator) approach in this thesis.

Distinguishability of quantum states

[...] the ‘imitation game.’ It is played with three people, a man (A), a woman (B), and an interrogator (C) who may be of either sex. The interrogator stays in a room apart from the other two. The object of the game for the interrogator is to determine which of the other two is

the man and which is the woman. Alan Turing

This chapter surveys four measures of distinguishability of quantum states: probability of error, trace norm (related to the Kolmogorov distance), overlap (related to the Bhattacharyya coefficient) and Shannon distinguishability (defined through the mutual information).

These measures have their roots in measures of distinguishability of probability distributions, from which a collection of inequalities can be obtained. These inequalities can be shown to hold also in the quantum model. We obtain upper and lower bounds for the Shannon distinguishability. This is important because explicit computation of the Shannon distinguishability is often difficult, while the other distinguishability measures are usually easier to evaluate. We derive a very simple upper bound on the Shannon distinguishability as a function of the trace norm.

Moreover, cryptography often uses the notion of exponential indistinguishability of two probability distributions. This notion expresses that the Kolmogorov distance between two probability distributions vanishes exponentially fast when the security parameter increases. Similarly, exponential indistinguishability of two families of quantum states can be defined: we require that the distinguishability between two families of quantum states vanishes exponentially fast. It turns out that exponential indistinguishability is independent of the specific measure chosen in the definition; the four different definitions are equivalent.

3.1 Introduction

If one wants to model and analyze the cryptographic security of quantum protocols, one of the first questions to be answered is: What does it mean for two quantum states to be “close” to each other or to be “far” apart? That is, we need a notion of distance between two quantum states. The state of a quantum system is usually described by means of a density matrix, but various definitions of distance are available, and preferences may depend on the problem at hand and the point of view taken.

However, key properties that we would like them to satisfy are (1) that they are symmetric, (2) that they are invariant under unitary transformation (in other words, independent of the choice of the basis), and (3) that they somehow correspond to a conceivable physical experiment. Because of the latter constraint it is more appropriate to speak of measures of distinguishability.

In this chapter we will discuss four notions of distinguishability that are of particular interest to cryptography: probability of error, trace norm, overlap and Shannon distinguishability. Each of these four distinguishability measures is a generalization of a distinguishability measure between two (classical) probability distributions.

This also allows us to find the interrelations (inequalities) between these quantum distinguishability measures.

We establish a connection between the probability of error (or the Kolmogorov distance; the two are intimately connected) and the trace norm which apparently has not been noticed before. We derive a simple upper bound on the Shannon distinguishability as a function of the trace norm: SD(ρ_{0}, ρ_{1}) ≤ \frac{1}{2}Tr|ρ_{0} − ρ_{1}|. Here ρ_{0} and ρ_{1} are density matrices, representing the states of two quantum systems. This bound may be very useful; for instance, in [BBBGM98 ] it is used to prove security of Quantum Key Distribution for a general class of attacks. Similarly, we can bound the Shannon distinguishability by the overlap between ρ_{0} and ρ_{1}.

In the design of cryptographic protocols, we often actually define a family of protocols parameterized by a security parameter, n (denoting for example the length of some string, the number of rounds, or the number of photons). Typically we require that the probability of cheating for each participant vanishes exponentially fast, i.e. is of the order O(ε^{n}), for ε between 0 and 1. In Definition 2.1 this plays an important role as well. It is therefore natural to consider two families of quantum states parameterized by n and to require that the distinguishability between the two families (defined by the pairwise distinguishability) vanishes exponentially fast. A priori this definition will depend on which distinguishability measure is chosen, but it is easy to show, as will be done, that exponential indistinguishability with respect to one distinguishability measure implies exponential indistinguishability with respect to each of the other distinguishability measures. In other words, these four notions are equivalent, and therefore it seems legitimate to talk of the notion of exponential indistinguishability for two families of quantum states.

This notion could be useful when defining the security of quantum protocols; indeed, this was initially the main motivation for this research. For instance, in [BMS96 ] it is proven that the Shannon distinguishability of the parity (i.e. the overall exclusive-or) of a quantum-bit-string decreases exponentially with the length of the string. This statement as such can be proven very easily using the techniques presented here, as will be shown in Section 8, without the need to keep track of the exact description of the density matrices involved (these tend to become quite complicated because of the tensor products involved).

The contribution of this chapter is three-fold. In the first place, even though some parts of this chapter are based on facts that have been known for some time, many of these facts are scattered throughout the literature, sometimes in papers that use an unusual terminology making it difficult to see that they are relevant. Elements of this work can already be found at various places in the work of Fuchs (see for instance [Fu95 ]), but to our knowledge no paper presents a systematic overview of the distinguishability measures for quantum states from a cryptographer’s point of view. In the second place, the bounds (inequalities) presented in Section 6 are useful, especially those that bound the Shannon distinguishability. The third contribution is the definition of exponential indistinguishability for quantum states, as explained two paragraphs earlier.

The structure of the chapter is as follows. In the following section we discuss probability distributions, mainly to introduce the setting and the notation to be used later. Section 3 discusses density matrices and measurements, showing how they lead to probability distributions as well. In Section 4 we discuss four measures of distinguishability, first classically, then quantumly. After a short summary in Section 5, we discuss several inequalities, again both classically and quantumly. In Section 7 these inequalities are applied to proving a theorem about exponential indistinguishability. Section 8 discusses an application.

3.2 Probability distributions

Let X_{0} be a stochastic variable over the finite set X, then we can define p_{0}(x) =^{def} Prob[X_{0} = x], so X_{0} induces a probability distribution p_{0} over X. Let p_{1} be defined likewise. Of course, ∑_{x∈X} p_{t}(x) = 1 for t=0, 1. After relabeling the outcomes x_{1}, x_{2}, x_{3}, … x_{m} to 1, 2, 3, … m we get:

x=1 x=2 x=3 … x=m
X_{0} π_{0} = \frac{1}{2} p_{0}(1) p_{0}(2) p_{0}(3) … p_{0}(m)
X_{1} π_{1} = \frac{1}{2} p_{1}(1) p_{1}(2) p_{1}(3) … p_{1}(m)

Here π_{0} and π_{1} are the a priori probabilities of the two stochastic variables; they sum up to 1. Throughout this chapter π_{0} = π_{1} = \frac{1}{2}. Even though much of what will be said could be extended to the case π_{0} ≠ π_{1} ≠ \frac{1}{2}, it seems not relevant to the questions addressed here. Two distributions are equivalent (i.e. perfectly indistinguishable) if p_{0}(x) = p_{1}(x) for all x ∈ X, and they are orthogonal (i.e. maximally distinguishable) if there exists no x for which both p_{0}(x) and p_{1}(x) are non-zero.

Observe that p_{t}(x) denotes the conditional probability that X=x given that T =t, written as Prob[X=x|T =t]. So the joint probability is half that value: Prob[X=x∧ T =t] = Prob[T =t] Prob[X=x|T =t] = π_{t}p_{t}(x) = \frac{1}{2}p_{t}(x).

The following definitions and simple observations will be useful later on. We define the conditional probability r_{t}(x) := Prob[T =t|X=x], and the probability that X=x regardless of t, that is, p(x) := Prob[X=x]. Using Bayes’ Theorem we get:

r_{t}(x) = Prob[T =t|X=x]
= Prob[T =t] Prob[X=x|T =t]/Prob[X=x]
= \frac{1}{2}p_{t}(x)/p(x)

Observe that r_{0}(x) + r_{1}(x) = 1 for all x. Using p(x) and r_{t}(x) we can represent the situation also in the following way:

x=1 x=2 x=3 … x=m
X  p(1) p(2) p(3) … p(m)
X_{0} π_{0} = \frac{1}{2} r_{0}(1) r_{0}(2) r_{0}(3) … r_{0}(m)
X_{1} π_{1} = \frac{1}{2} r_{1}(1) r_{1}(2) r_{1}(3) … r_{1}(m)

3.3 Density matrices and measurements

Recall that a quantum state is said to be in a pure state if there exists a measurement that can confirm this fact with probability 1. Pure states can be represented by vectors in an N-dimensional Hilbert space, i.e. a vector space with inner product. In this chapter N is finite. Now consider the following preparation: A flips a fair coin, and depending on the outcome sends one of two different pure states |ψ_{0}⟩ or |ψ_{1}⟩ to B. Then the “pureness” of the quantum states is “diluted” by the classical uncertainty about the resulting coin flip. In this case no deterministic measurement exists, and the quantum state is said to be in a mixed state.

How do we deal with mixed states mathematically? Instead of using a vector |ψ⟩ to represent a pure state, we use the operator which projects onto the subspace spanned by |ψ⟩. In bra-ket notation this operator is written as |ψ⟩⟨ψ|. For a mixed state we construct a new operator by taking the sum of the projection operators, weighted according to their probabilities. The result is called a density matrix or density operator. It reflects B’s knowledge about the state of the system, that is, his best prediction about any measurement results.

Example: Consider the case where A prepares either a horizontally or a vertically polarized photon. We choose a basis such that |H⟩ = \binom{1}{0} and |V⟩ = \binom{0}{1}. Then A’s preparation is perceived by B as the mixed state

\frac{1}{2}|H⟩⟨H|+ \frac{1}{2}|V⟩⟨V| = \frac{1}{2} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} )+ \frac{1}{2} ( \begin{matrix}0 & 0 \\ 0 & 1 \end{matrix} ) = ( \begin{matrix}1/2 & 0 \\ 0 & 1/2 \end{matrix} ) , (3.1)

which is the “completely mixed state”.

Note that the same density matrix will be obtained if A prepares an equal mixture of left-polarized and right-polarized photons. In fact, in this twodimensional example any equal mixture of two orthogonal pure states will yield the same density matrix.

Density matrices are always Hermitian i.e. ρ = ρ^{†}. (The adjoint ρ^{†} of the matrix ρ is obtained by transposing ρ and taking the complex conjugate of all its entries.) This ensures that all the eigenvalues are real. To ensure that they are positive we require that ρ be positive, semi-definite (i.e. ⟨ψ|ρ|ψ⟩ ≥ 0 for all ψ ∈ H). Finally we require that the eigenvalues (i.e. the trace of ρ) sum up to 1. These conditions make a probability interpretation of equation (3.3) below meaningful.

3.1 Definition (see for instance [Su86 , Is95 , Pe93 ]) A density matrix ρ is an N×N matrix which has trace 1, which is Hermitian and which is positive, semi-definite.

Any source of quantum samples (that is, an imaginary Alice who indefinitely prepares quantum states in a prescribed way) is called an ensemble, which can be viewed as the quantum counterpart of a stochastic variable. A density matrix describes B’s knowledge about the quantum state of a sample completely; two different ensembles (i.e. two different preparations) with the same density matrices are indistinguishable as far as B is concerned. There exists no measurement that will allow B to distinguish between these two ensembles.

However, the fact that a density matrix describes the a priori knowledge of B implies that additional classical information can change the density matrix, even when no measurement is performed and the state remains untouched. Two typical cases are (1) when A reveals information about the way she prepared the state(s) to B, or (2) when A and B share entanglement (epr particles, for instance), and A sends the results of the measurements she performed to B. Observe that, consequently, a density matrix is subjective in the sense that it depends on what B knows.

Example (continued): (1) Suppose that, after A has sent an equal mixture of |H⟩ and |V⟩, she reveals to B that for that particular sample she prepared |V⟩. Then B’s density matrix suddenly changes from

( \begin{matrix}1/2 & 0 \\ 0 & 1/2 \end{matrix} ) to ( \begin{matrix}0 & 0 \\ 0 & 1 \end{matrix} ) .  (3.2)

(2) An identical change happens in the following situation: A prepares an epr pair whose combined state is written as

|Ψ^{−}⟩ = \frac{1}{\sqrt{2}}(|H⟩|V⟩ − |V⟩|H⟩),

known as the singlet state, and sends one of the particles to B. If A and B measure both particles using the same basis, their measurement outcomes will always be anti-correlated. So if A after measuring finds that her particle is horizontally polarized (|H⟩) and if she tells this to B, then B’s density matrix changes according to (3.2).

As an aside, it is interesting to remark that people disagree about whether the density matrix should be regarded as the state of the system or not, depending on the interpretation of quantum mechanics they adhere to. Consider for instance the situation before B has received the additional classical information to be sent by A. What is the state of his system? A pragmatist will answer that the state is simply described by B’s density matrix, whereas a realist will argue that the state actually is different (maybe known by A or by God) and that B is merely ignorant of this. For discussion on this topic see for instance [Is95 , Me96 ]. Here we will leave this philosophical question whether this is really the state or not unanswered, but adhere to the pragmatic approach, which seems more relevant from an informationtheoretical point of view.

Now let us describe how to compute the probability of a certain measurement result from a density matrix. Mathematically speaking a density matrix ρ can be regarded as an object to which we can apply another operator E_{x}. Taking the trace of the product yields the probability that the measurement result is x given that the state was ρ, i.e. Prob[result=x|state=ρ] = Tr(ρE_{x}). Here the x serves as a label, connecting the operator E_{x} and the outcome x, but it has no specific, physical meaning.

This formula explains the name ‘density matrix’ or ‘density operator’: one has to apply another operator (corresponding to the measurement) and take the trace in order to obtain a density function (wave function), which is the equivalent of a probability distribution in the continuous case. Note that ‘matrix’ and ‘operator’ are freely interchanged, which is justified as long as it is understood that all operators are linear.

A measurement is the application of not just one operator, but of a collection (ordered set) of operators.

3.2 Definition (see [Pe93 ]) Let E = ⟨E_{1}, …, E_{m}⟩ be a collection (ordered set) of operators such that (1) all E_{x} are positive semi-definite operators, and (2) ∑_{x} E_{x} = Id. Such a collection specifies a Positive Operator-Valued Measure (povm ).

Applying a povm to a system whose state is described by a density matrix ρ results in a probability distribution according to:

Prob[result = x|state = ρ] = Tr(ρE_{x})  (3.3)

where x ranges from 1 to m.

As an alternative name for a povm one also sees Probability Operator Measure. It is a postulate of quantum mechanics that any measurement can be described by a povm , though it is not always clear that each povm can indeed be experimentally realized. The set of all possible measurements, i.e. povm s, is denoted by M.

Warning: The way measurements are defined in this chapter is not standard; indeed, many physicists are not familiar with this approach. In the usual approach, as developed by von Neumann, a measurement is defined as an Hermitian operator, and the eigenvalues of this operator correspond to the measurement results. However, both approaches can be proven equivalent using the spectral decomposition theorem [Is95 ].

A Projection Valued Measurement (pvm) (corresponding to what is usually called a von Neumann measurement) is a special case of a povm : if we add the requirement that E_{x}E_{y} = δ(x, y)E_{x} (with δ(x, y)=1 if x=y and 0 otherwise—i.e. the Kronecker-delta), then the operators E_{x} are necessarily projections. Note that for povm s the E_{x} do not necessarily commute. Though pvm’s are better known, they sometimes yield less information than povm s. (On the other hand it has been shown that each povm is equivalent to a pvm in a larger Hilbert space by adding a system in a known state, see [Pe93 ] for discussion.)

Example: Measuring whether a photon is polarized according to angle α or to α + π/2 is done by the povm

\{( \begin{matrix}c^{2} & cs \\ cs & s^{2} \end{matrix} ) , ( \begin{matrix}s^{2} & −cs \\ −cs & c^{2} \end{matrix} )\} ,

where c = cos α and s = sin α. This is a pvm. When applied to a photon known to be in state |H⟩, for instance, this results in the probability distribution ⟨c^{2}, s^{2}⟩, using equation (3.3). An example of a povm which is not a pvm is the symmetric three-outcome ‘trine’ povm

\{\frac{2}{3} ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) , \frac{2}{3} ( \begin{matrix}γ^{2} & γσ \\ γσ & σ^{2} \end{matrix} ) , \frac{2}{3} ( \begin{matrix}γ^{2} & −γσ \\ −γσ & σ^{2} \end{matrix} )\} ,

where γ = cos(π/3) = − cos(2π/3) = \frac{1}{2} and σ = sin(π/3) = sin(2π/3) =

\frac{1}{2} \sqrt{3}. This simplifies to

\{( \begin{matrix}\frac{2}{3} & 0 \\ 0 & 0 \end{matrix} ) , ( \begin{matrix}\frac{1}{6} & \sqrt[\frac{1}{6}]{3} \\ \sqrt[\frac{1}{6}]{3} & \frac{1}{2} \end{matrix} ) , ( \begin{matrix}\frac{1}{6} & −\frac{1}{6} \sqrt{3} \\ −\frac{1}{6} \sqrt{3} & \frac{1}{2} \end{matrix} )\} .

Applying this povm to the state |V⟩ results in the probability distribution ⟨0, \frac{1}{2}, \frac{1}{2}⟩, again according to (3.3).

We have just seen that a measurement (a povm ) applied to a density matrix results in a probability distribution. Suppose now we have two density matrices defined over the same Hilbert space. Then we find ourselves back in the (classical) situation described in the previous section: comparing two probability distributions over the same outcome space X. In particular, let ρ_{0}, ρ_{1} be two density matrices, and let E = {E_{1}, …, E_{m}} again denote a povm . Let p_{0}(E) denote the probability distribution obtained by performing the povm E on a system in state ρ_{0} according to equation (3.3); let p_{1}(E) be defined likewise. Then we have:

x=1  x=2  x=3  … x=m
p_{0}(E) π_{0} Tr(ρ_{0}E_{1}) Tr(ρ_{0}E_{2}) Tr(ρ_{0}E_{3}) … Tr(ρ_{0}E_{m})
p_{1}(E) π_{1} Tr(ρ_{1}E_{1}) Tr(ρ_{1}E_{2}) Tr(ρ_{1}E_{3}) … Tr(ρ_{1}E_{m})

As before, π_{0} and π_{1} denote the a priori probabilities and are assumed to equal \frac{1}{2}.

3.4 Measures of distinguishability

This section discusses four different definitions of distinguishability, for probability distributions and for density matrices. Note that being able to distinguish between distributions, that is, between alternative hypotheses, is an important and well-studied problem with a vast literature. It goes under the name of classification, discrimination or feature evaluation, and has applications like speech recognition and radar detection. For a general overview, consult [Be82 ]. The problem studied here is a special case, in the sense that we want to distinguish between only two discrete probability distributions which have equal a priori probabilities. However, for the quantum case these probability distributions are determined by the choice of the measurement, thus optimization over all povm s is required. In the following subsections the classical measure of distinguishability is discussed first, followed by its quantum counterpart.

3.4.1 Probability of error

Consider the following experimental situation in which B is asked to distinguish between two stochastic variables, as follows. First A provides him with one sample, x, chosen from either X_{0} or X_{1} with equal probability. Then B’s task is to guess which of the two stochastic variables the sample came from, X_{0} or X_{1}. Clearly, the average probability that B makes the right guess serves as a measure of distinguishability between the two probability distributions p_{0} and p_{1} induced by X_{0} and X_{1} respectively.

It is well known that B’s optimal strategy is to look at the a posteriori probabilities: given the sample x his best choice is the t for which r_{t}(x) is maximal (see the representation at the end of Section 3.2). This strategy is known as Bayes’ strategy. So the average probability of successfully identifying the distribution now equals ∑_{x∈X} p(x) max\{r_{0}(x), r_{1}(x)\} = \frac{1}{2} ∑_{x∈X} max\{p_{0}(x), p_{1}(x)\}. Conversely, we can also express the probability that B fails.

3.3 Definition The probability of error between two probability distributions is defined by

PE(p_{0}, p_{1}) =^{def} \frac{1}{2} ∑_{x∈X} min\{p_{0}(x), p_{1}(x)\}  (3.4)

Two identical distributions have PE = \frac{1}{2}, and two orthogonal distributions have PE = 0.

Warning: PE does not act as a distance: when two distributions are close to one another, PE is not close to 0, but close to \frac{1}{2}.

In the quantum model, the experimental set-up is almost identical. Again A has two ensembles, one according to ρ_{0}, the other one according to ρ_{1}. She provides B with a quantum sample chosen from one of the two ensembles with equal probability. Again B must guess from which ensemble the sample came: ρ_{0} or ρ_{1}. And again, the Bayesian strategy of optimizing the a posteriori probabilities is optimal. However, in the quantum model B has an extra degree of freedom: he can choose the measurement he applies to his sample. Clearly, B’s probability of successfully distinguishing ρ_{0} from ρ_{1} depends on the measurement he performs; he would like to choose the measurement that minimizes his probability of error. So we define:

3.4 Definition The probability oferror betweentwodensitymatrices ρ_{0} and ρ_{1} is defined by

PE(ρ_{0}, ρ_{1}) =^{def} min_{E∈M} PE(p_{0}(E), p_{1}(E)),  (3.5)

where the povm E ranges over the set of all possible measurements M.

The question of finding an explicit formula for the optimal povm in this definition was first studied by Helstrom [He76 , pp. 106–108]. He shows that the povm E^{∗} that minimizes PE(p_{0}(E), p_{1}(E)) is actually a pvm. Knowing the optimal povm , the probability of error can be expressed explicitly. The expression he gives is,

PE (ρ_{0}, ρ_{1}) = \frac{1}{2} + \frac{1}{2} ∑_{λ_{j}≤0} λ_{j} ,  (3.6)

where the λ_{j} denote the eigenvalues of the matrix Γ = ρ_{0} − ρ_{1}.

This expression can be cleaned up a little in the following way. Consider the function f(x) = \frac{1}{2}(x − |x|). It vanishes when x ≥ 0 and is the identity function otherwise. Thus, with its use, we can expand the summation in Eq. (3.6) to be over all the eigenvalues of Γ:

PE (ρ_{0}, ρ_{1}) = \frac{1}{2} + \frac{1}{2} ∑_{j=1}^{N} f(λ_{j})
= \frac{1}{2} + \frac{1}{4}TrΓ − \frac{1}{4} ∑_{j=1}^{N} |λ_{j}|
= \frac{1}{2} − \frac{1}{4}Tr|Γ| .

Hence we have the following proposition:

3.5 Proposition Given two arbitrary density matrices ρ_{0} and ρ_{1}, the probability of error equals

PE(ρ_{0}, ρ_{1}) = \frac{1}{2} − \frac{1}{4} ∑_{j=1}^{N} |λ_{j}| = \frac{1}{2} − \frac{1}{4}Tr|ρ_{0} − ρ_{1}|,  (3.7)

where the λ_{j} are the eigenvalues of ρ_{0} − ρ_{1}.

PE (ρ_{0}, ρ_{1}) is therefore just a simple function of the distance between ρ_{0} and ρ_{1}, when measured as the trace norm of their difference.

3.4.2 Kolmogorov distance

Among cryptographers another measure of distinguishability between probability distributions is often used.

3.6 Definition The Kolmogorovdistance between two probability distributions is defined by

K(p_{0}, p_{1}) =^{def} \frac{1}{2} ∑_{x∈X} |p_{0}(x) − p_{1}(x)|.  (3.8)

Two identical distributions have K=0, and two orthogonal distributions have K=1.

In some references the factor \frac{1}{2} plays no role, and it is often left out, yet in other references an extra factor \frac{1}{2} is included. Here we left it in because we wanted a value between 0 and 1.

Probability of error and Kolmogorov distance are closely related.

3.7 Proposition

PE(p_{0}, p_{1}) = \frac{1}{2} − \frac{1}{2}K(p_{0}, p_{1})  (3.9)

This fact is not very difficult to prove, see [To72 ]. The most important step is to split the sum over X in two disjoint sub-sums, one for which p_{0}(x) < p_{1}(x), and one for which p_{0}(x) ≥ p_{1}(x).

In the quantum scenario we will optimize again over all possible measurements. But here this means that we have to find the povm that maximizes the Kolmogorov distance.

3.8 Definition The Kolmogorov distance betweentwo density matrices ρ_{0} and ρ_{1} is defined by

K(ρ_{0}, ρ_{1}) =^{def} max_{E∈M} K(p_{0}(E), p_{1}(E)),  (3.10)

where the povm E ranges over the set of all possible measurements M.

The relation between probability of error and Kolmogorov distance (eq. 3.9) shows that the two measurements that optimize PE and K are necessarily identical: the measurement E^{∗} minimizes PE(p_{0}(E), p_{1}(E)) = \frac{1}{2} − \frac{1}{2}K(p_{0}(E), p_{1}(E)) if and only if E^{∗} maximizes K(p_{0}(E), p_{1}(E)). See also the appendix of [Fu96 ]. Combining equations (3.7) and (3.9) we get:

3.9 Proposition The Kolmogorov distance between two density matrices ρ_{0} and ρ_{1} equals

K(ρ_{0}, ρ_{1}) = \frac{1}{2}Tr|ρ_{0} − ρ_{1}|,  (3.11)

where the λ_{j} are the eigenvalues of ρ_{0} − ρ_{1}.

Observe that Tr|ρ_{0} − ρ_{1}| is known as the trace norm on operators [RS72, Or96 ], so K has the additional property of satisfying the triangle inequality. The trace norm appears to be of unique significance within the class of all norms because of its connection to probability of error.

3.4.3 Bhattacharyya coefficient

Another distinguishability measure was defined in the 1940s because in some (continuous) cases the exact probability of error is difficult to evaluate exactly. See [Ka67 , To71 , To72 ].

3.10 Definition The Bhattacharyya coefficientbetweentwoprobability distributions p_{0} and p_{1} is defined by

B(p_{0}, p_{1}) = ∑_{x∈X} \sqrt{p_{0}(x)p_{1}(x)}  (3.12)

Two identical distributions have B = 1, whereas two orthogonal distributions have B = 0.

Warning: B does not act as a distance: when two distributions are close to one another, B is not close to 0, but close to 1. In some papers this is remedied by taking arccos(B) or − ln(B).

No simple operational definition for the Bhattacharyya coefficient seems to exist. However, geometrically it is related to the angle between p_{0} and p_{1}, interpreted as vectors in the m-dimensional real space. A similar relation exists in the quantum model, as we will see shortly.

For the quantum model, we can now define a distinguishability measure by minimizing over all measurements possible.

3.11 Definition The Bhattacharyya coefficient betweentwodensitymatrices ρ_{0} and ρ_{1} is defined by

B(ρ_{0}, ρ_{1}) =^{def} min_{E∈M} B(p_{0}(E), p_{1}(E)),  (3.13)

where the povm E ranges over the set of all possible measurements M.

Surprisingly, it turns out that B is equivalent to another measure, studied by Wootters [Wo81 ] and Jozsa [Jo94 ], among others. Suppose |ψ_{0}⟩ and |ψ_{1}⟩ are pure states. When we think of these two state vectors geometrically, a natural notion of distinguishability is the angle between |ψ_{0}⟩ and |ψ_{1}⟩, or any simple function of this angle. In particular, using the formula |⟨ψ_{0}|ψ_{1}⟩| = |ψ_{0}||ψ_{1}| cos α and recalling that state vectors are usually normalized, we can define overlap(|ψ_{0}⟩, |ψ_{1}⟩) := |⟨ψ_{0}|ψ_{1}⟩| as a measure of distinguishability. The question is: what to do for mixed states?

The answer was given by Uhlmann [Uh76 ] and simplified by Jozsa [Jo94 ]. If ρ_{0} is the density matrix of a mixed state in the Hilbert space H_{1}, then we can always extend the Hilbert space such that ρ_{0} becomes a pure state in the combined Hilbert space H_{1} ⊗ H_{2}. More precisely, we can always find an extension H_{2} of H_{1} and a pure state |φ_{0}⟩ ∈ H_{1} ⊗ H_{2}, such that Tr_{2}(|φ_{0}⟩⟨φ_{0}|) = ρ_{0}. Here the operator Tr_{2} means to trace out H_{2}, the Hilbert space that was added, as explained in Subsection 4.3.3. When this condition holds, |φ_{0}⟩ is said to be a purification of ρ_{0}. Similarly, if |φ_{1}⟩ is the purification of ρ_{1}, we are back to a situation with two pure states, and we can apply the formula above, leading to the following definition.

3.12 Definition The (generalized) overlap between two density matrices is defined by

overlap(ρ_{0}, ρ_{1}) =^{def} max |⟨φ_{0}|φ_{1}⟩|,  (3.14)

where the maximum is taken over all purifications |φ_{0}⟩ and |φ_{1}⟩ of ρ_{0} and ρ_{1} respectively.

It can be shown [Uh76 ] [Jo94 ] that

overlap(ρ_{0}, ρ_{1}) = Tr (\sqrt{\sqrt{ρ_{0}}ρ_{1}\sqrt{ρ_{0}}}) ,  (3.15)

but for dimensions higher than 2 this formula is difficult to evaluate, unless the eigenvalues of ρ_{0} and ρ_{1} are known. However, overlap(ρ_{0}, ρ_{1}) has the nice property that it is multiplicative over tensor products:

overlap(ρ_{0} ⊗ ρ_{1}, ρ_{2} ⊗ ρ_{3}) = overlap(ρ_{0}, ρ_{2}) overlap(ρ_{1}, ρ_{3}).  (3.16)

The following proposition establishes the connection between the Bhattacharyya coefficient and the overlap.

3.13 Proposition (Fuchs and Caves [FC95]) Overlap is equivalent to the quantum Bhattacharyya coefficient:

overlap(ρ_{0}, ρ_{1}) = B(ρ_{0}, ρ_{1}).  (3.17)

Apart from the geometric interpretation of the overlap mentioned above, there also exists a physical interpretation for the square of this value. The following discussion is based on Jozsa’s work.

Consider again the situation in which A provides B with a quantum state according to ρ_{0} or ρ_{1}. Let us first suppose that both states are pure, so ρ_{0} = |ψ_{0}⟩⟨ψ_{0}| and ρ_{1} = |ψ_{1}⟩⟨ψ_{1}|. Define F (ρ_{0}, ρ_{1}) = (overlap(ρ_{0}, ρ_{1}))^{2}. There is an obvious physical interpretation of this quantity: it is the probability that a particle in state |ψ_{1}⟩ passes the test: “Are you yes/no in state |ψ_{0}⟩?” Von Neumann called this the transition probability. In a communication model, if we see |ψ_{0}⟩ as the input of a channel and |ψ_{1}⟩ as the output, we could call this the fidelity.

This interpretation can be extended to the case where ρ_{1} is mixed but ρ_{0} is still pure: F (ρ_{0}, ρ_{1}) = ⟨ψ_{0}|ρ_{1}|ψ_{0}⟩ is the probability that a particle in state ρ_{1} passes the test: “Are you yes/no in state ψ_{0}?” For the most general case, where ρ_{0} and ρ_{1} are both mixed, no physical interpretation seems to exist; nevertheless, F remains well-defined in this case and it is natural to continue to call it ‘fidelity’.

3.4.4 Shannon distinguishability

Now we come to the last, and maybe most important notion of distinguishability. Mutual information, as defined by Shannon [Sh48 ], can also be used as a distinguishability measure between probability distributions [Li56, Be82 ]. Recall that the (Shannon) entropy function H is defined as

H(X) =^{def} − ∑_{x∈X} Prob[X=x] lg Prob[X=x],  (3.18)

where lg denotes the logarithm function with base 2. The argument of H can be either a stochastic variable or a probability distribution. A special case is the function H_{2}(x), which is the entropy of the distribution ⟨x, 1 − x⟩.

Consider the following elementary example. Suppose we have two boxes, each containing colored balls. Let t ∈ T ={0, 1} denote a particular identity of one of the boxes, whereas T denotes the stochastic variable representing the identity of the box. Then Prob[T = t] is just what was called the a priori probability π_{t} in Section 3.2. Recall that in our case π_{0} = π_{1} = \frac{1}{2}, so H(T) = 1. Similarly, let X denote the stochastic variable corresponding to the color of the balls, regardless of the box it came from. Recall that Prob[X=x] was written as p(x).

Considering the same experiment as with the probability of error, in which A picks a ball from one of the two boxes and gives it to B, one can ask now: How much information does X (the color of a picked ball) convey about T (the identity of the box it came from)?

Information is defined as the reduction of uncertainty, where uncertainty is quantified using the Shannon entropy. Consider two quantities: (1) the average uncertainty of B about T before he was handed a sample (or ball); and (2) his average uncertainty about T after he was handed a sample. This difference expresses the amount of information gained through the experiment, and can also be used as a measure of distinguishability between two distributions. Thus we obtain:

average information = (average uncertainty about T) −

(average uncertainty about T when x is given)

= H(T) − H(T |X)
= H_{2}(\frac{1}{2}) − ∑_{x∈X} p(x) H(T |X = x)

= 1 − ∑_{x∈X} p(x) H_{2}(r_{0}(x))
= I(T; X).

This leads to the following definition:

3.14 Definition The Shannon distinguishability betweentwoprobability distributions p_{0} and p_{1} is defined by:

SD(p_{0}, p_{1}) =^{def} I(T; X).  (3.19)

Shannon distinguishability can also be applied in the quantum scenario: find the measurement that optimizes the Shannon distinguishability of the two distributions obtained when applying the same measurement to two different quantum states.

3.15 Definition The Shannon distinguishability between two density matrices ρ_{0} and ρ_{1} is defined as

SD(ρ_{0}, ρ_{1}) =^{def} max_{E∈M} SD(p_{0}(E), p_{1}(E)),  (3.20)

where the povm E ranges over the set of all possible measurements M.

There is an unfortunate problem for this measure of distinguishability: calculating the value SD(ρ_{0}, ρ_{1}) is generally a difficult problem. Apart from a few special cases, no explicit formula for SD solely in terms of ρ_{0} and ρ_{1} is known. Even stronger than that: no such formula can exist in the general case [FC94]. This follows from the fact that optimizing the Shannon distinguishability requires the solution of a transcendental equation. (See also [Pe93 ] and [Mo97 ] for a discussion of other aspects of SD.)

3.5 Overview

The material presented in the previous four subsections can be summarized in the following table.

classical  optimization quantum
definition  p_{0} = p_{1} p_{0}⊥p_{1} criterion expression
pe \frac{1}{2} ∑ min\{p_{0}(x), p_{1}(x)\}  1/2  0  min  \frac{1}{2} − \frac{1}{4}Tr|ρ_{0} − ρ_{1}|
k \frac{1}{2} ∑ |p_{0}(x) − p_{1}(x)|  0  1  max  \frac{1}{2}Tr|ρ_{0} − ρ_{1}|
b ∑(p_{0}(x)p_{1}(x))^{1/2}  1  0  min  overlap(ρ_{0}, ρ_{1})
sd via I(X; T)  0  1  max  does not exist

Table 3.1: Classical and quantum notions of indistinguishability.

3.6 Inequalities

We have seen already (equation (3.9)) that probability of error and Kolmogorov distance are related through the equality:

PE(p_{0}, p_{1}) = \frac{1}{2} − \frac{1}{2}K(p_{0}, p_{1})  (3.21)

The other pairs of distinguishability measures are related through inequalities which can be found in various places in the literature [Ka67 , HR70, To71 , To72 , Be82 ].

3.16 Proposition Let p_{0} and p_{1} be probability distributions. The following relations hold:

1 − B(p_{0}, p_{1}) ≤ K(p_{0}, p_{1}) ≤ \sqrt{1 − B(p_{0}, p_{1})^{2}}  (3.22)
1 − H_{2}(PE(p_{0}, p_{1})) ≤ SD(p_{0}, p_{1}) ≤ 1 − 2PE(p_{0}, p_{1}).  (3.23)
1 − B(p_{0}, p_{1}) ≤ SD(p_{0}, p_{1}) ≤ 1 − H_{2}(\frac{1}{2} − \frac{1}{2} \sqrt{1 − B(p_{0}, p_{1})})  (3.24)

Before giving a proof of this proposition, we would like to state its quantum equivalent.

3.17 Theorem Proposition 3.16 can be generalized to the quantum scenario: one can substitute PE, K, B and SD and use density matrices ρ_{0} and ρ_{1} as operands.

Alternatively, using the quantum expressions, equations (3.22), (3.23) and (3.24) can be expressed in the following, equivalent form:

1 − overlap(ρ_{0}, ρ_{1}) ≤ \frac{1}{2}Tr|ρ_{0} − ρ_{1}| ≤ \sqrt{1 − overlap(ρ_{0}, ρ_{1})^{2}}  (3.25)
1 − H_{2}(\frac{1}{2} − \frac{1}{4}Tr|ρ_{0} − ρ_{1}|) ≤ SD(ρ_{0}, ρ_{1}) ≤ \frac{1}{2}Tr|ρ_{0} − ρ_{1}|.  (3.26)
1 − overlap(ρ_{0}, ρ_{1}) ≤ SD(ρ_{0}, ρ_{1}) ≤ 1 − H_{2}(\frac{1}{2} − \frac{1}{2} \sqrt{1 − overlap(ρ_{0}, ρ_{1})}) (3.27)

The importance of this theorem is that, while the Shannon distinguishability itself may sometimes be difficult to calculate exactly, the inequalities provide a way to bound it. We will use this in the next section.

Proof of proposition 3.16: We will start with proving (3.22). We start with the left inequality:

1 − B(p_{0}, p_{1}) = \frac{1}{2} (∑_{x∈X} p_{0}(x) + ∑_{x∈X} p_{1}(x) − 2 ∑_{x∈X} \sqrt{p_{0}(x)p_{1}(x)})
= \frac{1}{2} ∑_{x∈X} (|\sqrt{p_{0}(x)} − \sqrt{p_{1}(x)}|)^{2}
≤ \frac{1}{2} ∑_{x∈X} |p_{0}(x) − p_{1}(x)|
= K(p_{0}, p_{1})

The inequality in the penultimate transition is valid for each term individually: |\sqrt{a}−\sqrt{b}| ≤ \sqrt{a}+\sqrt{b} because of the triangle inequality. Taking the absolute value on the right does not change the expression; now multiply both sides by |\sqrt{a} − \sqrt{b}|.

We need the Schwarz inequality, (∑_{x∈X} c(x)d(x))^{2} ≤ (∑_{x∈X} c(x)^{2})(∑_{x∈X} d(x)^{2}), for the right inequality of (3.22), where c and d are vectors in the m-dimensional real vector space. Define the coordinates as c(x) = |\sqrt{p_{0}(x)} − \sqrt{p_{1}(x)}| and d(x) = |\sqrt{p_{0}(x)} + \sqrt{p_{1}(x)}|. Then we find that

K(p_{0}, p_{1})^{2} = \frac{1}{4} (∑_{x∈X} |p_{0}(x) − p_{1}(x)|)^{2}
= \frac{1}{4} (∑_{x∈X} |\sqrt{p_{0}(x)} − \sqrt{p_{1}(x)}||\sqrt{p_{0}(x)} + \sqrt{p_{1}(x)}|)^{2}

≤ \frac{1}{4} (∑_{x∈X} |\sqrt{p_{0}(x)} − \sqrt{p_{1}(x)}|)^{2} (∑_{x∈X} |\sqrt{p_{0}(x)} + \sqrt{p_{1}(x)}|)^{2}
= \frac{1}{4} (∑_{x∈X} p_{0}(x) + p_{1}(x) − 2\sqrt{p_{0}(x)p_{1}(x)}) (∑_{x∈X} p_{0}(x) + p_{1}(x) + 2\sqrt{p_{0}(x)p_{1}(x)})
= \frac{1}{4}(2 − 2B(p_{0}, p_{1}))(2 + 2B(p_{0}, p_{1}))
= 1 − B(p_{0}, p_{1})^{2}

In order to prove the left inequality in (3.23) we observe that this is a special case of Fano’s inequality (see for instance [CT91]):

H(T |X) ≤ H_{2}(PE(p_{0}, p_{1})) + PE(p_{0}, p_{1}) log(#T − 1).

Recall from Subsection 3.4.4 that the cardinality of T , denoted as #T , equals 2. One could also use Jensen’s inequality.

For the right inequality of (3.23) we expand I(X; T) as H(T) − H(T |X) to obtain an inequality between SD and PE (see also [HR70]). Recalling the definitions of r_{t}(x) and p(x), observing that r_{1}(x) = 1 − r_{0}(x) and that 2 min{r, 1 − r} ≤ H_{2}(r) for all r between 0 and 1 (see Figure 3.1), we obtain:

SD(p_{0}, p_{1}) = 1 − ∑_{x∈X} p(x) H_{2}(r_{0}(x))
≤ 1 − ∑_{x∈X} p(x) · 2 min{r_{0}(x), 1 − r_{0}(x)}
≤ 1 − 2PE(p_{0}, p_{1}).

The left hand inequality of (3.24) is obtained in a very similar way, using that H_{2}(r) ≤ 2\sqrt{r(1 − r)} (see Figure 3.1):

SD(p_{0}, p_{1}) = 1 − ∑_{x∈X} p(x) H_{2}(r_{0}(x))
≥ 1 − ∑_{x∈X} p(x) · 2\sqrt{r_{0}(x)(1 − r_{0}(x))}
= 1 − ∑_{x∈X} \sqrt{p_{0}(x)p_{1}(x)}
= 1 − B(p_{0}, p_{1}).

Figure 3.1: 2 min\{x, 1 − x\} ≤ H_{2}(x) ≤ 2(x(1 − x))^{\frac{1}{2}} . (Formally this is proven by looking at the first and second derivatives.)

For the right hand side of (3.24) we define the function

g(r) := \frac{1}{2} − \frac{1}{2} \sqrt{1 − r^{2}}.  (3.28)

If we let h(r) = 2\sqrt{r(1 − r)} for 0 ≤ r ≤ 1, then we get that h(r) = h(1 − r), that gh(r) = min{r, 1 − r}, and that hg(r) = r. So H_{2}(r_{0}(x)) = H_{2}(min{r_{0}(x), 1 − r_{0}(x)}) = H_{2}(gh(r_{0}(x))), and

SD(p_{0}, p_{1}) = 1 − ∑_{x∈X} p(x) H_{2}(r_{0}(x))
= 1 − ∑_{x∈X} p(x) H_{2}(g( h(r_{0}(x)) ))
≤ 1 − H_{2}(g(∑_{x∈X} p(x)h(r_{0}(x))))
= 1 − H_{2}(g(B(p_{0}, p_{1})))
= 1 − H_{2}(\frac{1}{2} − \frac{1}{2} \sqrt{1 − (B(p_{0}, p_{1}))^{2}})

Here we used Jensen’s inequality on the (composite) function H_{2}(g(r)); this function is convex. This concludes the proof of Proposition 3.16.□

Proof of theorem 3.17: First we prove equation (3.25). We start with the first inequality. Let E_{B}^{∗} denote a povm which optimizes B; define E_{K}^{∗} likewise.

1 − B(ρ_{0}, ρ_{1}) = 1 − B(p_{0}(E_{B}^{∗}), p_{1}(E_{B}^{∗}))
≤ K(p_{0}(E_{B}^{∗}), p_{1}(E_{B}^{∗}))
≤ K(p_{0}(E_{K}^{∗}), p_{1}(E_{K}^{∗}))
= K(ρ_{0}, ρ_{1})

The second inequality of (3.25) follows from

K(ρ_{0}, ρ_{1}) = K(p_{0}(E_{K}^{∗}), p_{1}(E_{K}^{∗}))
≤ \sqrt{1 − B(p_{0}(E_{K}^{∗}), p_{1}(E_{K}^{∗}))^{2}}
≤ \sqrt{1 − B(p_{0}(E_{B}^{∗}), p_{1}(E_{B}^{∗}))^{2}}
= \sqrt{1 − B(ρ_{0}, ρ_{1})^{2}}

Equations (3.26) and (3.27) are proven in a similar way. In particular, in (3.25) the function on the extreme left, f(x) = 1 − x, and on the extreme right, f(x) = \sqrt{1 − x^{2}} are monotonously decreasing. In addition, B must be minimized whereas K must be maximized. The same is true for (3.26) and (3.27). □

3.7 Exponential indistinguishability

As already described in the Introduction, when designing cryptographic protocols, we often actually define a family of protocols parameterized by a security parameter n (for instance denoting the length of some string, the number of rounds, or the number of photons). Typically we require that the probability of cheating for each participant vanishes exponentially fast, i.e. is of the order O(ε^{−n}), with ε between 0 and 1. For instance, one technique is to compare the protocol implementation, which is usually a family of protocols parameterized by n, with an ideal protocol specification, and to prove that these two become exponentially indistinguishable [Be91b ].

3.18 Definition Let {X_{0}} = ⟨X_{0}^{(1)}, X_{0}^{(2)}, X_{0}^{(3)} …⟩ denote a family of stochastic variables with corresponding distributions ⟨p_{0}^{(1)}, p_{0}^{(2)}, p_{0}^{(3)} …⟩. Let {X_{1}} be defined similarly. Then {X_{0}} and {X_{1}} are exponentially indistinguishable if there exists an n_{0} and an ε between 0 and 1 such that

∀n ≥ n_{0} : K(p_{0}^{(n)}, p_{1}^{(n)}) ≤ ε^{n}

Examples can be constructed easily. For instance, let X_{0}^{n} be uniformly distributed over {0, 1}^{n} (the set of strings of length n), i.e. for each x ∈ {0, 1}^{n} we have p_{0}^{(n)}(x) = 2^{−n}. This defines the family of uniform distributions {X_{0}}. We define {X_{1}} identically, except that p_{1}^{(n)}(0^{n}) = 0, while p_{1}^{(n)}(1^{n}) = 2^{−n+1}. So 0^{n}, the word with all zeroes, has zero probability, and 1^{n}, the word with all ones, has double the probability. Clearly the two families {X_{0}} and {X_{1}} are exponentially indistinguishable.

The reader should be aware that in computational cryptography more refined notions of distinguishability have been defined [GMR89 ]. In polynomial indistinguishability it is only required that the families converge as fast as 1/n^{k}, for any k > 0. Though we will not be arguing this formally, it is not hard to see that the proof of the Lemma below also applies for polynomially indistinguishable families. Yet another refinement is computational indistinguishability: the sample is given to a polynomial time Turing machine which outputs a 0 or 1. We look at the Kolmogorov distance of the possible outputs while maximizing over all polynomial time Turing Machines, and require that this converges as 1/n^{k} for any k > 0. Computational indistinguishability turned out to be extremely powerful for defining notions such as pseudo-random number generators [Ya82b ] and zero knowledge protocols [GMR89 ], but is of no concern here. All three notions have in common that a distinguisher who is restricted to polynomial time, and who is given a sample of either source, will not be able to tell the identity of the source.

Here we followed the computational-cryptographic tradition of defining exponential indistinguishability using the Kolmogorov distance. This choice, however, is in no way crucial, since the next lemma shows that we could have taken any of the four distinguishability measures. In other words K, PE, B and SD turn out to be equivalent when we require exponentially fast convergence. There is a small technicality here: indistinguishable distributions have PE = \frac{1}{2} and B = 1, so exponential indistinguishability means convergence to those values, instead of convergence to 0, as is the case with K and SD.

3.19 Lemma Let {X_{0}} and {X_{1}} be two families of stochastic variables which are exponentially indistinguishable with respect to one of the distinguishability measures K, PE, B, SD. Then {X_{0}} and {X_{1}} are exponentially indistinguishable with respect to each of K, PE, B, SD.

Proof: The equivalence between exponential indistinguishability for PE and K follows from equation (3.9), whereas the other equivalences are derived using equations (3.22) through (3.24).

For instance, to prove that exponential indistinguishability for K implies exponential indistinguishability for B would go as follows. Suppose

[∃n_{0}, ε][∀n ≥ n_{0}] : K(p_{0}^{(n)}, p_{1}^{(n)}) ≤ ε^{n}.  (3.29)

Using the left hand side of equation (3.22) it follows that 1 − B(p_{0}^{(n)}, p_{1}^{(n)}) ≤ ε^{n}.

For the reverse direction: if 1 − B(p_{0}^{(n)}, p_{1}^{(n)}) ≤ ε^{n} then

1 − (B(p_{0}^{(n)}, p_{1}^{(n)}))^{2} ≤ ε^{n}(1 + B(p_{0}^{(n)}, p_{1}^{(n)})) ≤ 2ε^{n},  (3.30)

so K(p_{0}^{(n)}, p_{1}^{(n)}) ≤ \sqrt{2}\sqrt{ε}^{n} using the right hand side of equation (3.22). If we choose ε̄ < \sqrt{ε} and n̄_{0} > n_{0} such that \sqrt{2} < (ε̄/\sqrt{ε})n̄_{0}, then K(p_{0}^{(n)}, p_{1}^{(n)}) ≤ ε̄^{n} for n ≥ n̄.

The other implications are proven in a similar way. As far as H_{2}(x) is concerned, it is sufficient to recall (see fig. 3.1) that

2 min\{x, 1 − x\} ≤ H_{2}(x) ≤ 2\sqrt{x(1 − x)}  (3.31)

This concludes the proof. □

The obvious next step is to define exponential indistinguishability for density matrices, and to show that the choice of the distinguishability measure is immaterial.

3.20 Definition Let {ρ_{0}^{(n)}} = ⟨ρ_{0}^{(1)}, ρ_{0}^{(2)}, ρ_{0}^{(3)} …⟩ denote a familyof density matrices defined over the Hilbert spaces H^{(1)}, H^{(2)}, H^{(3)} … Let {ρ_{1}^{(n)}} be defined similarly. Then {ρ_{0}^{(n)}} and {ρ_{1}^{(n)}} are exponentially indistinguishable if there exists an n_{0} and an ε between 0 and 1 such that

∀n ≥ n_{0} : K(ρ_{0}^{(n)}, ρ_{1}^{(n)}) ≤ ε^{n}

An example will be presented in the next section. But first let us end this section with the quantum analogue of Lemma 3.19.

3.21 Theorem Let {ρ_{0}^{(n)}} and {ρ_{1}^{(n)}} be two families of density matrices which are exponentially indistinguishable with respect to one of the distinguishability measures K, PE, B, SD. Then {ρ_{0}^{(n)}} and {ρ_{1}^{(n)}} are exponentially indistinguishable with respect to each of K, PE, B, SD.

Proof: This follows now immediately from the proof of Lemma 3.19 using Theorem 3.17. □

3.8 Applications

Let us now look at an application of the quantum-exponential indistinguishability idea. In particular, we look at the problem of the parity bit in quantum key distribution as studied in [BMS96 ] (henceforth called bms). Let |ψ_{0}⟩ = \binom{cos α}{sin α} and |ψ_{1}⟩ = \binom{cos α}{− sin α}, and let ρ_{0} and ρ_{1} be the corresponding density matrices. The bits 0 and 1 are represented by ρ_{0} and ρ_{1} Likewise, the bit string z = z_{1}z_{2} … z_{n} is represented by n different photons, the ith photon being in state ρ_{i}. Thus the combined state for the string z is given by

ρ_{z} = ρ_{z_{1}} ⊗ ρ_{z_{2}} ⊗ ⋯ ⊗ ρ_{z_{n}}  (3.32)

where ⊗ stands for the tensor product.

Now let Z_{0}^{(n)} denote all the strings of length n with even parity (i.e. with overall exclusive-or equal to 0) and Z_{1}^{(n)} all strings of length n with odd parity. Then define

ρ_{j}^{(n)} = \frac{1}{2^{n−1}} ∑_{z∈Z_{j}^{(n)}} ρ_{z}  (3.33)

for j = 0, 1. In bms these two density matrices are explicitly calculated in order to compute their Shannon distinguishability as a function of n and α, for 0 ≤ α < π/4. This is extremely important because the parity bit appears in the proof of security of the BB84 key exchange protocol [BB84].

Here we compute the distance between ρ_{0}^{(n)} and ρ_{1}^{(n)} in terms of Kolmogorov distance and overlap. And for the special case n = 2 we will study the inequalities obtained in Theorem 3.16, just as an illustration to see how good these bounds are. Observe that, at this point in time, the problem of the parity bit is one of the few nontrivial examples in which Shannon distinguishability, Kolmogorov distance (and related, probability of error) and overlap can be computed, yet the optimal povm s are known to be different. For the next few paragraphs the reader is advised to consult bms, or to take (3.34), (3.41) and (3.42) for granted.

First let us calculate the Kolmogorov distance K(ρ_{0}^{(n)}, ρ_{1}^{(n)}) as a function of n and α. In bms it is shown that Δ^{(n)} =^{def} \frac{1}{2}(ρ_{0}^{(n)} −ρ_{1}^{(n)}) has non-zero entries on the secondary diagonal only. Moreover, it is not difficult to see that all these entries equal c^{n}s^{n}, where c = cos α, s = sin α. Therefore Δ^{(n)} has 2^{n−1} eigenvalues equal to −c^{n}s^{n}, and 2^{n−1} eigenvalues equal to +c^{n}s^{n}, so

K(ρ_{0}^{(n)}, ρ_{1}^{(n)}) = ∑ |λ_{j}| = (2cs)^{n} = (sin 2α)^{n} = S^{n},  (3.34)

where S = sin 2α. Obviously, {ρ_{0}^{(n)}} and {ρ_{1}^{(n)}} are exponentially indistinguishable.

Computing the overlap between ρ_{0}^{(n)} and ρ_{1}^{(n)} is more elaborate. For the discussion in this section we will denote the overlap as B and define it through equation (3.15):

B(ρ_{0}, ρ_{1}) := Tr (\sqrt{\sqrt{ρ_{0}}ρ_{1}\sqrt{ρ_{0}}})  (3.35)

This is justified because of Proposition 3.13. In bms equation (19) it is shown that ρ_{0}^{(n)} and ρ_{1}^{(n)} are block-diagonal, with 2 × 2 blocks. If σ is of the form

( \begin{matrix}[σ^{u}] & ( \begin{matrix}0 & 0 \\ 0 & 0 \end{matrix} ) \\ ( \begin{matrix}0 & 0 \\ 0 & 0 \end{matrix} ) & [σ^{l}] \end{matrix} )  (3.36)

we will write this as σ = σ^{u} ⊕ σ^{l}. It is not difficult to see that the following three equalities now hold:

Tr(σ^{u} ⊕ σ^{l}) = Tr(σ^{u}) + Tr(σ^{l})
(σ_{0}^{u} ⊕ σ_{0}^{l})(σ_{1}^{u} ⊕ σ_{1}^{l}) = σ_{0}^{u}σ_{1}^{u} ⊕ σ_{0}^{u}σ_{1}^{u}
\sqrt{(σ^{u} ⊕ σ^{l})} = \sqrt{(σ^{u})} ⊕ \sqrt{(σ^{l})}

From this it follows that

Tr (\sqrt{\sqrt{σ_{0}}σ_{1}\sqrt{σ_{0}}}) = Tr (\sqrt{\sqrt{σ_{0}^{u}}σ_{1}^{u}\sqrt{σ_{0}^{u}}}) + Tr (\sqrt{\sqrt{σ_{0}^{l}}σ_{1}^{l}\sqrt{σ_{0}^{l}}}) (3.37)

which we rewrite as

B(σ_{0}, σ_{1}) = B(σ_{0}^{u}, σ_{1}^{u}) + B(σ_{0}^{l}, σ_{1}^{l}).  (3.38)

This means that we can evaluate B by evaluating each block individually according to (3.35) and sum up the results. Note that the operands on the right are not normalized, i.e. their trace does not equal 1.

Again according to bms eq. (20) (but slightly changing notation) each block is of the form

σ_{0}^{(n,k)} = ( \begin{matrix}u^{2} & uv \\ uv & v^{2} \end{matrix} ) for even parity; σ_{1}^{(n,k)} = ( \begin{matrix}u^{2} & −uv \\ −uv & v^{2} \end{matrix} ) for odd parity,

(3.39)

with u = c^{n−k}s^{k}, v = c^{k}s^{n−k}. So in fact these density matrices represent pure states, \binom{u}{v} and \binom{u}{−v}, and the formula for B reduces to taking the inner product. We find that

B(σ_{0}^{(n,k)}, σ_{1}^{(n,k)}) = c^{2(n−k)}s^{2k} − c^{2k}s^{2(n−k)}.  (3.40)

Summing up over all blocks of ρ_{i}^{(n)} we get

B(ρ_{0}^{(n)}, ρ_{1}^{(n)}) = ∑_{k=0}^{⌊(n−1)/2⌋} \binom{n}{k}B(σ_{0}^{(n,k)}, σ_{1}^{(n,k)})
= ∑_{k=0}^{(n−1)/2} \binom{n}{k}(c^{2(n−k)}s^{2k} − c^{2k}s^{2(n−k)}),

for n odd. For n even we find the same expression: even though for k = n/2 there are only \frac{1}{2} \binom{n}{k} blocks, their contribution is zero since B(σ_{0}^{(n,k)}, σ_{1}^{(n,k)}) = 0 in this case. For the case n = 2 this expression reduces to

B(ρ_{0}^{(2)}, ρ_{1}^{(2)}) = c^{4} − s^{4} = (c^{2} − s^{2})(c^{2} + s^{2}) = C,  (3.41)

where C = cos 2α.

For the Shannon distinguishability in the special case n = 2 bms eq. (44) gives

SD(ρ_{0}^{(2)}, ρ_{1}^{(2)}) = \frac{1}{2}(1 + C^{2})H_{2} (1 − \frac{C^{2}}{1 + C^{2}} ) + \frac{S^{2}}{2} .  (3.42)

Now we are in a position to substitute (3.34), (3.41) and (3.42) into equations (3.25), (3.26) and (3.27). Observe that (3.25) is easily seen to hold, in fact with equality holding on the right hand side. Equations (3.26) and (3.27) are illustrated in Figures 3.2 and 3.3. The horizontal axis represents the angle α between |ψ_{i}⟩ and \binom{1}{0}, meaning that for π/4 (≈ 0.785) the states |ψ_{0}⟩ and |ψ_{1}⟩ are orthogonal. The fact that the bounds using overlap seem tighter might be explained by the fact that the function 2\sqrt{x(1 − x)} resembles H_{2}(x) fairly well.

3.9 Conclusion

We have presented four measures of distinguishability for density matrices, shown their relation to classical measures of distinguishability for probability distributions, thus obtaining several inequalities and the generalized notion of exponential indistinguishability. The latter will be useful in the next chapter. The preceding presentation somewhat sidesteps the issue of the exact measurements involved, partially to make this work more accessible to non-physicists. Interesting questions are, for instance, under which conditions the measurements that optimize PE , B and SD are identical, or under what conditions equality holds in the inequalities presented. Such questions are still subject of ongoing research.

Figure 3.2: Equation 3.26 for the parity bit with n = 2 and with α ∈ [0, π/4] on the horizontal axis.

Figure 3.3: Equation 3.27 for the parity bit with n = 2 and with α ∈ [0, π/4] on the horizontal axis.

A model for quantum protocols

Quantum particles: the dreams that stuff is made of. David Moser

In this final chapter we present our model for two party quantum protocols, and a definition of security. We restrict ourselves to protocol tasks with classical input and output only, and describe how two quantum computers can execute a protocol using a quantum channel.

We discuss in detail the differences between classical and quantum information: the fact that quantum information cannot be copied and the physical principle that prevents us from extracting any classical information from a quantum system without disturbing its state. And despite the fact that classical information can be seen as a special case of quantum information, we show that from a cryptographic point of view the two types of information must be kept separated.

For the formal model we use Quantum Turing Machines for the parties and describe the quantum channel by means of a quantum communication tape. We define the output, view and profile of a quantum protocol, and use a quantum interface (simulator) to compare the security of two protocols.

After the formal definition of security we present strong evidence that the classical technique known as rewinding is impossible in quantum protocols.

4.1 Introduction

In Chapter 2 we have presented a classical definition of security, whereas in Chapter 3 we defined exponential indistinguishability for quantum states. In this chapter we extend the definition of security to quantum protocols, i.e. to protocols whose task specification remains classical, but in which the participants communicate through a quantum channel. The idea is simple; we take the definition as presented in Section 2.2 and see what happens when we replace the classical Turing Machines by two Quantum Turing Machines who communicate through a quantum tape. Chapter 3 provides us with the right notion of exponential indistinguishability.

Despite the fact that there are many papers on quantum cryptography, no formal definition has been presented so far. A protocol model was presented by Yao [Ya95 ] and was adapted by Mayers [Ma97 ] and Lo and Chau [LC97a , LC97b ]. However, the explanations and justification for the underlying assumption was either brief or imprecise, and sometimes difficult to comprehend for someone without a proper physical background.

Here we examine the model from the point of view of a cryptographer with a strong interest, but not necessarily a strong background in quantum physics. In particular we give the intuition behind some of the quantum phenomena, and try to determine the physical principles responsible for them. Therefore, the first part of this chapter will be somewhat informal.

First we introduce briefly qubits and quantum circuits. In Section 3 we discuss in detail how a quantum computer can emulate classical computation, including measurements. Subsequently, in Section 4, we describe informally how two parties can communicate through a quantum channel. There we also discuss the fundamental difference between classical and quantum information, and the implication this has for the view of the adversary. In Section 5 we present the formal model, based on Quantum Turing Machines, and the definition of security. Section 6 discusses rewinding of the adversary.

4.2 Qubits and unitary transformations

The qubit is the basic unit of quantum information, as the bit is for classical information. In quantum mechanics the state of a (discrete) system is represented by a unit vector in an N-dimensional Hilbert space over the field of complex numbers, and a state thus representable is called a pure state. In this formalism it is natural to represent the mutually exclusive bits 0 and 1 as orthogonal vectors |0⟩ and |1⟩, which together span a 2-dimensional Hilbert space. The superposition principle states that any state |ψ⟩ which is a linear superposition of |0⟩ and |1⟩ and which has norm 1 is itself also a pure state. Consequently, a qubit is a variable which can attain any value

|ψ⟩ = α|0⟩ + β|1⟩,  (4.1)

with α, β ∈ ℂ and |α|^{2} + |β|^{2} = 1. We say that a qubit is in state |ψ⟩, while α and β are called the amplitudes.

For concreteness it may be useful to think of photon polarization as an implementation of a qubit, but most people do not think any more of bits in terms of On/Off, voltage levels or magnetization directions. Moreover, photons may not be the most convenient medium to store qubits; for this purpose ion traps are probably more practical. In any case, here we will not be concerned with implementation issues; nevertheless we will sometimes talk about a qubit as if it where a particle.

Any pure state of a collection of n qubits can be described by a vector in an Ndimensional Hilbert space H, when N = 2^{n}. The N basis vectors can conveniently be labeled by the set of strings of length n; so each

|b_{1}...b_{n}⟩ = ⨂_{i=1}^{n} |b_{i}⟩

represents a basis vector, where b_{i} ∈ {0, 1} and where ⊗ stands for tensor product. From the superposition principle it follows that a state like |Ψ^{−}⟩ = \frac{1}{\sqrt{2}}(|01⟩ − |10⟩) is also a pure state. There is no way we can write |Ψ^{−}⟩ as a product of pure states of two individual qubits, i.e. as (α_{1}|0⟩ + β_{1}|1⟩) ⊗ (α_{2}|0⟩ + β_{2}|1⟩).

According to quantum mechanics any state evolution of a discrete system is described by a unitary transformation. A unitary transformation U is a linear operator on H which has an inverse and which preserves scalar products, i.e.

⟨Uψ|Uφ⟩ = ⟨ψ|φ⟩  (4.2)

From these two conditions it can be shown that UU^{†} = U^{†}U = Id, where U^{†} is obtained by transposing the matrix representing U and taking the complex conjugate of all its entries. This condition can serve as an alternative characterization of a unitary transformation. Intuitively, a unitary operator is the analogue of a rotation in ℝ^{N}; in particular, it is equivalent to choosing another basis.

As an example, consider the following unitary transformation on two qubits, defined by the image of each basis vector under U:

|00⟩ → |00⟩
|01⟩ → |01⟩
|10⟩ → |11⟩
|11⟩ → |10⟩.

This operation is called the XOR, because |ab⟩ ⟶ |a (a ⊕ b)⟩. Observe that U shows its ‘xoring’ behavior only if the input states correspond to the classical states |0⟩ or |1⟩, but otherwise any intuition is likely to fail. For instance, in the {|0⟩, |1⟩} basis the role of |a⟩ and |b⟩ (i.e. the first and second qubits) is not symmetric: only |b⟩ is affected whereas |a⟩ is preserved. For this reason this operation is also called controlled-not: a controls whether b is inverted or not. But surprisingly, in the Hadamard basis \{\frac{1}{\sqrt{2}}(|0⟩ + |1⟩), \frac{1}{\sqrt{2}}(|0⟩ − |1⟩)\} the roles of |a⟩ and |b⟩ are reversed. To see that XORis indeed unitary, it is sufficient to write it as a matrix in the basis |00⟩, |01⟩, |10⟩, |11⟩ and one obtains:

XOR= ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix} )  (4.3)

The XOR is one of the simplest quantum operations, and is also referred to as an XOR gate; people use it as a building block to design quantum circuits. Several alternative gates have been defined; most notably the Toffoli gate T. This is 3-qubit gate, also called the controlled-controlled-not because

|abc⟩ \underrightarrow{T} |ab ((a ∧ b) ⊕ c)⟩.

So c is inverted only if a=b=1.

By using the ‘constants’ |0⟩ and |1⟩ as input values, a Toffoli gate T allows us to do various operations on one qubit, like Not, XORor Fanout, and on two qubits, like And and Swap. We will give the Fanout explicitly, because it is of significant importance later on. Let d be either |0⟩ or |1⟩. Then |d10⟩ \underrightarrow{T} |d1d⟩. This Fanout works only when the input qubit d ∈ {|0⟩, |1⟩}, i.e. when the input qubit is known to represent a classical value. The Fanout does not work for an arbitrary qubit state |ψ⟩, so there is no contradiction with the no-cloning theorem for quantum states, which we will explain in Section 4.4.3. For more details about gates, see for instance [St97 ].

4.3 Emulating classical computation and measure-

ments by a quantum computer

Classical information and quantum information are quite different, and it seems that a general model of quantum computation has to deal with two types of information.

This, however, is not very convenient; it is much more desirable to have one type of information to deal with. In the next subsection we will show that any probabilistic computation can be emulated by a quantum computer.

In addition, we have to deal with measurements. It is a priori not clear what effects measurements during the computation have, whether a party gains or loses computational power by switching back and forth between classical and quantum information. Most textbooks about quantum mechanics present two possible kinds of transformations on the state of a quantum system: (1) unitary transformation, which are reversible, and (2) measurements (usually described as projection operators), which are not reversible. From this, one could easily come to the conclusion that measurements are irreversible, and therefore cannot be emulated by a (reversible) quantum computer. To show that a quantum computer can emulate any measurement is the subject of Subsection 4.3.2.

In this section we discuss emulating classical computation. The quantum computer is not yet explicitly defined, it can be thought of as a quantum circuit, a Quantum Turing Machine (to be introduced in Section 4.5.1), or any collection of unitary transformations on a register of qubits. We will return to emulating classical communication in a cryptographic protocol in Section 4.4.1. Most of the observations in this section are not new, but we believe it is worth discussing them thoroughly, in particular since we want to extend these type of arguments.

4.3.1 Deterministic and random bits

A party who wants to represent classical bits by means of qubits can simply use orthogonal states, say |0⟩ and |1⟩, to encode 0 and 1. We have seen this already before when we discussed quantum gates. Obviously, if a qubit is known to contain a classical bit and the basis is known, then the original value can always be retrieved by a measurement in this basis.

To obtain a random bit with a quantum computer a quantum coin flip is executed (also referred to as a role of a quantum die). One takes a qubit known to be in state |0⟩ (or |1⟩), and applies the unitary operator

QCF = ( \begin{matrix}\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{−1}{\sqrt{2}} \end{matrix} ) .  (4.4)

Then a measurement in the {|0⟩, |1⟩} basis is performed, resulting in either 0 or 1 with equal probability.

In the next subsection we will see that one can emulate the measurement and postpone the actual measurement until the end. So the measurement result will be a qubit |b⟩ instead of a classical bit b. The quantum computer evaluates all possible execution paths in superposition until the end of the computation, when the measurement is performed. From all possible executions now one is ‘chosen’, according to the proper probability distribution.

Observe that this has the somewhat counterintuitive consequence that all randomness has disappeared from the computation itself: the state evolution is fully deterministic, the probabilistic aspect comes from the measurement at the end.

4.3.2 Measurements

Nobody seems to understand precisely what exactly happens during a measurement, and the subject is often debated upon. However, this is beside the point here. The crucial observation is that, in some sense, any measurement can be considered as being reversible (unitary). This is exactly the point of view we take here, because it shows us that a quantum computer can emulate any measurement.

In Chapter 3, where we used the povm formalism to describe measurements, we put the boundary between the classical and the quantum world between the observed system and the measurement apparatus. In other words, the measurement apparatus was completely factored out in the mathematical formalism used. Here we do the opposite: we consider the measurement apparatus as part of the quantum system as well. Then any measurement can be reformulated as an interaction between

|ψ⟩^{|φ⟩}  U_{M}

Figure 4.1: A measurement M of a system in state |ψ⟩ interpreted as an interaction U_{M} with an auxiliary system in a known state |φ⟩.

quantum system and measurement apparatus, described by a unitary transformation on both systems combined.

Let us give an example. Suppose that a qubit in state |ψ⟩ = α|0⟩+β|1⟩ is measured according to the {|0⟩, |1⟩} basis (see Figure 4.1). Let |φ⟩ be the initial state of the measurement apparatus, and let U_{M} denote the unitary transformation corresponding to the measurement M, i.e. the unitary transformation that ‘xors’ information about the observed system (here the qubit) into the measurement apparatus. Then the state evolution of the ‘measurement’ can be described by

|ψ⟩|φ⟩ ⟶^{U_{M}} α|0⟩|φ_{0}⟩ + β|1⟩|φ_{1}⟩.  (4.5)

How is the resulting state to be interpreted? Suppose that a ‘real’ measurement would occur, then we would argue as follows: if, after suitable amplification of its state, the measurement apparatus indicates that its state is |φ_{0}⟩, then we would deduce that the qubit was in state |0⟩. This happens with probability |α|^{2}. And with probability |β|^{2} the opposite happens: the measurement apparatus is found to be in state |φ_{1}⟩, indicating that the qubit was in state |1⟩. So we find that after the measurement interaction the states of the qubit and the measurement apparatus are correlated: |φ′⟩ = |φ_{b}⟩⇔|ψ′⟩ = |b⟩. This correlation is called entanglement.

The previous description was just to explain how the state could be interpreted.

However, we are in no way forced to assume that a ‘real’ measurement actually has occurred. To put it differently, any quantum computer can emulate the evolution U_{M} described above: the measurement apparatus is simply regarded as a part of the quantum computer itself. And in this extended model the emulated measurement U_{M} can be undone (reversed): just apply U_{M}^{−1}. Note that in this section we are not interested in actually undoing the measurement, we only want to convince ourselves that the evolution is unitary. However, we will return to this point in Section 4.6 when discussing rewinding.

The preceding description of a measurement using entanglement was already given by Schrödinger in 1935 [Sc35 , section 10], in the same paper in which he introduced his cat. This was several months after Einstein, Podolsky and Rosen’s paper [EPR35 ]. See also [Sv97 ] for some helpful discussion.

Talking about epr : it is interesting to elaborate on the previous discussion. The observation is the following: a quantum computer that emulates the measurement does not need the whole measurement apparatus to store |φ_{0}⟩ or |φ_{1}⟩. It suffices to take only one qubit since the subspace spanned by the (orthogonal) states |φ_{0}⟩ and |φ_{1}⟩ is of dimension two. So it becomes logical to write |φ_{b}⟩ := |b⟩. If we now set the initial state |φ⟩ of this ‘measurement’ qubit to |0⟩ we get

(α|0⟩ + β|1⟩)|0⟩ = α|00⟩ + β|10⟩ ⟶^{U_{M}} α|00⟩ + β|11⟩,  (4.6)

which is exactly the evolution of the XOR. The resulting state is entangled, not unlike the state |Ψ^{−}⟩ often used in epr ‘paradoxes’.

However, in the remainder of the computation both qubits play quite a different role. The ‘measured’ qubit continues to play a role in the quantum computation, and it can interact with other qubits. The ‘measurement’ qubit, on the other hand, is preciously kept isolated in memory until the computation has completed. Then it will be measured according to the same bases that would have been used if the measurement had been performed immediately, the {|0⟩, |1⟩} basis. It is clear that this does not change the probability distribution of the measurement results. Consequently, during the emulation nothing is changed if parties do not perform their measurements immediately. Instead, they can keep the information in quantum memory and measure it (make it classical) at a later stage, without changing any probability distribution on the results. Note that a measurement in an arbitrary basis can be described by a unitary operation (implementing the change of basis) followed by a measurement in {|0⟩, |1⟩} basis.

We have almost accomplished what we want: we can emulate deterministic and random bits and we can emulate each conceivable measurement. The only issue remaining is the if statement, where the condition is a measurement outcome, and the actions are unitary operators. Let |φ′⟩ ∈ H_{1} be the result of a measurement, and suppose we want to implement: if |φ′⟩ = |0⟩ then U_{0} else U_{1}, where U_{0} and U_{1} act on H_{2}. It is not difficult to see that there exists a unitary transformation U_{if} on H_{1} ⊗ H_{2} which has the same effect as this if statement.

The overall conclusion is that no computational power is lost or gained by emulating measurements. On the other hand, we obtain a uniform description using unitary transformations and quantum information (qubits) only, while all measurements are performed at the end.

4.3.3 Partial knowledge about entangled systems

The previous discussion about entanglement provides a good starting point to explain a mathematical technique, called tracing out.

Suppose A has a qubit in state α|0⟩ + β|1⟩, while B has a qubit in state |0⟩. Suppose they jointly apply the XORto their two qubits, then they separate again. The overall state of both qubits together evolves as in equation (4.6), resulting in |Φ⟩ = α|00⟩+ β|11⟩. This describes perfectly the overall state of both qubits, but what do we know about the state of A’s individual qubit? Or rather, what does A know about the state of her qubit?

It follows from the earlier discussion that with probability |α|^{2} A’s qubit is in state |0⟩, and with probability |β|^{2} in state |1⟩; and the same is true for B. This was easy to see in this particular case. But in the general case, how do we calculate the partial knowledge a party has about an entangled system when not all the particles are in his hands?

The general strategy is to use density matrices (see Section 3.3) to describe the combined state, and then to trace out. The density matrix describing the state |Φ⟩ is

|Φ⟩⟨Φ| = ( \begin{matrix}a & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & b \end{matrix} ) ,  (4.7)

where a = |α|^{2} and b = |β|^{2}. Labeling the rows and columns by the strings 00, 01, 10 and 11, each entry of this matrix can be represented by d_{ij,kl}, with i, j, k, l ∈ {0, 1}.

Let E be the matrix obtained by A after tracing out B’s Hilbert space. The entries of E are defined by e_{i,k} = Tr(D_{i,k}), where

D_{i,k} = ( \begin{matrix}d_{i0,k0} & d_{i1,k0} \\ d_{i0,k1} & d_{i1,k1} \end{matrix} )  (4.8)

In the example

E = Tr_{B}|Φ⟩⟨Φ| = ( \begin{matrix}a & 0 \\ 0 & b \end{matrix} ) ,  (4.9)

exactly reflecting that with probability |α|^{2} A’s qubit is in state |0⟩, and with probability |β|^{2} in state |1⟩.

Similarly, we can trace out A’s Hilbert space by interchanging the roles of i and k with the roles of j and l. In this particular example A and B obtain the same result after tracing out, but that need not be true generally. Note that some entries (like d_{00,01}) are lost in the process, so tracing out always implies a loss of information, unless the two qubits are not entangled. Tracing out is easily generalized to any tensor product of two vector spaces of finite dimension.

4.4 Quantum protocols informally

In this chapter our purpose is to describe a general model for quantum protocols and security. Before presenting a formal definition in the next section, we will discuss some important issues first in an informal way.

4.4.1 The quantum channel

We assume that A and B each have a quantum computer, and that they communicate through a quantum channel. What the latter precisely means is actually not very clear. For instance, we could say that they communicate by exchanging some quantum particles, but a particle can be in a superposition of being sent and not being sent. This is not so far-fetched as it may seem; it is possible to design quantum protocols using half-silvered mirrors, resulting in photons being in superposition of going through and being reflected. Nevertheless, it can be shown that this example as well can be modeled by using qubits.

We assume that A and B each have a private collection of qubits, on which they can do some unitary transformations, and that they share some quantum channel. This could be, for instance, a register of qubits which they modify in turns, or a collection of particles they send back and forth. In the QTM formalism it will be a communication tape they can both access.

Described more formally: A has her Hilbert space H^{A}, likewise B has his Hilbert space H^{B}, while their shared Hilbert space, the quantum channel, is denoted H^{C}. During step j, party P applies the transformation U_{j}^{P}|ψ⟩, with |ψ⟩ ∈ H^{P} ⊗ H^{C}.

Suppose A wants to send quantum information to B. She applies the unitary transformation U on her qubits and the shared qubits, defined by U^{A}(|ψ^{A}⟩ ⊗ |ψ^{C}⟩). Generally this means that A’s qubits will become entangled with those of the channel. Then it becomes B’s turn: he applies a unitary transformation U^{B}(|ψ^{C}⟩ ⊗ |ψ^{B}⟩) to the shared qubits and his own, and the qubits of A, B and C end up being all entangled. Note that, in some intuitive sense, the unitary transformation applied by A and B correspond to reading and writing simultaneously.

This description seems sufficient to model any kind of quantum communication between A and B. However, is the model complete? One restriction is clear: we have restricted ourselves to discrete phenomena. This means that we cover only physical phenomena which, if measured, can give a finite number of (mutually exclusive) outcomes. Examples are: electron spin, photon polarization, energy levels of an atom. Continuous phenomena are excluded; an example would be electron position. Measurements here give a continuum of results, like “the electron is observed at position x”. Defining a qubit in the context of a continuous phenomenon does not seem meaningful.

It is a postulate (i.e. an assumption about how reality can be described) of quantum mechanics that the pure state of every conceivable discrete quantum phenomenon can be described by a vector in an N-dimensional Hilbert space, and ⌈lg N⌉ qubits are sufficient to provide an equivalent description. In particular, this implies that any kind of (discrete) quantum phenomenon, even those that are yet to be discovered, can be described using this mathematical formalism, so in this respect the model is complete.

4.4.2 Dealing with classical information

In many proposed quantum protocols only part of the communication is sent through a quantum channel. Often a significant amount of communication is sent through a (reliable) classical channel. Thus it seems that we are dealing with two different types of information: classical and quantum. Measurements can be seen as a process that converts quantum information to classical information. A priori it seems necessary that any model for quantum protocols should describe classical and quantum information separately, and that A and B use two channels: one classical and one quantum.

On the other hand, we saw in the previous section that classical computation and measurements can be emulated by a quantum computer, so why not do the same for two quantum computers communicating through a quantum channel? Even though some physicists would not hesitate long and accept these statements without much doubt, it is not so clear from the onset, especially since security issues are involved. Cryptographers simply have to be extremely careful about the models they use for proving security. The next few subsections will show that this care is justified.

4.4.3 Information and disturbance

The most striking difference between classical and quantum information is that the former can be copied, whereas the latter cannot. Even though quantum information can be transferred onto another quantum system (through a unitary transformation or teleportation), it is impossible to gain classical information about the quantum state without changing the state. Let us examine this crucial difference in more detail.

Consider a qubit which is to be measured. The measurement apparatus can be interpreted as an auxiliary quantum system, and the measurement is a unitary transformation on the combined system. This situation is exactly as has been described before (Section 4.3.2), but the purpose is different: before we wanted to argue that measurements can be emulated by a quantum computer, whereas here we want to point out that any gain in classical information must imply a disturbance of the quantum state.

When subjected to a (complete) von Neumann measurement, the qubit is asked “Are you in state |0⟩ or in |1⟩?” This measurement yields one bit of classical information (0 or 1, with probability |α|^{2} resp. |β|^{2}) which is maximal. The state is now fully disturbed: the initial state is lost, and the system has changed (‘collapsed’) to |0⟩ or |1⟩, in agreement with the result.

In particular we know that we cannot simultaneously learn the answer to the question “Are you in state |0′⟩ or in |1′⟩”, when

|0′⟩ = \frac{1}{\sqrt{2}}(|0⟩ + |1⟩)
|1′⟩ = \frac{1}{\sqrt{2}}(|0⟩ − |1⟩),

which is a conjugate basis. For instance, when this measurement is performed after the first one, its result is random. It seems obvious that we can extract only one classical bit of information from a qubit, and this fact is often attributed to the Heisenberg Uncertainty Principle, but the latter is not correct. In the first place, what is being referred to is not a new principle, but just a set of equations that follow from the theory. In addition, these relations do not say anything about making two conjugate measurements on the same particle at all: The Heisenberg Uncertainty Relations reflect a statistical statement about measurements on an ensemble of particles. For more discussion on this subject, see [Pe93 , page 93] [Is95 , page 126] [Fu96 , sect. 3].

Nature allows for a much more subtle kind of measurement than the measurement described above. There exist partial measurements, in which the state can disturbed a bit and in which only partial information about the state is obtained. The idea is simply to use a different U_{M} than the one describing complete measurements. Obviously, one extreme case is when no measurement takes place (U = Id): no information about the quantum state is obtained, and the state is not disturbed. All the possibilities between these two extremes exist. In Chapter 3 we discussed an alternative formalism to describe such measurements without explicitly having to deal with the auxiliary system, called povm s, but for the discussion here this formalism is less appropriate.

The fact that we must cause disturbance if we want to gain information, follows from a proposition, shown by Bennett, Brassard and Mermin.

4.1 Proposition ([BBM92 ]) Suppose M is a measurement that leaves two non-orthogonal states undisturbed. Then M cannot yield any information about which of these two states a given system is in.

Proof: Let again U_{M} be the unitary operator corresponding to M. Let |ψ_{a}⟩ and |ψ_{b}⟩ be non-orthogonal, so their inner product is non-zero. Let |φ⟩ be the state of the measuring system. A state evolution that disturbs neither |ψ_{a}⟩ nor |ψ_{b}⟩ would look like

|ψ_{a}⟩|φ⟩ ⟶^{U_{M}} |ψ_{a}⟩|φ_{a}⟩
|ψ_{b}⟩|φ⟩ ⟶^{U_{M}} |ψ_{b}⟩|φ_{b}⟩

But since U_{M} is unitary,

⟨ψ_{a}|ψ_{b}⟩⟨φ|φ⟩ = ⟨φψ_{a}|ψ_{b}φ⟩ = ⟨φ_{a}ψ_{a}|ψ_{b}φ_{b}⟩ = ⟨ψ_{a}|ψ_{b}⟩⟨φ_{a}|φ_{b}⟩  (4.10)

The first and the last equality are true because the inner product is multiplicative over the tensor product, and the middle equality is true because unitary transformations are inner product preserving. Consider the left-most and the right-most expression. Since ⟨φ|φ⟩ = 1 and ⟨ψ_{a}|ψ_{b}⟩ ≠ 0, we obtain that ⟨φ_{a}|φ_{b}⟩ = 1. Since |φ_{a}⟩ and |φ_{b}⟩ are normalized, it means that |φ_{a}⟩ = |φ_{b}⟩. So the final state after the measurement interaction is the same, regardless of the state the measured system had before. Consequently, M yields no information. □

It follows that cloning (i.e. creating two particles each in state |ψ⟩ from one particle in state |ψ⟩) of quantum states is impossible: if we could clone we could measure one particle to gain information, and keep the other. More direct proofs of the no cloning theorem show that the evolution |ψ⟩|φ_{0}⟩ → |ψ⟩|ψ⟩ (with |φ_{0}⟩ some fixed initial state of the auxiliary system) cannot be unitary for arbitrary states |ψ⟩ [WZ82, Pe93 ].

This information disturbance principle is the physical principle on which the security of Quantum Key Distribution is based. We do not want to discuss this protocol in full detail here, but it provides a good intuition of what information-causes-disturbance means. Moreover, it shows how an E attacking a quantum protocol gains information. As is shown in Figure 4.2, A and B communicate through a quantum channel that is being eavesdropped upon by E. They also have access to an unjammable classical broadcast channel.

A  B E^{ρ^{A}}^{σ}  ^{ρ^{B}}^{σ′} U^{E}

Figure 4.2: Quantum Key Distribution: E eavesdrops on the quantum channel between A and B. The final states are obtained after tracing out (see text).

E’s attack is modeled through a unitary transformation U^{E} that it applies to the particles sent through the quantum channel. From E’s point of view A’s initial state is mixed, expressed by the density matrix ρ^{A}. The auxiliary system used by E has initial state σ, and final state σ′, The latter is obtained by tracing out B’s particles:

σ′ = Tr_{B}(U^{E}(ρ_{A} ⊗ σ)(U^{E})^{†}).

The final state of B is obtained by tracing out E’s system.

The distance between σ and σ′ is a measure for the amount of ‘information’ E has gained. On the other hand, the distance between ρ^{A} and ρ^{B} is in indication for the amount of disturbance that U^{E} has caused; clearly, in the absence of E they are equal. Various reasonable notions of distance exist, this was exactly the subject of Chapter 3. The information disturbance principle now tells us that if E tries to gain information, this necessarily causes a disturbance in the transmission between A and B with overwhelming probability. This they will detect through their public discussion after the quantum transmission has taken place.

Quantifying the relation between the information E gains and the disturbance caused by the attack is generally not easy. In [FGGNP97 ] this problem is addressed for one qubit, using Shannon information (distinguishability) as the distance measure. A simple relation is derived for the information obtained by a partial measurement in the {|0⟩, |1⟩} basis, as a function of the disturbance this measurement causes in the conjugate {|0′⟩, |1′⟩} basis, and it is shown the sum of information gained and disturbance caused never exceeds one bit. A less rigorous derivation of this relation is found in [CG97], which also deals with the case for two qubits. For more than two qubits no general formulas concerning information and disturbance are known. For a more thorough exposition about the information disturbance principle the reader is referred to [Fu96 ].

4.4.4 Redefining the view

The different nature of quantum information has significant consequences for the model, in particular for the definition of the view. Look for instance at Figure 2.4 on page 24, and assume that A, B and E are quantum computers, and suppose that A is corrupted. This means that A gives all the qubits she receives immediately to E, and sends only qubits that it gave her. However, unlike in the classical case, E’s capability to look at the qubits it receives from A is severely restricted by the fact that if it looks, it will also cause a disturbance.

In general, from the discussion in the previous subsection it follows that parties cannot monitor a quantum channel without disturbing it. Copying the channel traffic and storing it for later reference is impossible. Consequently, the quantum view, i.e. the view that a party has of the quantum communication taking place in a protocol, is completely different from the classical view as defined in Section 2.2.2. To emphasize this point consider an elementary example: Suppose that A sends a qubit to B, and B does nothing to this qubit and sends it back. (In the context of a bigger protocol this could be one meaningful course of action among other possibilities). In this case no communication took place, and the view of B is empty (contains no information).

This may be somewhat puzzling, until we realize that A and B communicate only if “... physical acts of A have induced a desired physical state in B” [CT91]. Since no physical change in B’s system takes place, no communication has occurred. Here we are reminded of the fact that, even though we are used to model communication in a mathematical way, communication is intrinsically a physical process.

The example of Quantum Key Distribution (see Figure 4.2) illustrates in which way an adversary E can extract information from quantum interactions: knowing its own initial state and its own unitary evolution, P’s final state contains information about the states of the systems it interacted with. Therefore we define the quantum view of P as its final state. Recall that a quantum state is commonly represented as a density matrix, which can be regarded as a generalization of a stochastic variable (see Chapter 3).

It is very tempting to regard the classical view simply as a special case of the quantum view. This may seem evident from a physical point of view, but it is wrong from a cryptographic point of view. We cannot measure quantum information without disturbing the state, but for classical information this is not the case. If a party knows that some qubits represent classical bits which are encoded by sending orthogonal states, s/he can measure them and obtain the information therein contained without being caught, so it is logical to assume that s/he will do so. Therefore it is necessary to separate the classical and the quantum communication taking place in a protocol, and to define the classical view and the quantum view separately.

At this point there are two ways to proceed:

(a) We assume that A and B are connected through a classical channel and a quantum channel. The view of P (either A or B) is defined as the combination of the classical view (the concatenation of all classical bits sent and received by P) together with the final state ρ_{F}^{P} .

(b) We assume that A and B are connected through a quantum channel only. This quantum channel incorporates the classical channel, as follows:

(i) P sends a 0 or a 1 as |0⟩ or |1⟩.

(ii) For each classical bit that P receives s/he emulates a measurement ac-

cording to the {|0⟩, |1⟩} basis as described in Section 4.3.2. (iii) For each qubit that P sends or receives and which is known to represent a classical bit, P makes a copy of it which s/he stores away in quantum memory until the end of the protocol. (This can been done using the Fanout, for instance, so this copying of classical bits is certainly unitary.)

Both descriptions are clearly equivalent: if we represent the classical view obtained in (a) using qubits in state |0⟩ or |1⟩, then the combined view obtained in (a) must be equivalent to the quantum view obtained in (b). We choose option (b) because of its simplicity: we have only one type of information and measurements can be emulated as described before, so they can all be postponed until the end of the protocol. This is in agreement with the model used by Mayers [Ma97 ]. The only difference in the two scenarios is that in (a) the measurements (and the ‘collapses’) occur during the protocol, whereas in (b) the measurements are emulated and the collapse occurs at the end. As has been said in Section 4.3.2: the point of time of a measurement does not changed the probability distributions on its results.

There is another way to phrase that security is not affected in the transition from (a) to (b) [MS97]. Intuitively, an honest party can always (and should always) measure those bits sent to him which correspond to classical bits. So even though E can fancy itself that it is doing a quantum attack on the classical bits, all these bits will collapse to either |0⟩ or |1⟩. All possible entangled states E might have created also collapse as a result of the honest party’s measurement, and effectively E’s attack is equivalent to a (probabilistic) classical attack. It is possible to show this formally with the help of Definition 4.2, but in the end the argument does not differ much from the one given in the previous paragraph: as long as an honest participant measures (forces a ‘collapse’) classical bits, s/he is protected.

4.4.5 Comparison with other work

The first model for quantum protocols was presented by Yao [Ya95 ], who mentions that separating out the classical communication is useful. This model was adapted both by Mayers [Ma97 ] and by Lo and Chau [LC97a ] to prove that Quantum Bit Commitment is impossible.

The model introduced in [Ma97 ] addresses the issue of classical information, but without giving any explanation, which was provided by personal communication [MS97]. This issue is nowhere addressed in the works of Lo and Chau, but this is not problematic when they prove that qbc is impossible, for the following reason. Intuitively, the proof shows that for every quantum computer B there exists a local unitary transformation that a cheating A can perform, allowing her to open as a 0 or as a 1. But since the quantifier ranges over all B, this also includes the B’s that measure and copy all classical information as described in (b) in the previous subsection. In other words, Lo and Chau’s model is good enough for proving that qbc is impossible. But the argument that “classical communication is a special case of quantum communication and needs no further consideration” [LC97b ] seems incorrect for defining a general model of security for arbitrary quantum protocols.

4.4.6 Protocol tasks

In Chapter 2 we separated tasks (the ideal behavior of honest parties) from the ideal protocol (which included all possible dishonest behaviors). But we saw already that we can specify tasks which might not be implementable in practice; for instance, most implementations of bit commitment cannot prevent A from sending in a value that contains nonsense.

In the case of Quantum Bit Commitment things are even more dramatic. The flaw in the proof of [BCJL93 ] was the following. It was proven that A could not open both as a 0 and a 1 simultaneously. However, this overlooked a possibility that classically does not make sense, but quantumly does: what if A can open a 0 or a 1 at her choosing? Classically, if A opens and B sees a 0, then he can assume the 0 was there in the commit phase. But quantumly this isn’t true anymore: by clever use of entanglement A can create a state on her side which allows her to open as a 0 or a 1 as she pleases. Moreover, if she is never requested to open she is able to exploit this state, see [BCMS97 ]. Observe that this does not mean that our task specification for bc is flawed, but that in a purely quantum-mechanical model Bit Commitment does not exist.

Considering tasks which have qubits as input and output stretches the imagination even more. What does it mean to commit to a qubit? Does it mean that A gives a physical qubit to the trusted host, or a construction prescription? Certainly a trusted host cannot inspect a qubit given to him. And how to deal with entangled qubits?

For now we will leave these questions for what they are, and restrict ourselves to cryptographic tasks which are classical. That is, A’s and B’s inputs and outputs are classical, even though they use quantum computers and a quantum channel. Despite the negative results about qbc and its implications for other two-party quantum protocols [Lo97 ], our quest for a proper model and definition is not meaningless, since we can always make some extra assumption (see the end of Section 4.5.4).

4.5 Formal definitions

After all these preparatory discussions we are finally ready to present our definition of security for quantum protocols. We follow the same approach as in Section 2.2.2, making modifications when the different nature of quantum information forces us to. But first we present a formal model of computation.

4.5.1 The Quantum Turing Machine

In principle, quantum algorithms can conveniently be described using the formalism of quantum circuits, but no complexity measure seems well-established, at least at the time of writing. On the other hand, even though describing a quantum algorithm by means of a Quantum Turing Machine (QTM) can be tedious, there is a welldefined complexity class based on them. Moreover, since the classical definitions in Chapter 2 use probabilistic TMs, it will be easier to extend the definition using QTMs instead of quantum circuits.

Quantum Turing Machines were first considered by Deutsch [De85 ], and considerably improved by Bernstein and Vazirani [BV97]. We will very briefly summarize those points from their paper that we need here.

A deterministic TM can be defined as a triplet ⟨Γ, Q, δ⟩, where Γ is the alphabet with blank symbol ⊤, where Q is the set of states with initial state q_{0} and final state q_{f}, and where δ is the transition function: ⟨q, s⟩ ⟶^{δ} ⟨q′, s′, d⟩. This means that when the machine is in state q and reads an s on the tape, it will write s′, move the head in direction d ∈ {left, right}, and change to the state q′.

For a probabilistic TMone pair ⟨q, s⟩ can map to several triples ⟨q′, s′, d⟩; each triple is associated with a certain probability which all sum up to one. For a quantum TM one pair ⟨q, s⟩ can map to several triples ⟨q′, s′, d⟩; each such transition is associated with a certain amplitude. The sum of the squares of the norm of these amplitudes must equal 1.

The configuration (or instantaneous description) of a classical TM includes the current state, the contents of the tape, and the position of the tape head. Let {c_{i}}_{i=1}^{∞} be an enumeration of all possible configurations. In the section about quantum circuits we have seen that to define a unitary transformation, it suffices to define the transformation on the classical basis states |b_{1}...b_{n}⟩ with b_{i} ∈ {0, 1}. For the QTM we do something similar, using the configurations {c_{i}}_{i=1}^{∞} as a basis.

We construct the (infinite-dimensional) matrix U = U_{⟨Γ,Q,δ⟩} as follows: the matrix entry with column c and row c′ contains the amplitude associated to go from configuration c to c′ in one step of the QTM, as prescribed by δ. Note that the number of non-zero entries in each row, i.e. the number of configurations c′ reachable from c, is certainly finite because δ has a finite description (in fact it is at most 2 · #Q · #Γ). So each row of U has zero entries almost everywhere. In the special case of a reversible deterministic TM there is only one transition leading from c to c′, and we obtain a permutation matrix.

We call U the time evolution operator, but in order to get a time evolution agreeing with quantum mechanics we must require that U be unitary (or, as can be shown equivalent, preserves Euclidean length). So if γ := ∑_{j=1}^{∞} α_{j}c_{j} is a superposition of configurations with Euclidean length 1 (i.e. ∑_{j=1}^{∞} |α_{j}|^{2} = 1), then one step of the QTM is defined by

γ ⟶^{U} U(∑_{j=1}^{∞} α_{j}c_{j}) = ∑_{j=1}^{∞} α_{j}U(c_{j}).  (4.11)

It is crucial to keep in mind that the definition of the QTM is based on the operator U acting on the complex vector space spanned by {c_{i}}_{i=1}^{∞}. Even though U is unambiguously defined by Q, Γ and δ, one easily loses intuition for what is going on. For concreteness, we can still think of each tape symbol as a qustring of ⌈lg #Γ⌉ qubits, with the ⊤ represented by the qustring consisting of |0⟩’s only. But imagining the tape head in many superpositions becomes rather mind-boggling.

It may not seem evident to verify that U_{⟨Γ,Q,δ⟩} indeed is unitary, but Bernstein and Vazirani show how this requirement translates to a set of conditions on δ which are relatively easy to verify, preserving Euclidean length being one of them.

Note that the amplitudes associated to each image of δ(q, s) are restricted to the subset of complex numbers whose real and imaginary parts can be approximated with an accuracy of 2^{−n} in a time polynomial in n for a deterministic Turing Machine. Without such a restriction non-computable information could be encoded in the binary expansion of the amplitudes. Another point is that not all different execution paths, represented by different configurations in superposition, need to enter q_{f} in the same time step. This is resolved by requiring that all inputs of same length take the same amount of time.

A language L ⊂ (Γ − ⊤)^{∗} belongs to the class BQP if the following holds: there exists a QTM that needs polynomially many steps in the length of its input z, such that if z∈L (z∉L) then z is accepted (rejected) with probability at least \frac{2}{3}. The class BQP is considered the quantum analogue of BPP: it reflects the class of languages efficiently computable on a quantum computer.

One of the main results of [BV97] is the fact that a universal QTM exists with only a polynomial simulation overhead. This allows us to use universal simulation as the mechanism through which the interface S has access to the adversary E.

4.5.2 Protocol, output, view, profile, the adversary

In order to execute a quantum protocol we suppose that A has access to a Quantum Turing Machine, called A. This QTM is equipped with an input tape, work tape and output tape. Before the protocol starts the (classical) input x is written on the input tape, whereas the work tape and output tape are in some well-defined pure state. The quantum state corresponding to A’s overall initial configuration is described by |ψ_{0}^{A}(x)⟩. We define |ψ_{0}^{B}(y)⟩ in a similar way. A and B both have access to a communication tape, whose initial state is described by |ψ_{0}^{C}⟩.

We assume that A begins and that B ends, so k, the number of steps, is even. We will describe A’s action during step j of the protocol for j odd; for j even A does nothing.

(a) A copies to one track of her work tape (reserved for logging purposes) all qubits received on the channel C representing classical bits.

(b) A applies a unitary operator U_{j}^{A} on the Hilbert space H^{A} ⊗ H^{C}.

(c) A copies to her logging track all qubits on C representing classical bits before she sends them.

B does nothing during step j, so U_{j}^{B} = Id. Note that anything he could do while it is A’s turn is restricted to a unitary transformation on his own qubits, which can be included in the previous or next step.

The unitary transformation on the full Hilbert space H^{A} ⊗ H^{C} ⊗ H^{B} in step j is

U_{j}^{tot} = U_{j}^{A} ⊗ Id^{B}  (j odd)  (4.12)

For j even, it is B’s turn and A does nothing. U^{B} acts on H^{C} ⊗ H^{B}, and we find

U_{j}^{tot} = Id^{A} ⊗ U_{j}^{B}  (j even)  (4.13)

We see that A and B can be described as a finite sequence of operators:

A = [U_{1}^{A}, Id^{A}, U_{3}^{A}, Id^{A}, ..., U_{k−1}^{A}, Id^{A}]  (4.14)

and

B = [Id^{B}, U_{2}^{B}, Id^{B}, U_{4}^{B}, ..., Id^{B}, U_{k}^{B}]  (4.15)

All the unitary operators U_{j}^{P} above are computable in polynomial time by a QTM.

Define

|ψ_{0}^{tot}⟩ := |ψ_{0}^{A}(x)⟩ ⊗ |ψ_{0}^{C}⟩ ⊗ |ψ_{0}^{B}(y)⟩  (4.16)

The protocol [A, B](x)(y) evolves as follows:

|ψ_{j}^{tot}⟩ := U_{j}^{tot}(|ψ_{j−1}^{tot}⟩),  (4.17)

where j = 1...k.

At the end of the protocol, B moves the contents of the communication tape to its work tape, returning the communication tape to its initial state. Then each party P makes a measurement of the output tape in the standard basis. The result of this measurement defines a stochastic variable, the party’s output of the protocol, written as [A, B]_{P}(x, y).

The view of a party P is the final state after the measurement has been performed. This final state, written as [A, B]_{P}^{∗}(x, y), is a density matrix. It is obtained by tracing out as explained in Subsection 4.3.3.

The adversary E is modeled like a player, but is more powerful. It is also a QTM, but we put no restrictions on the time it takes. E has an extra step 0, denoted by U_{0}^{E} in which it can issue a (classical) corruption request (in a two-party protocol it does not seem meaningful to have E being in a superposition of corrupting A and B, but in a multi-party setting it is). The operator U_{j}^{E} describes its behavior during round j. For j odd or even, depending whether A or B is corrupted, U_{j}^{E} = Id. During the protocol E behaves as any party monitoring a combined channel: it measures the qubits known to be classical and stores them.

At the end E must provide the corrupted party with an output; this follows from the discussion about output awareness in Section 2.5.2 and our proposed definition of security. Hence, at the end of the protocol E performs a measurement M^{E}, and provides the result to the corrupted party, which defines this party’s output. Its quantum state after the measurement is defined as the adversary’s view of the protocol, and is written as [A, B: E]_{E}^{∗}(x, y).

Just as in the classical case, we are interested in the profile, the triple consisting of the output of A, the output of B, and the view of E. Therefore we define the following variable:

[A, B: E]^{‡}(x)(y) =^{def} ⟨[A, B: E]_{A}(x)(y), [A, B: E]_{B}(x)(y), [A, B: E]_{E}^{∗}(x)(y)⟩. (4.18)

Even though strictly speaking the first and the second component are stochastic variables, we will regard them as density matrices.

Just as in the classical case, we can assume that the inputs x and y are samples from the stochastic variable X and Y, so [A, B: E]^{‡}(X)(Y) is well-defined.

Recall that cryptographic protocols are usually designed with a security parameter, n, which is not explicit in the notation. The notion of exponential indistinguishability for quantum states has been explored in detail in Chapter 3.

4.5.3 Comparing the security of protocols; interface

For comparing the security of two quantum protocols we follow the same course as for comparing the security of classical protocols, as explained in Section 2.2.3. Just as before we introduce an interface which can translate any attack E on Π_{1} into an attack S(E) on Π_{2}, but now we assume that S is a QTM. Again we use universal simulation.

The following definition is the analogue of the classical definition of relative security, Definition 2.1. The difference is that everything, except the protocol output, has become quantum.

4.2 Definition Protocol Π_{1} = [A_{1}, B_{1}] is at least as secure as Π_{2} = [A_{2}, B_{2}] if there exists an interface S from [A_{1}, B_{1}] to [A_{2}, B_{2}] such that for all E ∈ E_{1} and for all possible ⟨X, Y ⟩ which are joint stochastic variables on X ×Y:

[A_{1}, B_{1}: E]^{‡}(X)(Y) ≈ [A_{2}, B_{2}: S(E)]^{‡}(X)(Y).  (4.19)

By choosing X and Y to range over all possible stochastic variables, we deal with the problem of side information, classical and quantum. This follows from the fact that we consider classical tasks only: whatever quantum system E ends up with, it can never be entangled with the input or output of the honest party, since s/he has been honest and has ‘collapsed’ the adversary’s state to something classical. Therefore, all that has been said about composition of protocols and about protocol reductions carries over to quantum protocols.

4.3 Theorem Let [A′_{1}, B′_{1}] be as secure as [A′_{2}, B′_{2}], and let [A′′_{1}, B′′_{1}] be as secure as [A′′_{2}, B′′_{2}]. Then Π_{1} = [A′_{1}A′′_{1}, B′_{1}B′′_{1}] is as secure as Π_{2} = [A′_{2}A′′_{2}, B′_{2}B′′_{2}].

If we consider cryptographic tasks for qubits this reasoning is likely to fail. Entanglement allows for interdependencies between such protocols that classically do not exist and probably each new protocol would have to be proven from scratch, even if the building blocks are well-known sub-protocols.

4.5.4 Ideal protocols and absolute security

Since we model classical protocol tasks, we can use the same definitions of ideal protocols as in Section 2.2.1. To facilitate the translation between the quantum implementation and the classical ideal protocol, there are two possibilities:

(a) We assume that A and B come with an ‘translator’ which codes classical bits b to qubits |b⟩ and vice versa.

(b) We assume that A and B are also quantum computers, and furthermore that the trusted host ‘collapses’ each qubit it sends or receives by measuring it according to the {|0⟩, |1⟩} basis.

Since an honest A or B communicates only classical information with the trusted host, the possibilities are equivalent. We choose possibility (b).

The definition of absolute security of a quantum protocol follows the same procedure; we require that the protocol be at least as secure as the ideal task:

4.4 Definition Let Π_{1} = [A_{1}, B_{1}] be the protocol implementation of a cryptographic task T, while Π_{2} = [A, B] is the ideal protocol for T. Then [A_{1}, B_{1}] is a secure protocol for T if [A_{1}, B_{1}] is as secure as [A, B].

At the moment of writing we do not know a candidate protocol that could satisfy this definition, and an additional assumption of some sort is probably necessary. For instance, we can assume that decoherence (quantum noise) exists, that the number of particles which can be measured coherently is only a constant fraction of all the particles sent, or that honest parties are available to bootstrap the protocol. Applying the definition in this context will be the subject of future research.

4.6 Rewinding the adversary

In Section 2.3 we spent a considerable effort explaining the various choices in the way the interface S controls the adversary E. In light of the different nature of quantum information we have to reconsider this.

The points which were addressed in Section 2.3 were the following:

(a) The order of the quantifiers.

There is no reason to reopen this discussion in the quantum scenario; the same argumentation as in the classical case applies.

(b) The computational power of the interface. We have argued before that the interface should not be too powerful. Therefore we require that the time it takes the interface S to attack Π_{2} is polynomial in the time it takes the adversary E to attack Π_{1}. Observe that if we put no such limitation on the computational power of S, it could simulate E simply by working out all the mathematical equations. This follows from Feynman’s observation that every quantum evolution can be simulated classically with exponential slowdown [Fe82 ]. The exponent comes from the fact that the state of a system consisting of n particles is described by a vector in a 2^{n}-dimensional Hilbert space.

(c) The extent to which the interface can influence the adversary. This is an important issue. Classically, we discussed two choices:

(i) universal simulation, for which we reasoned that taking snapshots and resetting was possible.

(ii) black-box simulation, for which resetting was possible, provided the randomness of E was supplied via the random tape, not internally.

Quantumly we consider the same choices. However, due to the information disturbance principle discussed in Section 4.4.3 it turns out that the classical techniques to simulate a probability distribution fail, as we will see shortly.

What does rewinding exactly mean in the classical case? Suppose a computer is running some program. Let c_{1} be the configuration of this program at some welldefined time t_{1}. When the program is implemented by a TM, the configuration includes the current state, the contents of all tapes, and the position of the tape heads. We would either like to remember c_{1}, or to be able to reconstruct it accurately. We proceed with the computation until some later time t_{2}. In one way or another we subject the current configuration c_{2} to a test T. If the test succeeds then continue the computation, else return to the configuration c_{1} in one way or another, but in polynomial time.

In case of black-box simulation, configuration c_{1} can be reconstructed by resetting the black-box and re-running the whole program again. Even though this does not change the behavior of the simulated E, the interface S can remember the random choices that worked, and try different ones where the simulation failed. In some sense this can be regarded as backtracking for probabilistic algorithms: if the algorithm fails it can return to a previous configuration in which it was successful (at least up to that point) and try another branch. This kind of simulation is often used in proofs of security for sequential composition of protocols under computational assumptions. It is also used, for instance, in [NOVY92 ]. In universal simulation ‘snapshots’ are allowed, so resetting and re-computing is unnecessary.

Quantumly it is tempting to think that rewinding might be possible by reversing the computation, but this is false. Let |ψ_{i}⟩ be the state at t_{i}, i = 1, 2. Let U_{1,2} be the unitary evolution between time t_{1} and t_{2}. Let T be the two-valued success/fail measurement following U_{1,2}, and let U_{T} denote the unitary operator emulating T. As before, we put the measurement result in one qubit, and get the unitary evolution

|ψ_{1}⟩ ⟶^{U_{1,2}} |ψ_{2}⟩ ⟶^{U_{T}} α|S⟩|ψ_{S}⟩ + β|F⟩|ψ_{F} ⟩  (4.20)

Now we would like to implement something like: if |S⟩ then continue with |ψ_{S}⟩ else U_{T}^{−1}(|F⟩|ψ_{F} ⟩). However, the ‘else’ case does not have the desired effect of returning to |ψ_{2}⟩ because the information contained in |ψ_{S}⟩ is lost. So the suggested evolution is almost certainly not unitary.

To deal with the question rigorously, we appeal to Proposition 4.1 once more: the qubit that contains the test result after the emulated measurement U_{T} is classical. So it can be measured without causing a further disturbance, and we can gain one bit of information with non-negligible probability. It follows that every state not orthogonal to |ψ_{F} ⟩ has been disturbed. So we conclude:

4.5 Proposition Rewinding by reversing the unitary transformation induced by E, or taking snapshots is impossible.

The overall conclusion with regard to measurements is that a measurement can always be undone, see Section 4.3.2, provided that all its possible (classical) measurement results are ‘forgotten’. We cannot accept some results and undo others. In Svozil’s extension [Sv97 , p. 12] of Schrödinger’s words [Sc35 ]: “By no way can we open the prediction catalog at one page [measure a density matrix in one basis], read and (irreversibly) memorize the page, close it; then open it at another, complementary [conjugate], page.”

But with regard to rewinding, showing that rewinding by reversing or by taking snapshots is impossible does not show that no other ways to rewind in polynomial time exists. Below we show that the classical technique of resetting the black box and computing ‘forward’, as has been described above, can only exist if quantum one-way functions do not exist. More precisely, suppose that S has a polynomial time algorithm R which takes as input |ψ_{1}⟩ and a description of U_{1,2} and T, and which outputs |ψ_{2}⟩ such that T (|ψ_{2}⟩) = success. Then R can be used to invert any one-way permutation.

The existence of one-way permutations, easy to compute in quantum polynomial time but hard to invert, is likely because of the results of Bennett, Bernstein, Brassard and Vazirani [BBBV97 ]. They show that, relative to a length preserving permutation oracle chosen at random, with probability 1 the class NP∩co-NP cannot be solved in time 0(2^{n/3}) on a QTM. It must be realized that if the class NP∩co-NP can be solved in polynomial time, then one-way permutations cannot exist: for any permutation f the language {y ∈ {0, 1}^{n}|∃x ∈ {0, 1}^{n−1} s.t. f(x0)=y} is evidently in NP. It is also in co-NP since its complement can be described as the set of y with a pre-image ending in 1. So deciding whether the pre-image of y ends in a 0 or 1 can be decided efficiently; a similar technique applies to retrieve the other bits.

4.6 Proposition Let |ψ_{2}⟩ be an arbitrary quantum state, and let T be an arbitrary two outcome test on |ψ_{2}⟩. Suppose that there exists a quantum algorithm R which takes as input |ψ_{1}⟩, U_{1,2} and T, and which yields a new state |ψ_{2}⟩ such that T (|ψ_{2}⟩) = success with overwhelming probability. Then there exists a polynomial time algorithm for inverting any one-way permutation.

Proof: Let f:{0, 1}^{n} →{0, 1}^{n} be a permutation. Let x̄∈{0, 1}^{n} be arbitrary, and let ȳ:= f(x̄). We construct a polynomial time algorithm which inverts f at ȳ. First we create the state

|ψ_{0}⟩ = ∑_{x∈\{0,1\}^{n}} \frac{1}{2^{n/2}} |x; 0^{n}⟩.

Then we evaluate the image of this state under f:

|ψ_{1}⟩ := f(|ψ_{0}⟩) = ∑_{x∈\{0,1\}^{n}} \frac{1}{2^{n/2}} |x; f(x)⟩

Let ȳ_{i} be the ith bit of ȳ and define the test T (|ψ_{2}⟩) = “the last bit of |ψ_{2}⟩ equals ȳ_{n}”.

By hypothesis, R = R(|ψ_{1}⟩, Id, T) computes in polynomial time a new state |ψ_{2}⟩ such that the last bit of |ψ_{2}⟩ equals ȳ_{n}. We proceed in this fashion for all the bits of ȳ, using the output of each procedure call to R as input to the next. After n steps the final state is |x̄; ȳ⟩, so f has been inverted. □.

So we have proven that rewinding by reversible computation, by taking snapshots, and by resetting and roll forwards from the beginning is impossible. Still, this does not prove that rewinding is completely ruled out. On the other hand, the kind of rewinding used here is in fact very realistic. For instance, in [NOVY92 ], Naor, Ostrowsky, Venkatesan and Yung give a Bit Commitment scheme which is computationally binding. That is, if an algorithm E exists that can open the Bit Commitment as 0 or 1 with non-negligible probability, they show that there exists a (classical) polynomial time algorithm S which inverts any one-way permutation f.

This algorithm S makes use of classical rewinding. Suppose we replace the classical algorithms E and S in this reduction by quantum algorithms E and S, and we allow quantum rewinding. Then, using the techniques developed in [BCMS97 ], we can obtain a quantum polynomial time algorithm that inverts any one-way permutation. Since rewinding is the only classical assumption the reduction (i.e. the description of S) uses, this gives us yet more evidence that quantum rewinding is generally impossible.

The fact that in the quantum model rewinding is probably impossible is worrying. For instance, if we take any Zero Knowledge protocol and run it on Quantum Turing Machines, then suddenly the proof of its security does not hold any longer. The general conclusion of this section is that proving the security of a quantum protocol by using simulatability is much harder, but at this point in time no promising alternative to proving security seems available.

4.7 Extensions and open problems

So far, we have assumed that the channel that connects A and B is perfect, and that it cannot be eavesdropped on. Observe in the first place that such assumptions are justified because of the existence of quantum error correcting codes (see for instance [Sh96 , Pr97 ] and the references therein). Intuitively, the idea is to embed each 2dimensional qubit in a much larger Hilbert space, of 2^{7} dimensions, for instance. When an error in one of the seven qubits occurs, the state leaves its allotted subspace. We can always correct this error and return the state to the subspace it should be in, surprisingly without disturbing the state.

To deal with an eavesdropper E, we only have to remember Figure 4.2, in which U^{E} is a transformation that it can perform on the quantum channel after A has sent but before B has received. It might be interesting to prove the security of the Quantum Key Distribution protocol by using simulation. In the ideal task a trusted host sends the same random string to both A and B, and E can corrupt nobody. So the question becomes whether an interface S, without talking to anybody, can produce a conversation which is indistinguishable from the real interaction between A and B.

Another extension is to include decoherence. Decoherence is quantum noise: in a non-perfect transmission we must consider the possibility that a quantum particle gets entangled with a particle which is not part of our system, usually called the environment. This is again a unitary transformation, just as in eavesdropping, but since we do not control the ‘strange’ particle the effect is an uncontrolled disturbance of the state, i.e. noise. Decoherence is exactly the phenomenon we are trying to fight with quantum error correction. But instead of regarding it as nuisance, it might also be used to our advantage. If decoherence can be proven to exist and can be quantified properly, it might very well be an additional hypothesis to base quantum protocols on. It would basically exploit the same idea as has been done classically by Crépeau and Kilian [CK88, Cr97 ], in which it is shown how to build Oblivious Transfer from a Noisy Channel.

A somewhat different question concerns transferability of proofs. In a classical zero knowledge protocol, if A provides B with a proof, this proof is certainly not transferable to a third party D: by definition B could have created this proof all by himself. The question is whether the same argument still applies in quantum protocols, in particular when D first supplies B with a quantum system in a state unknown to B. In addition, B is supposed to perform measurements on this system depending on messages received from A, and to use the measurement results as a source of randomness in his communication with A. After B has finished interacting with A he sends the transcript of the conversation, together with the modified quantum system back to D. The question is whether B is able to satisfy D without ever talking to A, or whether this serves as a transferable proof of knowledge.

Conclusion

We must never forget that “reality” too is a human word just like “wave” or “consciousness”. Our task is to use these words correctly—that is, unambiguously and consistently.

Niels Bohr (as quoted by Kalckar)

The main objective of this thesis, presenting a formal model for quantum protocols and developing a definition of security, has been achieved. However, it is still too early to judge precisely the merits of this definition. A part of the problem is that no two-party protocol task fulfills the definition without an additional assumption, for instance the existence of noisy quantum channels (decoherence). On the other hand, the notions of exponential indistinguishability for quantum systems and of reduction between protocols (“an attack on protocol Π_{1} must imply an attack on Π_{2}”), as a fundamental method to compare the security of quantum protocols, have been defined properly.

We have presented good reasons to believe that the classical technique of rewinding is quantumly impossible. But in a quantum world, where everything is reversible and no information gets lost, the fact that rewinding is impossible looks actually very reasonable. The initial objection when this research was started, that Quantum Bit Commitment was secure yet not rewindable or simulatable, has disappeared. It will be interesting so see how these notions develop when we make the additional assumption that decoherence exists.

A practical problem encountered when trying to prove security is the fact that many quantum protocols use error-correcting codes at some stage. Maybe the techniques developed in Chapter 3 can be extended to deal with this problem.

From Chapter 2 it is obvious that, after 20 years of (public) research in cryptography, the field is still in a precarious state. Even just classically we talk about protocol security all the time, but we still have problems defining it properly, or coming up with rigorous proofs. Yet, I am not aware of more than 5 papers continuing the approaches of Beaver and/or Micali-Rogaway presented 6 years ago. In my opinion there is a serious problem here, and it deserves much wider attention.

Even if practical implementations of quantum protocols remain restricted to quantum key distribution, I believe quantum cryptography has taught cryptography an important lesson. It has shown us that our intuitions about security and our definitions are based on classical assumptions. Since the overwhelming majority of protocols in use today is classical anyway, this is perfectly all right. Nevertheless, from a purely theoretical perspective things look different. Physical experiments show us that the world is intrinsically quantum. Therefore we should also accept the quantum-version of the Church-Turing thesis: that quantum computation is the fundamental notion of computability. But if we accept that, we must certainly investigate what security defined in terms of quantum mechanics means. This has led already to some surprises, new insights and puzzling questions about what security really means. In this respect we only begin to understand what’s going on.

The title of my thesis is tentative. I hope that this work contributes to a proper understanding of the topics mentioned above.

Acknowledgments

Regardez le ciel. Demandez-vous : Le mouton oui ou non a-t-il mangé la fleur? Et vous verrez comme tout change... Et aucune grande personne ne comprendra jamais que ça a

tellement d’importance! Le petit prince

In the first place I would like to thank my two supervisors, Gilles Brassard and Claude Crépeau. I can never decide who I should thank more, therefore I won’t. For neither of them I have ever been able to figure out how exactly they do research or how they think, but both have mathematical, physical and cryptographic intuitions that would always baffle me (“Where did he get that from??”). Working with them in the vanguard of science is extremely stimulating and exciting, and I have learned enormously from them. They also kept their confidence in me when progress was not as expected; for this I thank them most. The Chapters 2 and 4 grew out of many long discussions with them.

The money for my PhD came indirectly from the research councils of Canada and Québec. I want to thank NSERC and FCAR for making this research possible.

Intellectually the most shocking experience of the past five years was to be confronted with quantum mechanics (maybe apart from, on the sly, Richard Dawkins’ books on evolution). I had always been interested in the subject, but probably got a little more than I was prepared for. Actually, during the first months in Montreal I thought that the whole subject of quantum computation was ridiculous, and I was shocked when I began to understand that the Church-Turing thesis is indeed a physical assumption. I would like to thank Richard Jozsa, Bill Wootters, Chris Fuchs and Tal Mor for their endless efforts trying to explain quantum physics to me. I think their time and energy have not been completely in vain: I often had (and still have) this ”ooh, so that is what he meant” experience, usually several years later.

Chapter 3 is the result of work done together with Chris. He deserves an extra thanks for explaining to me that seeing a cat in superposition of being alive or dead is not more improbable than seeing tomorrow’s weather with 50 % chance of sunshine and 50 % chance of snow. From Tal I learnt another important thing: to be happy with small results.

Furthermore, I have had many good discussions with the people from the lab, Alain Tapp, Dominic Mayers and Michel Boyer in particular.

For supporting me in one way or another I would like to thank Eliana, Frédéric & Ordia, Hassan & Mounia and Jean-François in Montreal, and my friends and family in the Netherlands, especially Alexander, Frank, Heleen, Liesbeth, Teake, and my parents.

Finally, I would like to thank Ana Paola for two and a half years of e-mail support and patience.

Bibliography

[Be89] Beaver, D., “Multiparty protocols tolerating half faulty processors”, In Proc. CRYPTO 89 (1989), G. Brassard, Ed., Springer-Verlag, pp. 560–572, Lecture Notes in Computer Science No. 435.

[BG89] Beaver, D. and S. Goldwasser, “Multiparty computation with faulty majority”, In Proc. CRYPTO 89 (1989), G. Brassard, Ed., Springer-Verlag, pp. 589–590, Lecture Notes in Computer Science No. 435.

[Be90] Beaver, D., Security, Fault Tolerance, and Communication Complexity in Distributed Systems, PhD thesis, Harvard University, 1990.

[Be91a] Beaver, D., “Foundations of secure interactive computing”, In Proc. CRYPTO 91 (1991), J. Feigenbaum, Ed., Springer, pp. 377– 391, Lecture Notes in Computer Science No. 576.

[Be91b] Beaver, D., “Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority”, Journal of Cryptology 4, 2 (1991), pp. 75–122.

[Be96] Beaver, D., personal communication, June 1996.

[Be82] Ben-bassat, M., “Use of distance measures, information measures and error bounds in feature evaluation”, In Handbook of Statistics, Volume 2 — Classification, Pattern Recognition and Reduction of Dimensionality (1982), P. R. Krishnaiah and L. N. Kanal, Eds., North-Holland, pp. 773–791.

[BB84] Bennett, C. H. and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing”, In Proceedings of IEEE International Conference on Computers, Systems and Signal Processing (Bangalore, India, 1984), pp. 175–179.

[BBBSS92] Bennett, C. H., F. Bessette, G. Brassard, L. Salvail and J. Smolin, “Experimental quantum cryptography”, Journal of Cryptology 5, 1 (1992), pp. 3–28.

[BBE92] Bennett, C. H., G. Brassard and A. Ekert, “Quantum cryptography”, Scientific American, October (1992), pp. 50–57.

[BBM92] Bennett, C. H., G. Brassard and N. Mermin, “Quantum cryptography without Bell’s theorem”, Physical Review Letters 68, 5 (1992), pp. 557–559.

[BMS96] Bennett, C. H., T. Mor and J. Smolin, “The parity bit in quantum cryptography”, Physical Review A 54, 3 (1996), p. 2675, also

available at http://xxx.lanl.gov/ps/quant-ph/9604040.

[BBBV97] Bennett, C. H., E. Bernstein, G. Brassard and U. Vazirani, “Strengths and weaknesses of quantum computation”, SIAM J. Computing 26, 5 (1997), pp. 1510–1523.

[BGW88] Ben-or, M., S. Goldwasser and A. Wigderson, “Completeness theorems for fault-tolerant distributed computing”, In Proc. 20th ACM Symp. on Theory of Computing (Chicago, 1988), ACM, pp. 1– 10.

[BV97] Bernstein, E. and U. Vazirani, “Quantum complexity theory”, SIAM J. Computing 26, 5 (1997), pp. 1411–1473.

[BBBGM98] Biham, E., M. Boyer, G. Brassard, J. van de Graaf and T. Mor, “Security of quantum key distribution against all collective attacks”, Tech. Rep. 9801022, LANL Quant-ph archives, 1998,

available at http://xxx.lanl.gov/ps/quant-ph/9801022.

[Bl82] Blum, M., “Coin flipping by telephone”, In Proc. IEEE Spring COMPCOM (1982), IEEE, pp. 133–137.

[Bo97] Bodor, A., “Is quantum bit commitment really impossible”, Tech. Rep. 9711040, LANL Quant-ph Archives, 1997, available at

http://xxx.lanl.gov/ps/quant-ph/9711040.

[BCC88] Brassard, G., D. Chaum and C. Crépeau, “Minimum disclosure proofs of knowledge”, Journal of Computer and System Sciences 37, 2 (1988), pp. 156–189.

[BC89] Brassard, G. and C. Crépeau, “Sorting out zero-knowledge”, In Proc. EUROCRYPT 89 (1989), J.-J. Quisquater and J. Vandewalle, Eds., Springer, pp. 181–191, Lecture Notes in Computer Science No. 434.

[BCJL93] Brassard, G., C. Crépeau, R. Jozsa and D. Langlois, “A quantum bit commitment scheme provably unbreakable by both parties”, In Proc. 34th IEEE Symp. on Foundations of Comp. Science (1993), IEEE, pp. 362–371.

[BCS96] Brassard, G., C. Crépeau and M. Sántha, “Oblivious transfers and intersecting codes”, IEEE Transactions on Information Theory 42, 6 (1996), pp. 1769–1780.

[BC97] Brassard, G. and C. Crépeau, “Oblivious transfers and privacy amplification”, In Proc. EUROCRYPT 97 (1997), Springer-Verlag, pp. 334–347, Lecture Notes in Computer Science No. 1233.

[BCMS97] Brassard, G., C. Crépeau, D. Mayers and l. Salvail, “Quantum attacks on classical bit commitment schemes”, Tech.

Rep. 9712023, LANL Quant-ph archives, 1997, available at

http://xxx.lanl.gov/ps/quant-ph/9712023.

[Ca96] Canetti, R., Studies in Secure Multiparty Computation and Applications, PhD thesis, The Weizmann Institute of Science, 1996, version dated: “June 1995; Revised: March 1996”.

[CFGN96] Canetti, R., U. Feige, O. Goldreich and M. Naor, “Adaptively secure multi-party computation”, Tech. Rep. 682, Laboratory of Computer Science, Massachusetts Institute of Technology, 1996, Report on line available from

http://www.wisdom.weizmann.ac.il/people/homepages/oded/papers.html.

[Ch81] Chaum, D., “Untraceable electronic mail, return addresses, and digital pseudonyms”, Communications of the ACM 24 (1981), pp. 84– 88.

[CCD88] Chaum, D., C. Crepeau and I. Damgård, “Multi-party unconditionally secure protocols”, In Proc. 20th ACM Symp. on Theory of Computing (Chicago, 1988), ACM.

[CG97] Cirac, J. I. and N. Gisin, “Coherent eavesdropping strategies for the 4 state quantum cryptography protocol”, Tech. Rep. 9702002, LANL Quant-ph Archives, 1997, available at

http://xxx.lanl.gov/ps/quant-ph/9702002.

[CT91] Cover, T. M. and J. A. Thomas, Elements of Information Theory, Wiley Series in Telecommunications, New York: John Wiley & Sons, 1991.

[CK88] Crépeau, C. and J. Kilian, “Weakening security assumptions and oblivious transfer”, In Proc. CRYPTO 88 (1988), S. Goldwasser, Ed., Springer-Verlag, pp. 2–7, Lecture Notes in Computer Science No. 403.

[Cr90] Crépeau, C., Correct and Private Reductions Among Oblivious Transfers, PhD thesis, Massachusetts Institute of Technology, 1990.

[Cr94] Crépeau, C., “Quantum oblivious transfer”, Journal of Modern Optics 41, 12 (1994), pp. 2445–2454.

[CGT95] Crépeau, C., J. van de Graaf and A. Tapp, “Committed oblivious transfer and private multi-party computation”, In Proc. CRYPTO 95 (1995), Springer-Verlag, pp. 110–123, Lecture Notes in Computer Science No. 963.

[Cr97] Crépeau, C., “Efficient cryptographic protocols based on noisy channels”, In Proc. EUROCRYPT 97 (1997), Springer-Verlag, pp. 306–317, Lecture Notes in Computer Science No. 1233.

[De85] Deutsch, D., “Quantum theory, the Church-Turing principle and the universal quantum computer”, Proc. Royal Society London Series A, 400 (1985), pp. 97–117.

[EPR35] Einstein, A., B. Podolski and N. Rosen, “Can the quantummechanical description of physical reality be considered complete?”, Physical Review 47 (1935), pp. 777–780, Reprinted in [WZ83].

[Fe82] Feynman, R., “Simulating physics with computers”, Int. Journal of Theoretical Physics 21, 6/7 (1982), pp. 467–488.

[Fr93] Franklin, M., Complexity and Security of Distributed Protocols, PhD thesis, Computer Science Department, of Columbia University, New York, 1993.

[FS90] Feige, U. and A. Shamir, “Witness indistinguishable and witness hiding protocols”, In Proc. 22nd ACM Symp. on Theory of Computing (Baltimore, MY, 1990), B. Awerbuch, Ed., ACM Press, pp. 416– [FC94] Fuchs, C. A. and C. M. Caves, “Ensemble-dependent bounds

for accessible information in quantum mechanics”, Physical Review Letters 73, 23 (1994), pp. 3047–3050.

[FC95] Fuchs, C. A. and C. M. Caves, “Mathematical techniques for quantum communication theory”, Open Systems and Information Dynamics 3, 3 (1995), pp. 345–356.

[Fu95] Fuchs, C. A., Distinguishability and Accessible Information in Quantum Theory, PhD thesis, University of New Mexico, 1995.

[Fu96] Fuchs, C. A., “Information gain vs. state disturbance in quantum theory”, to appear in Fortschritte der Physik (1996), available at

http://xxx.lanl.gov/ps/quant-ph/9611010.

[FGGNP97] Fuchs, C. A., N. Gisin, R. B. Griffiths, C. S. Niu and A. Peres, “Optimal eavesdropping in quantum cryptography. I. Information bound and optimal strategy”, Physical Review A 56, 2 (1997), pp. 1163–1172.

[GO94] Goldreich, O. and Y. Oren, “Definitions and properties of zero-knowledge proof systems”, Journal of Cryptology 7, 1 (1994), pp. 1–32.

[GMR85] Goldwasser, S., S. Micali and C. Rackoff, “The knowledge complexity of interactive proof-systems”, In Proc. 17th ACM Symp. on Theory of Computing (Providence, 1985), ACM, pp. 291–304.

[GMR89] Goldwasser, S., S. Micali and C. Rackoff, “The knowledge complexity of interactive proof-systems”, SIAM. J. Computing 18, 1 (1989), pp. 186–208.

[Gr95] van de Graaf, J., “The matchmaking problem”, CWI Quarterly 8, 2 (1995), pp. 129–146.

[HR70] Hellman, M. E. and J. Raviv, “Probability of error, equivocation, and the Chernoff bound”, IEEE Transactions on Information Theory IT-16, 4 (1970), pp. 368–372.

[He76] Helstrom, C. W., Quantum Detection and Estimation Theory, Mathematics in Science and Engineering, vol. 123, Academic Press, 1976.

[Hu89] Hughes, R. I. G., The Structure and Interpretation of Quantum Mechanics, Harvard University Press, 1989.

[Is95] Isham, C., Lectures on Quantum Theory, Imperial College Press, 1995.

[Jo94] Jozsa, R., “Fidelity for mixed quantum states”, Journal of Modern Optics 41, 12 (1994), pp. 2315–2323.

[Ka67] Kailath, T., “The divergence and Bhattacharyya distance measures in signal selection”, IEEE Transactions on Communication Technology COM-15, 1 (1967), pp. 52–60.

[Ke97] Kent, A., “Unconditionally secure quantum bit commitment”, Tech. Rep. 9711023, LANL Quant-ph Archives, 1997, available at

http://xxx.lanl.gov/ps/quant-ph/9711023.

[Ki88] Kilian, J., “Founding cryptography on oblivious transfer”, In Proc. 20th ACM Symp. on Theory of Computing (Chicago, 1988), ACM, pp. 20–31.

[Ki90] Kilian, J., Uses of Randomness in Algorithms and Protocols, MIT Press, 1990.

[Lo97] Lo, H.-K., “Insecurity of quantum secure computations”, Tech. Rep. 9611031, LANL Quant-ph Archives, 1997, available at

http://xxx.lanl.gov/ps/quant-ph/9611031.

[LC97a] Lo, H.-K. and H. F. Chau, “Is quantum bit commitment really possible?”, Physical Review Letters 78 (1997), pp. 3410–3413.

[LC97b] Lo, H.-K. and H. F. Chau, “Why quantum bit commitment and ideal quantum coin tossing are impossible”, Tech. Rep. 9711065, LANL Quant-ph archives, 1997, available at

http://xxx.lanl.gov/ps/quant-ph/9711065.

[LV93] Li, M. and P. Vitányi, An introduction to Kolmogorov Complexity and its Applications, Springer, 1993.

[Li56] Lindley, D. V., “On a measure of the information provided by an experiment”, Ann. Math. Statist. 27 (1956), pp. 986–1005.

[Ma97] Mayers, D., “Unconditionally secure quantum bit commitment is impossible”, Physical Review Letters 78 (1997), pp. 3414–3417.

[Me96] Mermin, N. D., “The Ithaca Interpretation of Quantum Mechanics”, Tech. Rep. 9609013, LANL Quant-ph Archives, 1996, available

at http://xxx.lanl.gov/ps/quant-ph/9609013.

[MR91] Micali, S. and P. Rogaway, “Secure Computation”, preliminary version in CRYPTO 91.

[Mo97] Mor, T., Quantum Memory in Quantum Cryptography, PhD thesis, Technion, Haifa, 1997.

[MS97] Mayers, D. and L. Salvail, personal communication, October 1997.

[NOVY92] Naor, M., R. Ostrovsky, R. Venkatesan and M. Yung, “Perfect zero-knowledge arguments for np can be based on general complexity assumptions”, In Proc. CRYPTO 92 (1992), E. F. Brickell, Ed., Springer-Verlag, pp. 196–214, Lecture Notes in Computer Science No. 740.

[Or87] Oren, Y., “On the cunning power of cheating verifiers: Some observations about zero knowledge proofs (extended abstract)”, In 28th Annual Symposium on Foundations of Computer Science (Los Angeles, California, 1987), IEEE, pp. 462–471.

[Or96] Or�owski, A., “Measures of distance between quantum states”, In Proceedings of the Fourth Workshop on Physics and Computation — PhysComp ’96 (Boston, 1996), New England Complex Systems Institute, pp. 239–242.

[Pe93] Peres, A., Quantum Theory: Concepts and Methods, Kluwer Academic Publishers, 1993.

[Pr97] Preskill, J., “Reliable quantum computer”, Tech. Rep. 9705031, LANL Quant-ph Archives, 1997, available at

http://xxx.lanl.gov/ps/quant-ph/9705031.

[Ra81] Rabin, M., “How to exchange secrets by oblivious transfer”, Tech. Rep. TR-81, Harvard Aiken Computation Laboratory, 1981.

[RB89] Rabin, T. and M. Ben-or, “Verifiable secret sharing and multiparty protocols with honest majority”, In STOC89 (1989), pp. 73–85.

[RS72] Reed, M. and B. Simon, Methods of Modern Mathematical Physics — Part I: Functional Analysis, Academic Press, 1972.

[Ro91] Rogaway, P., The Round Complexity of Secure Protocols, PhD thesis, Massachusetts Institute of Technology, 1991.

[Sc91] Schnorr, C. P., “Efficient signature generation by smart cards”, Journal of Cryptology 4 (1991), pp. 161–174.

[Sc35] Schrödinger, E., “Die gegenwärtige Situation in der Quantenmechanik”, Naturwissenschaften 23 (1935), pp. 807–812, 823–828, 844–849, English translation in [WZ83].

[SRA81] Shamir, A., R. L. Rivest and L. M. Adleman, “Mental poker”, In The Mathematical Gardner (Belmont, California, 1981), D. Klarner, Ed., Wadsworth, pp. 37–43.

[Sh48] Shannon, C. E., “A mathematical theory of communication”, Bell Sys. Tech. J. 27 (1948), pp. 379–423 and 623–656.

[Sh49] Shannon, C. E., “Communication theory of secrecy systems”, Bell Sys. Tech. J. 28 (1949), pp. 657–715.

[Sh96] Shor, P. W., “Fault-tolerant quantum computation”, In 37th Annual Symposium on Foundations of Computer Science (Burlington, Vermont, 14–16 Oct. 1996), IEEE, pp. 56–65.

[St97] Steane, A., “Quantum computing”, Tech. Rep. 9708022, LANL Quant-ph Archives, 1997, available at http://xxx.lanl.gov/ps/quant-

ph/9708022.

[Su86] Sudbery, Quantum Mechanics and the Particles of Nature — an Outline for Mathematicians, Cambridge University Press, 1986.

[Sv97] Svozil, K., “The Church-Turing thesis as a guiding principle for physics”, Tech. Rep. 9710055, LANL Quant-ph archives, 1997,

available at http://xxx.lanl.gov/ps/quant-ph/9710055.

[To71] Toussaint, G. T., “Some functional lower bounds on the expected divergence for multihypothesis pattern recognition, communication, and radar systems”, IEEE Transactions on Systems, Man, and Cybernetics SMC-1 (1971), pp. 384–385.

[To72] Toussaint, G. T., “Comments on ‘The divergence and Bhattacharyya distance measures in signal selection’ ”, IEEE Transactions on Communication Technology COM-20 (1972), p. 485.

[Uh76] Uhlmann, A., “The ‘transition probability’ in the state space of a ^{∗}-algebra”, Reports on Mathematical Physics 9 (1976), pp. 273– 279.

[Wo81] Wootters, W., “Statistical distance and Hilbert space”, Physical Review D 23 (1981), pp. 357–362.

[WZ82] Wootters, W. and W. Zurek, “A single quantum cannot be cloned”, Nature 299 (1982), pp. 802–803.

[WZ83] Wheeler, J. and W. Zurek, Quantum Theory and Measurement, Princeton University Press, 1983.

[Ya82a] Yao, A. C.-C., “Protocols for secure computations”, In Proc. 23rd IEEE Symp. on Foundations of Comp. Science (Chicago, 1982), IEEE, pp. 160–164.

[Ya82b] Yao, A. C.-C., “Theory and application of trapdoor functions”, In Proc. 23rd IEEE Symp. on Foundations of Comp. Science (Chicago, 1982), IEEE, pp. 80–91.

[Ya95] Yao, A. C.-C., “Security of quantum protocols against coherent measurements”, In Proc. 27th ACM Symp. on Theory of Computing (1995), ACM, pp. 67–82.