MÉMOIRE DE PREMIERE ANNÉE DE MAGISTÈRE - MAI 1993

CRYPTOGRAPHIE QUANTIQUE

Frédéric MAGNIEZ † auteur du sujet : Alain FINKEL ‡

† ENS-Cachan ch. M464 61 av. du Pdt Wilson 94235 Cachan France, e-mail :

magniez@ens-cachan.fr

‡ LIFAC ENS-Cachan 61 av. du Pdt Wilson 94235 Cachan France, e-mail : finkel@ens-cachan.fr

MÉMOIRE DE PREMIERE ANNÉE DE MAGISTÈRE - MAI 1993

CRYPTOGRAPHIE QUANTIQUE

Frédéric MAGNIEZ † auteur du sujet : Alain FINKEL ‡

† ENS-Cachan ch. M464 61 av. du Pdt Wilson 94235 Cachan France, e-mail : magniez@ens-cachan.fr ‡ LIFAC ENS-Cachan 61 av. du Pdt Wilson 94235 Cachan France, e-mail : finkel@ens-cachan.fr

Résumé

Ce mémoire fait à la fois une présentation de la cryptographie quantique au lecteur et une synthèse des découvertes essentielles dans ce domaine, qui subit une expansion considérable depuis ces dernières années. Notre objectif essentiel sera de mettre en évidence des primitives s’appliquant à l’élaboration de protocoles cryptographiques et à la distribution de clefs secrètes utilisées pour le one-time pad^{1}. Un souci d’introduction formelle et de justification des outils quantiques utilisés a été fait, néanmoins il n’est pas nécessaire de tous les assimiler pour comprendre les idées directrices de ce mémoire; le lecteur pourra donc dans une première approche passer sur le formalisme quantique le génant.

1ONE-TIME PAD, ou code de Vernam, inventé en 1917, est un système de codage qui utilise une clef de codage aussi longue que le message à coder que l’on ajoute terme à terme en utilisant l’addition cyclique (l’équivalent en binaire du ou exclusif : ⊕). C’est la seule méthode dont l’inviolabilité ait été prouvée sous l’hypothèse qu’une clef ne soit jamais utilisée deux fois.

Table des matières

1 Introduction 1 1.1 Présentation - Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Résultats fondamentaux de mécanique quantique pour la suite... . . . . . . . . 2

1.3.1 Notions - Polarisation d’un photon . . . . . . . . . . . . . . . . . . . . . 2 1.3.2 Définitions - Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.3 Clônage d’un état quantique . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3.4 Le paradoxe d’E.P.R. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.4 Le one-time pad (version binaire) . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 Le transfert quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Protocoles cryptographiques 6 2.1 Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Mise en gage d’un bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.2 Une version simplifiée . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.3 Une version un peu plus évoluée . . . . . . . . . . . . . . . . . . . . . . 11 2.2.4 Une application : le tirage à pile ou face à distance . . . . . . . . . . . . 13 2.2.5 La dernière version actuelle . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3 Transfert équivoque – Transfert inconscient . . . . . . . . . . . . . . . . . . . . 17 2.3.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.2 Un transfert équivoque faible . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.3 Un transfert inconscient . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.4 Comment avoir un transfert équivoque fort? . . . . . . . . . . . . . . . . 20

3 Distribution de clefs quantiques 22 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2 Un Protocole de distribution de clefs quantiques . . . . . . . . . . . . . . . . . 23

3.2.1 Le protocole théorique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.2 Etude de l’attaque d’Eve . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2.3 L’implémentation pratique . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.3 Autres méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.3.1 Photons EPR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.3.2 Interférométrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4 Conclusion 26

5 Appendice : l’information quantique 27 5.1 Généralités - Postulats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.2 Mesure des grandeurs physiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.3 Réduction du paquet d’ondes (cas d’un spectre discret) . . . . . . . . . . . . . 28 5.4 Quelques conséquences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 TABLE DES MATIÈRES ii

5.5 L’opérateur densité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.5.1 Position . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.5.2 Cas pur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.5.3 Cas non-pur : mélange statique d’états . . . . . . . . . . . . . . . . . . . 30

5.6 Produit tensoriel d’états . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.6.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.6.3 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

Chapitre 1

Introduction

1.1 Présentation - Motivations

Dans les domaines se rapprochant plus ou moins de la cryptographie, on a de tous temps cherché des systèmes inviolables pour, par exemple, échanger des messages dans un secret absolu, la mise en gage d’informations, la comparaison de données sans révéler ces dernières, ou encore résoudre des problèmes se ramenant au tirage à pile ou face à distance. Hélas les solutions jusqu’alors avancées n’étaient pas mathématiquement inviolables ou supposaient des conditions initiales assez fortes, comme pour le one-time pad l’existence de données confidentielles, servant de clefs, entre les interlocuteurs (ce qui en pratique pose le problème de sécurité de stockage de ces données). Cependant, si on se place dans le modèle de la mécanique quantique, son principe d’incertitude donne une autre vision à ces problèmes en apportant des solutions (ou au moins de croire fortement en leur existence) quasi-idéales (en fait les attaques ont une probabilité de réussite exponentiellement faible en la complexité des protocoles (running time)), et réalisables pratiquement (à une échelle encore restreinte, mais qui ne peut que s’améliorer avec les technologies nouvelles et à venir). Dans toute la suite de ce mémoire, on supposera donc être dans un univers pour lequel le modèle de la mécanique quantique est vrai, ce qui semble acceptable comme hypothèse...

1.2 Historique

La naissance de la cryptographie quantique s’est faite dans la fin des années 60 avec Stephen Wiesner et son article “Conjucate Coding” [Wie83] qui, trop innovateur, ne fut pas publié à l’époque. Wiesner y expliquait comment le principe d’incertitude de la mécanique quantique pouvait être utilisé pour produire des données infalsifiables et pour implémenter une primitive de transfert équivoque^{1}. Ce n’est qu’en 1979 que Charles H. Bennet et Gilles Brassard reprirent les travaux de Wiesner pour concevoir un système de distribution de clefs secrètes reposant sur la mécanique quantique [BBBW82]. L’article de Wiesner fut alors publié en 1983. L’un des principaux progrès fut d’utiliser les photons pour transmettre de l’information et non pour la stocker. Ce n’est cependant que vers 1991 que la cryptographie quantique ne fut plus considérée comme de la science fiction, et ce essentiellement grâce au succès du premier protocole expérimental de distribution de clefs quantiques [\underline{BBBSS90}]... Depuis son développement est spectaculaire et son principe a été décrit dans la pluspart des magazines de vulgarisation comme Scientific American [Wal89, \underline{BBE92}], The Economist [Got89], New Scientist [Deu89], Science News [Pet90], ou Pour la science [Del92].

1OBLIVIOUS TRANSFER, ou transfert équivoque, est une primitive permettant d’entremêler deux messages d’une façon telle qu’on ne puisse en lire qu’un, et qu’en le lisant, on rende l’autre illisible.

1.3 Résultats fondamentaux de mécanique quantique pour la suite...

1.3.1 Notions - Polarisation d’un photon

On considérera toujours des photons de même longueur d’onde.

Comme la lumière, on peut polariser des photons avec le même genre de matériel. Ainsi, on utilisera des lames (ou filtres) polarisantes et quart d’onde pour obtenir des polarisations dans une direction fixée ou circulaires... On supposera dans toute la suite des photons polarisés uniquement dans une direction fixée, par conséquent un photon sera entièrement caractérisé par son angle de polarisation.

Formellement, la mécanique quantique représente l’état interne d’un système quantique (comme la polarisation d’un photon) par un vecteur unitaire dans un espace de Hilbert. La dimension de l’espace de Hilbert dépend de la complexité du système. Chaque mesure physique pouvant être effectuée sur ce système correspond à un opérateur diagonalisant en base hilbertienne, appelé une observable, tel que les résultats possibles d’une mesure soient les valeurs propres de l’observable associée, et tel que l’état après une mesure soit sa projection normalisée avant mesure sur le sous-espace propre associé à la valeur propre du résultat. Le nombre de résultats possibles est donc limité par la dimension de l’espace de Hilbert.

L’espace de Hilbert d’un photon polarisé dans une direction et isolé est de dimension 2, identifié à ^{2} muni du produit scalaire canonique ⟨|⟩. On caractérisera l’état d’un photon de polarisation θ (par rapport à l’horizontale) par le vecteur polarisation cos θ|↔⟩ + sin θ| ↕⟩ (où (|↔⟩, | ↕⟩) est la base canonique de ^{2}); on ira jusqu’à identifier un photon avec son vecteur polarisation, et on notera |θ⟩ l’état d’un photon polarisé suivant la direction θ et ⟨θ| = |θ⟩^{∗} (cf. appendice).

1.3.2 Définitions - Résultats

Pour mesurer la polarisation, θ, d’un photon, on peut le faire passer par une lame polarisante orientée de φ de laquelle il ressort (polarisé à φ) avec une probabilité de cos^{2}(θ − φ). En fait on utilise un prisme de calcite de Wollaston orienté de φ duquel le photon ressort d’un coté (et polarisé à φ) avec une probabilité de cos^{2}(θ − φ) = ⟨φ|θ⟩ ou de l’autre (et polarisé à φ + \frac{π}{2} ) avec une probabilité de sin^{2}(θ − φ) = ⟨φ|θ + π/2⟩.

\underline{Proposition} 1.1— Il est impossible de déterminer exactement la polarisation d’un photon sans d’autres informations supplémentaires sur ce photon. De plus, en accord avec la mécanique quantique, la méthode exposée ci-dessus est la meilleure qui puisse être pour mesurer la polarisation d’un unique photon.

Démonstration:

Soit A l’observable associée à une certaine technique de mesure de la polarisation d’un photon. Il existe θ ∈ [0, 2π[ tel que la matrice de A soit, dans la base orthonormée (|θ⟩, |θ + π/2⟩), diag(α, β). Ceci correspond à prendre un calcite orienté de θ, et à associer le résultat α si le photon ressort polarisé à θ et β sinon.

\underline{Definition} 1.1— (|φ⟩, |ψ⟩) est une base si il existe une mesure fiable permettant de dissocier les états |φ⟩ et |ψ⟩. On parlera de mesure dans la base (|φ⟩, |ψ⟩) et on notera ψ = φ^{⊥}.

Remarque : Si θ est un angle, alors (|θ⟩, |θ + π/2⟩) est une base. Il suffit de considérer comme mesure celle du calcite orienté de θ.

\underline{Definition} 1.2— Soient (|φ⟩, |φ^{⊥}⟩), (|ψ⟩, |ψ^{⊥}⟩) deux bases. On dira qu’elles sont conjuguées si pour un photon dans {|φ⟩, |φ^{⊥}⟩} (resp. {|ψ⟩, |ψ^{⊥}⟩}) une mesure dans la base (|ψ⟩, |ψ^{⊥}⟩) (resp. (|φ⟩, |φ^{⊥}⟩)) est complètement aléatoire et entraîne la perte de toute information.

Notations : On notera certains états de polarisation comme suit :

– polarisation horizontale définie par le vecteur |↔⟩.

– polarisation verticale définie par le vecteur | ↕⟩.

– polarisation à \frac{π}{4} définie par le vecteur |↗ ↙⟩.

– polarisation à \frac{3π}{4} définie par le vecteur |↘ ↖⟩.

– polarisation à \frac{π}{8} définie par le vecteur |B⟩. La base (|B⟩, |B^{⊥}⟩) est appelée base de Breidbart. On notera par commodité κ = cos(π/8) (rq : κ^{2} ≈ 85%).

On notera aussi les bases associées ↕ ↔= (|↔⟩, | ↕⟩) et ↗ ↙ ↘ ↖= (|↗ ↙⟩, |↘ ↖⟩).

\underline{Proposition} 1.2— Les bases ↕ ↔ et ↗ ↙ ↘ ↖ sont conjuguées.

1.3.3 Clônage d’un état quantique

\underline{Theoreme} 1.1 (Wootters-Zurek [WZ82])— On ne peut pas clôner “directement” (sans faire de mesure) un état quantique.

Démonstration: On donne ici une démonstration simplifiée en oubliant quelques problèmes de formalisme... Soient |φ⟩, |ψ⟩ des états quantiques normés et U un opérateur unitaire de clônage de (E, ⟨|⟩).

On a donc :

U|φ⟩ = |φ⟩|φ⟩ : vecteur de E ⊗ E
U|ψ⟩ = |ψ⟩|ψ⟩

D’où en faisant le produit scalaire des deux expressions et en utilisant le fait que U est unitaire on a :

⟨φ|ψ⟩ = ⟨φ|ψ⟩^{2}

Ce qui est absurde d’après l’inégalité de Schwarz si |φ⟩ et |ψ⟩ sont ni égaux, ni orthogonaux.

1.3.4 Le paradoxe d’E.P.R.

On pourra consulter pour plus d’informations [EPR35], voici néanmoins une première approche de ce paradoxe...

Il s’agit de l’existence de photons émergeant d’un même point (provenant de la désexcitation d’un atome), fuyant dans deux directions opposées, et surtout étant corrélés, c’est-à-dire qu’après toute mesure dans une certaine base de l’un des deux photons, la mesure de l’autre photon dans la même base donnera \underline{toujours} le même résultat...

On pourrait donc croire que l’information du résultat de la première mesure se propage instantanément (i.e. plus vite que la lumière). Or le résultat de la première mesure est \underline{aléatoire}, donc on ne transmet pas une information voulue mais aléatoire, ce qui n’est pas en contradiction avec les fondements de la mécanique quantique!

On appellera une telle paire de photons corrélés des photons EPR, qui servirons dans la suite pour envisager certaines attaques des participants...

1.4 Le one-time pad (version binaire)

\underline{Algorithme} 1.1— (codage(A, B))

– message binaire à coder A = a_{1}a_{2} … a_{n}.

– clef binaire de codage B = b_{1}b_{2} … b_{n}.

– renvoyer le message codé C = c_{1}c_{2} … c_{n} avec ∀i ∈ {1, 2, …, n} , c_{i} = a_{i} ⊕ b_{i}.

\underline{Algorithme} 1.2— (décodage(C, B))

– message binaire codé C = c_{1}c_{2} … c_{n}.

– clef binaire associée B = b_{1}b_{2} … b_{n}.

– renvoyer le message décodé A = a_{1}a_{2} … a_{n} avec ∀i ∈ {1, 2, …, n} , a_{i} = c_{i} ⊕ b_{i}.

\underline{Proposition} 1.3— Dans le one-time pad, si la clef est aussi longue que le message à coder et si elle n’est utilisée qu’une seule fois, alors il est impossible de décoder le message sans connaître la clef.

Démonstration: Il suffit de remarquer que B ↦ décodage(B, C) est une bijection de {0, 1}^{n}, par conséquent,

sans aucune information sur la clef de codage, il est impossible de décoder un message utilisant le one-time pad.

Remarques :

1. L’inconvénient du one-time pad est qu’Alice et Bob doivent avoir chacun une copie de la clef secrète, et que cette copie est longue si l’on veut transmettre de longs messages... De plus, il faut pouvoir la garder secrète jusqu’au moment de son utilisation.

2. Son avantage réside dans le fait que la clef en elle même peut être quelconque, on peut donc remplacer le problême de transmission d’un message binaire secret fixé de longueur n en la distribution d’une clef quelconque de longueur n, ce que l’on va pouvoir faire grâce au principe d’incertitude de la mécanique quantique... Il suffira ensuite de transmettre par un canal infalsifiable codage(message,clef), qui ne donne aucune information sur message si clef n’est pas révélée.

3. Pour simplifier, on notera codage(A, B)=décodage(A, B)=A ⊕ B.

1.5 Le transfert quantique

Méthode

On suppose l’existence de canaux permettant le transit de photons sans interférences internes, mais ne garantissant pas leur sécurité vis-à-vis d’une éventuelle “écoute” de la ligne...

Alice envoie (et on suppose cela possible) à Bob un unique photon polarisé d’un angle θ fixé et connu d’Alice uniquement.

A la réception de ce photon, Bob lit l’information du photon, qui est sa polarisation, en le faisant passer dans un prisme de calcite de Wollaston orienté de φ. Bob considère avoir reçu le bit 0 si le photon ressort dans la direction de polarisation φ et 1 sinon.

Protocole

\underline{Protocole} 1.1— (Quantum Transfert)

– Alice envoie à Bob un photon |θ⟩.

– Bob mesure le photon reçu dans une base (|φ⟩, |φ^{⊥}⟩).

– Bob fixe le bit x ← \{ \begin{matrix}0 & si la mesure donne φ \\ 1 & sinon \end{matrix} .

Modélisation

Tout se passe comme s’il éxistait une machine QT régissant les communications entre Alice et Bob de la manière suivante :

– Alice envoie un angle θ à QT.

– Bob envoie un angle φ à QT.

– QT envoie le bit x à Bob tel que Pr(x = 0) = cos^{2}(θ − φ).

\underline{Proposition} 1.4— QT est inviolable i.e. :

– Bob n’apprend rien sur θ.

– Alice n’apprend rien sur φ et x.

Démonstration:

– D’après la proposition 1.1 Bob a le maximum d’informations en suivant le protocole, i.e. la variable x représente le maximum d’informations sur θ. Avant mesure, Bob n’a aucune information sur θ donc pour lui

Pr(x = 0) = ∫_{0}^{2π}cos^{2}(θ − φ) dθ = \frac{1}{2} = Pr(x = 1)

Donc le résultat est complètement aléatoire, donc aucune information n’est transmise.

– Citons le lemme suivant, que nous admettrons, et dont nous nous servirons dans le reste du mémoire.

\underline{Lemme} 1.1— Le maximum d’informations qu’Alice peut avoir sur ce qu’advient un photon émis, qu’elle ne peut plus observer directement, est son photon corrélé dans une paire EPR.

Alice pourrait donc stocker le photon corrélé à celui émis jusqu’à ce que Bob le mesure. Mais on se trouve alors dans la situation inverse : tout ce passe comme si Bob avait envoyé à Alice un photon de polarisation φ, qu’Alice ignore; la seule chose qu’elle peut faire étant de mesurer le photon gardé pour un θ choisi quelconque!

Protocoles cryptographiques

2.1 Présentation

Deux participants (appelés Alice et Bob), qui ne se font pas confiance, veulent effectuer des tâches utilisant des informations secrètes provenant des deux parties, et ce sans pour autant se les révéler mutuellement. On modèlisera les participants par des machines de Turing probabilistes mais pas forcément bornées polynômialement par le temps, contrairement à ce qu’on fait généralement dans ce genre de situation. On aura donc en fait des preuves de sécurité même si P = N P, ce qui n’est pas habituellement le cas.

Nous allons donc expliciter des primitives cryptographiques fondamentales qui permettent d’établir de nombreux protocoles cryptographiques plus élaborés : mise en gage d’un bit (bit commitment scheme)^{(1)}, transfert équivoque (oblivious transfer (OT))^{(2)}, transfert inconscient (one-out-of-two oblivious tansfer (\binom{2}{1} -OT)).

Exemples d’applications de ces primitives :

– (1) ⟶ tirage à pile ou face à distance (coin tossing protocols).

– (1) ⟶ preuve à divulgation nulle (zero-knowledge proofs): Alice veut prouver la validité d’un prédicat à Bob sans lui révéler d’informations sur le fait que le prédicat est juste.

– (2) ⟶ Evaluation de fonctions avec sécurité des données des participants (secure two party computation) : On considère une fonction (x, y) ↦ f(x, y) à deux paramètres et calculable en un temps polynômial. Alice connait x et Bob y. On veut établir un protocole entre Alice et Bob leur permettant d’évaluer f(x, y) sans révéler d’informations autre que f(x, y) aux participants.

Signalons que nous allons travailler sur des bits, mais que l’implémentation sur des entiers quelconques et donc sur n’importe quel alphabet fini ne pose aucun problème. Enfin, le lecteur trouvera une vaste littérature sur les applications de ces primitives dont il trouvera une bibliographie représentative dans [\underline{Cré93}].

2.2 Mise en gage d’un bit

2.2.1 Définition

\underline{Definition} 2.1— On dit qu’Alice met en gage un bit x à Bob quand Alice donne une représentation de x à Bob telle que :

– Bob ne peut en tirer aucune information sur x.

– Alice peut à tout moment révéler x avec preuve de sa bonne foi.

Les conditions de mise en gage sont :

– la sécurité d’une Alice honnête face à un Bob malhonnête.

– la sécurité d’un Bob honnête face à une Alice malhonnête.

En effet, on ne cherche qu’à garantir les gens honnêtes face à des gens malhonnêtes, si tout le monde est malhonnête l’intérêt est nul. En fait on garantit la sécurité d’un participant s’il suit le protocole à la lettre. Il en sera de même pour les autres parties de ce chapitre...

Remarque : En fait, on montrera que les chances de réussites d’attaques des participants sont exponentiellement faibles en la complexité des protocoles.

2.2.2 Une version simplifiée

Nous proposons ici une des premières mises en gage quantiques explicitée par Bennett et Brassard dans [\underline{BB84}].

Voici tout d’abord la première partie du protocole qui permet à Alice de mettre en gage un bit x à Bob; n est un entier très grand fixé. On notera [a_{0}, a_{1}, …, a_{n}]_{i} = a_{i}.

\underline{Protocole} 2.1— BB-commit(x)

1. Alice choisit aléatoirement un vecteur de n bits C ← (c_{1}, c_{2}, …, c_{n}).

2. Bob choisit aléatoirement un vecteur de n bits B′ ← (b′_{1}, b′_{2}, …, b′_{n}).

3. Alice choisit sa base de polarisation (|φ⟩, |φ^{⊥}⟩) ← [ ↕ ↔, ↗ ↙ ↘ ↖]_{x}.

4. DO_{i=1}^{n}:

– Alice envoie un photon π_{i} de polarisation [|φ⟩, |φ^{⊥}⟩]_{c_{i}} à Bob.

– Bob mesure le photon π_{i} reçu dans la base (|φ′_{i}⟩, |φ′_{i}^{⊥}⟩) ← [ ↕ ↔, ↗ ↙ ↘ ↖]_{b′_{i}}.

– Bob fixe c′_{i} ← \{ \begin{matrix}0 & si la mesure donne φ′_{i} \\ 1 & sinon \end{matrix} .

5. Bob établie C′ ← (c′_{1}, c′_{2}, …, c′_{n}).

\underline{Proposition} 2.1— BB-commit a une complexité en n.

\underline{Theoreme} 2.1— Si Alice est honnête, Bob ne peut pas estimer la valeur de x, i.e. Pr(x = 0 | C′) = Pr(x = 1 | C′) = \frac{1}{2}.

Démonstration:

Nous allons exposer deux démonstrations, la première, plus concrète, n’utilise pas beaucoup d’outils, la deuxième, plus élégante, utilise les matrices densités (cf. appendice). J’ai tenu à faire la démonstration de ce théorème en détails, que je n’ai trouvée nulle part, car je pense que sa compréhension permet de mieux assimiler celles qui suivent.

1. Bob ne peut que mesurer les photons arrivants : le fait de les conserver ne lui apporterait rien, de plus il ne peut pas les clôner. Ne supposons pas les |φ_{i}⟩_{i} dans {|↔⟩, | ↕⟩, |↗ ↙⟩, |↘ ↖⟩}, mais dans {|θ⟩; θ ∈ [0, 2π[}. Avec ce modèle nous traitons toutes les attitudes possibles de Bob. Les seules informations qu’il peut tirer sont donc contenues dans C′.

On suppose x fixé. Si Pr(c_{i} = 0) = Pr(c_{i} = 1) = \frac{1}{2} alors :

Pr(c′_{i} = 0) = \frac{cos^{2}(ψ_{i} − φ) + cos^{2}(ψ_{i} − φ^{⊥})}{2} = \frac{1}{2} = Pr(c′_{i} = 1)

Donc la i-ème mesure donne un résultat aléatoire pour Bob. Donc la valeur de x n’influe en rien la valeur de C′. Donc si on appelle C′_{0} la valeur de la variable C′, on a :

Pr(C′ = C′_{0} | x = 0) = Pr(C′ = C′_{0} | x = 1)

donc en utilisant la formule de Bayes on a :

Pr(x = 0 | C′ = C′_{0}) = \frac{Pr(C′ = C′_{0} | x = 0) × Pr(x = 0)}{Pr(C′ = C′_{0} | x = 0) × Pr(x = 0) + Pr(C′ = C′_{0} | x = 1) × Pr(x = 1)}
= \frac{1}{2}
= Pr(x = 1 | C′ = C′_{0})

2. Soit ρ_{0} la matrice densité décrivant le mélange statistique des états envoyés à Bob pour représenter x = 0 à l’étape 4 du protocole BB-commit:

ρ_{0} = ⨂_{i=1}^{n} (\frac{1}{2}|↔⟩⟨↔ | + \frac{1}{2}| ↕⟩⟨ ↕ |) = ⨂_{i=1}^{n} ( \begin{matrix}\frac{1}{2} & 0 \\ 0 & \frac{1}{2} \end{matrix} )

et pour x = 1 :

ρ_{1} = ⨂_{i=1}^{n} (\frac{1}{2}|↗ ↙⟩⟨↗ ↙ | + \frac{1}{2}|↘ ↖⟩⟨↘ ↖ |) = ρ_{0}

On constate que la matrice obtenue pour BB-commit(0) coïncide à celle obtenue pour BB-commit(1). Un théorème de mécanique quantique dit que deux mélanges qui ont les mêmes matrices densités ne peuvent être distingués par aucune mesure quantique (cf. théorème 5.2).

Voici maintenant la deuxième partie du protocole qui permet à Alice de révéler x à Bob:

\underline{Protocole} 2.2— BB-unveil(x, C, B′, C′)

1. Alice révèle x et C à Bob.

2. Bob accepte si le prédicat [∀i ∈ {1, 2, …, n} , [(b′_{i} = x) ⇒ (c′_{i} = c_{i})]] est vrai et refuse sinon.

\underline{Proposition} 2.2— BB-unveil a une complexité en n.

Remarque : Si Alice est honnête et s’il n’y a pas d’erreurs de transmission, alors Bob acceptera toujours dans le protocole ci-dessus.

Exemple :

\begin{matrix}1. & ↗ ↙ & ↕ & ↘ ↖ & ↔ & ↕ & ↕ & ↔ & ↔ & ↘ ↖ & ↗ ↙ & ↕ & ↘ ↖ & ↗ ↙ & ↗ ↙ & ↕ \\ 2. & ↕ ↔ & ↗ ↙ ↘ ↖ & ↗ ↙ ↘ ↖ & ↕ ↔ & ↕ ↔ & ↗ ↙ ↘ ↖ & ↗ ↙ ↘ ↖ & ↕ ↔ & ↗ ↙ ↘ ↖ & ↕ ↔ & ↗ ↙ ↘ ↖ & ↗ ↙ ↘ ↖ & ↗ ↙ ↘ ↖ & ↗ ↙ ↘ ↖ & ↕ ↔ \\ 3. & ↕ & ↗ ↙ & ↘ ↖ & ↔ & ↕ & ↗ ↙ & ↗ ↙ & ↔ & ↘ ↖ & ↕ & ↘ ↖ & ↘ ↖ & ↗ ↙ & ↗ ↙ & ↕ \\ 4. & ? & ? & √ & √ & √ & ? & ? & √ & √ & ? & ? & √ & √ & √ & √ \end{matrix}

1. Alice envoie à Bob une suite aléatoire de photons polarisés horizontalement (↔), verticalement ( ↕), à π/4 (↗ ↙) ou à 3π/4 (↘ ↖).

2. Bob mesure la polarisation de chacun de ces photons aléatoirement, soit de façon rectiligne ( ↕ ↔), soit de façon diagonale (↗ ↙ ↘ ↖).

3. Résultat des mesures de Bob.

4. Alice révèle à Bob les bases et polarisations de chacun des photons envoyés. Bob teste alors, quand il avait fait le bon choix de base, s’il a la même polarisation que celle que lui a annoncée Alice. Si les tests sont concluants, Bob accepte.

On suppose Bob honnête mais Alice malhonnête, i.e. Alice veut être libre de révéler à sa guise 0 ou 1 (sans avoir à tenir compte de sa mise en gage). Quelles sont les chances de réussite d’Alice?

Modélisation d’une stratégie d’attaque pour Alice

On suppose qu’Alice envoie des photons π_{i} de polarisation intrinsèque φ_{i} ∈ [0, 2π[, et que pour révéler x ∈ {0, 1}, Alice utilise le vecteur C^{x} dans BB-unveil.

On dira que la stratégie est réussie quand :

∀i ∈ {1, 2, …, n} , [(b′_{i} = 0) ⇒ (c′_{i} = c_{i}^{0})] ∧ [(b′_{i} = 1) ⇒ (c′_{i} = c_{i}^{1})]
i.e. quand ∀i ∈ {1, 2, …, n} , c′_{i} = c_{i}^{b′_{i}}

\underline{Theoreme} 2.2— Dans ce modèle, si Bob est honnête, Pr(stratégie réussie) ≤ κ^{2n}.

Démonstration: Je me suis encore attaché ici à faire avec une démonstration propre dans ce cas simple car

les mêmes méthodes seront réutilisées utltérieurement.

Traçons le tableau des probabilités de validité du prédicat [c′_{i} = c_{i}^{b′_{i}}]:

Pr(c′_{i} = c_{i}^{b′_{i}})  c_{i}^{b′^{i}} = 0  c_{i}^{b′^{i}} = 1
b′_{i} = 0  cos^{2} φ_{i}  cos^{2}(φ_{i} − π/2)
b′_{i} = 1  cos^{2}(φ_{i} − π/4) cos^{2}(φ_{i} − 3π/4)

D’où une stratégie optimale :

• c_{i}^{0} = c_{i}^{1} = 0 : Pour ne privilégier ni x = 0 ni x = 1, i.e. ni b′_{i} = 0 ni b′_{i} = 1 on prend φ_{i} = π/8.

• c_{i}^{0} = c_{i}^{1} = 1 ⟶ φ_{i} = 5π/8.

• c_{i}^{0} = \overline{c_{i}^{1}} ⟶ φ_{i} = 3π/8.

Dans tous les cas on a donc : Pr(c′_{i} = c_{i}^{b′_{i}}) = κ^{2}(= cos^{2}(π/8)). Donc la stratégie optimale est réussie avec une probabilité P:

P = ∏_{i=1}^{n} Pr(c′_{i} = c_{i}^{b′_{i}}) = κ^{2n}

Une attaque possible d’Alice : l’attaque EPR

Supposons qu’Alice utilise des paires de photons EPR. Alice n’a qu’à suivre le protocole suivant pour avoir une stratégie réussie :

\underline{Protocole} 2.3— BB-commit’

1. Alice choisit aléatoirement un vecteur de n bits C ← (c_{1}, c_{2}, …, c_{n}).

2. Bob choisit aléatoirement un vecteur de n bits B′ ← (b′_{1}, b′_{2}, …, b′_{n}).

3. DO_{i=1}^{n}:

– Alice produit une paire de photons EPR (π_{i}, π′_{i}) et envoie π_{i} à Bob tout en stoquant π′_{i}.

– Bob mesure le photon π_{i} reçu dans la base (|φ′_{i}⟩, |φ′_{i}^{⊥}⟩) ← [ ↕ ↔, ↗ ↙ ↘ ↖]_{b′_{i}}.

– Bob fixe c′_{i} ← \{ \begin{matrix}0 & si la mesure donne φ′_{i} \\ 1 & sinon \end{matrix} .

4. Bob établie C′ ← (c′_{1}, c′_{2}, …, c′_{n}).

Lorsqu’Alice désire révéler x ∈ {0, 1} de son choix à Bob, elle fait :

– Alice choisit sa base de polarisation (|φ⟩, |φ^{⊥}⟩) ← [ ↕ ↔, ↗ ↙ ↘ ↖]_{x}

– DO_{i=1}^{n}:

– Alice mesure le photon π′_{i} dans la base (|φ⟩, |φ^{⊥}⟩).

– Alice fixe c_{i} ← \{ \begin{matrix}0 & si la mesure donne φ_{i} \\ 1 & sinon \end{matrix} .

– Alice établie C ← (c_{1}, c_{2}, …, c_{n}).

Puis il suffit à Alice d’effectuer BB-unveil(x) avec Bob.

Remarque :

– Actuellement, le stoquage de photons est impossible sauf durant des temps très courts, donc cette attaque est irréalisable. Donc pratiquement, ce protocole est incassable des deux parties; néanmoins d’un point de vue théorique, il est important de trouver un protocole parfaitement incassable.

– Une solution pour lutter contre l’attaque EPR serait donc d’imposer une condition aux polarisations des photons envoyés pour forcer Alice à les polariser effectivement (i.e. d’avoir un unique état intrinsèque pour chaque photon envoyé). Une telle solution sera mise en évidence dans les protocoles qui suivent.

Bilan

\underline{Theoreme} 2.3 En théorie, la mise en gage de [\underline{BB84}] est inviolable par Bob et est violable par Alice si et seulement si Alice peut générer des paires EPR et stocker des photons.

Démonstration: Il suffit de constater qu’après avoir envoyé les photons π_{i}, la seule trace qu’Alice peut en

garder est leurs éventuels photons corrélés dans des paires EPR, et de rassembler ce qui précède.

Autres problèmes

Outre le problème théorique de l’attaque EPR, il y a des problèmes pratiques. On peut en éliminer certains facilement, d’autres non. Pour commencer, il n’est pas raisonnable de faire dans BB-unveil : [∀i ∈ {1, 2, …, n} , [(b′_{i} = b) ⇒ (c_{i} = c′_{i})]]. En effet, les erreurs de transmission ne peuvent être absentes en pratique, d’autant plus que les appareils utilisés sont très sensibles (cf. paragraphe 3.2.3). On a constaté dans l’appareil actuel utilisé pour la distribution de clefs quantiques [\underline{BBBSS90}] qu’il était raisonnable d’espérer 4% d’erreurs. Il faut donc mettre à la place dans BB-unveil [∀i ∈ {1, 2, …, n} , [(b′_{i} = b) ⇒_{90%} (c′_{i} = c_{i})]]. Le seul prix à payer étant que le paramètre n, qui sécurise le protocole, doit être choisi plus grand pour atteindre la même infime probabilité de réussite de tricherie.

L’autre problème pratique est beaucoup plus sérieux : il est très difficile d’envoyer en pratique dans BB-commit des photons isolés. Il est beaucoup plus facile d’envoyer de faibles impulsions de photons polarisés comme dans l’appareil expérimental de distribution de clefs. Malheureusement, celles-ci contiennent parfois plus d’un photon, et tous les photons d’une même impulsion ont la même polarisation, et ceci est contraignant : quand Bob lit une impulsion qui contient plus d’un photon dans la base (|φ⟩, |φ^{⊥}⟩), si Bob détecte des photons dans les deux directions du calcite alors l’impulsion est polarisée dans la base conjuguée à (|φ⟩, |φ^{⊥}⟩) dans l’ensemble { ↕ ↔, ↗ ↙ ↘ ↖}, sinon l’impulsion est polarisée dans la base (|φ⟩, |φ^{⊥}⟩); donc dans les deux cas Bob découvre la valeur de x. Il n’y a pas de solutions à ce problème avec cette mise en gage, cependant le protocole qui suit restera fiable lorsqu’il n’y aura qu’un petit nombre de multiphotons émis.

2.2.3 Une version un peu plus évoluée

Cette version, tirée de [\underline{BC91}], présente l’avantage de résister à l’attaque EPR et de rester fiable en présence de multiphotons.

\underline{Protocole} 2.4— BC-commit(x)

1. Alice choisit aléatoirement une matrice booléenne n × n C = (c_{i,j}) telle que

∀i ∈ {1, 2, …, n} , ⨁_{j=1}^{n} c_{i,j} = x

2. Alice choisit aléatoirement une matrice booléenne n × n B = (b_{i,j}).

3. Bob choisit aléatoirement une matrice booléenne n × n B′ = (b′_{i,j}).

4. DO_{i=1}^{n} DO_{j=1}^{n}:

– Alice fixe la base (|φ_{i,j}⟩, |φ_{i,j}^{⊥}⟩) ← [ ↕ ↔, ↗ ↙ ↘ ↖]_{b_{i,j}}

– Alice envoie un photon π_{i,j} de polarisation [|φ_{i,j}⟩, |φ_{i,j}^{⊥}⟩]_{c_{i,j}} à Bob.

– Bob mesure le photon π_{i,j} reçu dans la base (|φ′_{i_{j}}⟩, |φ′_{i_{j}}^{⊥}⟩) ← [ ↕ ↔, ↗ ↙ ↘ ↖]_{b′_{i,j}}.

– Bob fixe c′_{i,j} ← \{ \begin{matrix}0 & si la mesure donne φ′_{i,j} \\ 1 & sinon \end{matrix} .

\underline{Proposition} 2.3— BC-commit a une complexité en n^{2}.

\underline{Proposition} 2.4— Si les deux participants sont honnêtes on a : Pr(c′_{i,j} = c_{i,j}) = \frac{3}{4}.

\underline{Lemme} 2.1— Si Alice est honnête, Bob ne peut obtenir plus d’informations sur x que lire séparément chaque photon π_{i} reçu dans la base (|B⟩, |B^{⊥}⟩).

Démonstration:

Cette démonstration est très proche de celle du lemme 2.2, nous la ferons donc seulement à ce moment. Disons seulement que la démonstration utilise un deuxième protocole, qui révèle autant d’informations que celui-ci (preuve par les matrices densités), pour lequel le maximum d’informations est évidemment obtenu par la lecture séparée de chaque photon π_{i} reçu dans la base (|B⟩, |B^{⊥}⟩).

\underline{Theoreme} 2.4— Si Alice est honnête, il existe une constante α ∈ [0, 1[ telle que :

\frac{1}{2} − α^{n} ≤ \{ \begin{matrix}Pr(x = 0 | C′) \\ Pr(x = 1 | C′) \end{matrix} \} ≤ \frac{1}{2} + α^{n}

\underline{Protocole} 2.5— BC-unveil(x, B, C, B′, C′)

1. Alice révèle x, B et C à Bob.

2. Bob accepte si

\{ \begin{matrix}∀i ∈ \{1, 2, …, n\} , ⨁_{j=1}^{n} c_{i,j} = x. \\ ∀(i, j) ∈ \{1, 2, …, n\}^{2} , [(b′_{i,j} = b_{i,j}) ⇒ (c′_{i,j} = c_{i,j})]. \end{matrix}

et refuse sinon.

\underline{Proposition} 2.5— BC-unveil a une complexité en n.

Modélisation d’une stratégie d’attaque pour Alice

On suppose qu’Alice envoie des photons π_{i,j} de polarisation intrinsèque φ_{i,j} ∈ [0, 2π[, et que pour révéler x ∈ {0, 1}, Alice utilise les vecteurs B^{x} et C^{x} dans BC-unveil.

On dira que la stratégie est réussie quand :

∀i ∈ {1, 2, …, n} , [⨁_{j=1}^{n} c_{i,j}^{0} = 0] ⋀ [⨁_{j=1}^{n} c_{i,j}^{1} = 1]  (2.1)

et ∀(i, j) ∈ {1, 2, …, n}^{2} , [(b′_{i,j} = b_{i,j}^{0}) ⇒ (c′_{i,j} = c_{i,j}^{0})] ∧ [(b′_{i,j} = b_{i,j}^{1}) ⇒ (c′_{i,j} = c_{i,j}^{1})] (2.2)

\underline{Theoreme} 2.5— Dans ce modèle, si Bob est honnête, Pr(stratégie réussie) ≤ κ^{2n}.

Démonstration:

Tout d’abord, notons que le prédicat 2.1 implique que C^{0} et C^{1} diffèrent au moins d’une composante par ligne. Donc il y a au moins n bits différents dans ces deux matrices. Soit (i, j) tel que c_{i,j}^{0} ≠ c_{i,j}^{1}. Deux cas se présentent :

1. b_{i,j}^{0} = b_{i,j}^{1} = b. Quand b′_{i,j} = b, le prédicat 2.2 n’est pas satisfait pour (i, j), sinon il l’est. Or Pr(b′_{i,j} = b) = \frac{1}{2}, donc quelque soit le choix de φ_{i,j}, Pr(2.2 vrai pour (i, j)) = \frac{1}{2}.

2. b_{i,j}^{0} = \overline{b_{i,j}^{1}}. Donc une des deux égalitéd du prédicat 2.2 pour (i, j) sera à vérifier. Pour augmenter ses chances de réussite de vérifier 2.2 pour (i, j), Alice envoie un photon de polarisation φ_{i,j} qui doit augmenter simultanément ses chances de réussite si b′_{i,j} = 0 ou b′_{i,j} = 1. On en déduit donc comme dans l’étude similaire au 2.2.2, qu’il y a deux sous cas :

(a) b_{i,j}^{0} = \overline{c_{i,j}^{0}} ⇒ φ_{i,j} = \frac{7π}{8} .

(b) b_{i,j}^{0} = c_{i,j}^{0} ⇒ φ_{i,j} = \frac{π}{8} .

Ce qui entraine dans les deux cas Pr(2.2 vrai pour (i, j)) = κ^{2}.

Nous avons vu qu’il y avait au moins n paires (i, j) telles que c_{i,j}^{0} ≠ c_{i,j}^{1}, on peut donc conclure.

Remarque : Quelques soient les photons envoyés, ils ont intérêt à être comme dans le cas idéal de la demonstration précédente pour augmenter les chances d’Alice, donc en particulier d’être polarisés de façon intrinsèque et de ne pas provenir par exemple d’une paire de photon EPR. Donc \underline{le théorème 2.5 est vrai pour n’importes quels photons envoyés}.

Une attaque possible de Bob : mesures cohérentes

Nous connaissons l’existence de fonctions f telles que, étant donnés deux photons de polarisations φ_{1} et φ_{2}, il existe un moyen d’avoir plus d’informations sur f(φ_{1}, φ_{2}) qu’en appliquant directement f aux résultats des mesures séparées de φ_{1} et φ_{2}. Ainsi s’il était possible de faire ceci avec l’opérateur ⊕, cette mise en gage serait non fiable pour Alice... Ce problème était ouvert à l’époque de la rédaction de [\underline{BC91}], mais le lemme 2.1, établie dans [\underline{BCJL93}] permet de répondre à ce problème par la négation.

Bilan

\underline{Theoreme} 2.6 En théorie, la mise en gage de [\underline{BC91}] est inviolable par Alice et Bob.

Comparaisons entre les deux protocoles

Une étude un peu plus poussée montre que ce protocole reste parfaitement fiable s’il y a quelques multiphotons (pour un n suffisament grand), de plus il résiste à l’attaque EPR. Cependant, il ne résiste pas aux erreurs de transmission car si Bob tolére occasionellement c′_{i,j} ≠ c_{i,j} lorsque b′_{i,j} = b_{i,j}, Alice peut facilement tricher (n est très grand, donc une erreur par ligne de C′ est acceptable ce qui permet facilement de changer ∀i ∈ {1, 2, …, n} , ⨁_{j=1}^{n} c_{i,j} = x).

Donc théoriquement ce protocole est inviolable, mais pratiquement les deux protocoles se complètent : le protocole de [\underline{BB84}] souffre des multiphotons mais pas des erreurs de transmisson, et celui de [\underline{BC91}] souffre de l’inverse!

2.2.4 Une application : le tirage à pile ou face à distance

Il s’agit donc d’une technique permettant de jouer à pile ou face par téléphone “quantique” en implémentant des primitives comme celles exposées précédemment.

Voici tout d’abord une première version étant donnée une primitive de mise en gage se décomposant en commit et unveil.

\underline{Protocole} 2.6— BB-cointoss

1. Alice choisit aléatoirement un bit x_{0} et utilise commit(x_{0}) avec Bob.

2. Bob choisit aléatoirement un bit x_{1} et l’envoie (normalement) à Alice.

3. Alice utilise unveil(x_{0}) avec Bob.

4. Bob a gagné si et seulement si x_{1} = x_{0}.

\underline{Proposition} 2.6— BB-cointoss a la même complexité que celle de commit plus celle de unveil.

\underline{Theoreme} 2.7— Ce protocole peut être violé si et seulement si la primitive de mise en gage utilisée peut l’être.

Citons cette autre version qui avait une importance lorsqu’on ne savait pas si l’attaque des mesures cohérentes avait lieu d’être:

\underline{Protocole} 2.7— BC-cointoss

1. Alice choisit aléatoirement un bit x_{0} et utilise BB-commit(x_{0}) avec Bob.

2. Bob choisit aléatoirement un bit x_{1} et utilise BC-commit(x_{1}) avec Alice (les rôles d’Alice et Bob sont ici provisoirement interchangés).

3. Alice utilise BB-commit(x_{0}) avec Bob.

4. Bob utilise BC-commit(x_{1}) avec Alice.

5. Bob gagne si et seulement si x_{1} = x_{0}.

\underline{Proposition} 2.7— BC-cointoss a une complexité en n^{2}.

\underline{Theoreme} 2.8— Seule Alice peut violer ce protocole, et elle peut le violer si et seulement si elle peut implémenter l’attaque EPR (et l’attaque des mesures cohérentes).

2.2.5 La dernière version actuelle

Ce protocole est extrait de [\underline{BCJL93}], non encore publié, mais dont une première version m’a été donnée par Claude Crépeau que je remercie vivement. Il s’agit d’une amélioration du protocole décrit dans [\underline{BC91}], qui permet une implémentation pratique et qui de plus solutionne le problème des mesures cohérentes du précédent protocole. Les démonstrations en étant d’autant plus pointues et faisant appel à des résultats de mécanique quantique et de probabilités, nous nous contenterons donc d’en exposer les grandes lignes.

On notera X⊙Y le produit scalaire booléen, i.e. si X = (x_{1}, x_{2}, …, x_{n}) et Y = (y_{1}, y_{2}, …, y_{n}) alors

X ⊙ Y = ⨁_{i=1}^{n} x_{i} ∧ y_{i}

Soit ε un majorant du taux d’erreurs du canal quantique, i.e. la probabilité qu’un photon polarisé |φ⟩ soit détecté comme étant |φ^{⊥}⟩.

On note d_{H}(X, Y) = |{i | x_{i} ≠ y_{i}}|, la distance de Hamming.

\underline{Definition} 2.2— On dira qu’une matrice binaire (booléenne) M vérifie la propriété P (n, k, d), où n,k et d sont des entiers naturels, si elle vérifie les propriétés si dessous :

– M est de dimension n × k.

– ∀(X, Y) ∈ {0, 1}^{k} , [(X ≠ Y) ⇒ (d_{H}(MX, MY) ≥ d)]

\underline{Theoreme} 2.9— Une matrice binaire aléatoire M de dimension n × k vérifiera la propriété P (n, k, d) sauf avec une probabilité 2^{−αn} tant que

k < n − H(d/n) − αn

où H est la fonction d’entropie définie par H(p) = p lg(\frac{1}{p}) + (1 − p) lg(\frac{1}{1−p}).

Démonstration:

cf. [MS77].

Appication : Si ε < 1%, alors on prend k/n = 0.52 et on en déduit qu’en choisissant une matrice binaire M de dimension n × 0.52n, M vérifie P (n, 0.52n, 10εn) sauf avec la probabilté 2^{−0.1n}. Notons que dans le cas défavorable, trouver des vecteurs contradisant P est un problème d’autant plus difficile que n est grand.

La mise en gage proprement dite :

\underline{Protocole} 2.8— BCJL-commit(x)

1. Bob choisit aléatoirement une matrice (n, k) booléenne M vérifiant P (n, k, d), où (n, k, d) vérifie d/n > 10ε et k/n = 0.52, et l’annonce à Alice.

2. Alice choisit aléatoirement un vecteur de n bits R et l’annonce à Bob.

3. Alice choisit aléatoirement un vecteur de k bits Y tel que C ⊙ R = x où C = DY.

4. DO_{i=1}^{n}:

– Alice choisit aléatoirement un bit b_{i} et définit sa base (|φ_{i}⟩, |φ_{i}^{⊥}⟩) ← [ ↕ ↔, ↗ ↙ ↘ ↖]_{b_{i}}.

– Alice envoie à Bob le photon π_{i} de polarisation [|φ_{i}⟩, |φ_{i}^{⊥}⟩]_{c_{i}}.

5. DO_{i=1}^{n}:

– Bob choisit aléatoirement un bit b′_{i} et mesure π_{i} dans (|φ′_{i}⟩, |φ′_{i}^{⊥}⟩) ← [ ↕ ↔, ↗ ↙ ↘ ↖]_{b′_{i}}.

– Bob fixe c′_{i} ← \{ \begin{matrix}0 & si la mesure donne φ′_{i} \\ 1 & sinon \end{matrix} .

\underline{Proposition} 2.8— Si on ne tient pas compte du choix de M, BCJL-commit a une complexité en n.

\underline{Lemme} 2.2— Si Alice est honnête, Bob ne peut obtenir plus d’informations sur x que lire séparément chaque photon π_{i} reçu dans la base (|B⟩, |B^{⊥}⟩).

Démonstration:

Considérons le protocole suivant différent du précédent à la 4-ième étape uniquement :

\underline{Protocole} 2.9— BCJL-commit’(x)

1….
2….
3….

4. DO_{i=1}^{n}:

– Alice choisit aléatoirement un bit b_{i} tel que Pr(b_{i} = 0) = κ^{2}.

– Alice envoie à Bob le photon π_{i} de polarisation (|B⟩, |B^{⊥}⟩)_{c_{i}⊕b_{i}}.

5….

Démonstration:

On calcule la matrice densité (cf. appendice) ρ_{0} décrivant le mélange statistique des états envoyés à Bob pour représenter un bit 0 (b_{i} = 0) à l’étape 4 du protocole BCJL-commit :

ρ_{0} = \frac{1}{2}|↔⟩⟨↔ | + \frac{1}{2}|↗ ↙⟩⟨↗ ↙ | = ( \begin{matrix}\frac{3}{4} & \frac{1}{4} \\ \frac{1}{4} & \frac{1}{4} \end{matrix} )

et pour un bit 1 :

ρ_{1} = \frac{1}{2}| ↕⟩⟨ ↕ | + \frac{1}{2}|↘ ↖⟩⟨↘ ↖ | = ( \begin{matrix}\frac{1}{4} & −\frac{1}{4} \\ −\frac{1}{4} & \frac{3}{4} \end{matrix} )

On procède de même pour BCJL-commit’ :

ρ′_{0} = κ^{2}|B⟩⟨B| + (1 − κ^{2})|B^{⊥}⟩⟨B^{⊥}| = … = ρ_{0}
ρ′_{1} = (1 − κ^{2})|B⟩⟨B| + κ^{2}|B^{⊥}⟩⟨B^{⊥}| = … = ρ_{1}

Donc, si on appelle ρ_{C} la matrice densité associée au mélange des états utilisés pour envoyer C dans BCJL-commit et ρ′_{C} pour BCJL-commit’ on a :

ρ_{C} = ρ_{c_{1}} ⊗ ρ_{c_{2}} ⊗ … ⊗ ρ_{c_{n}} = ρ′_{c_{1}} ⊗ ρ′_{c_{2}} ⊗ … ⊗ ρ′_{c_{n}} = ρ′_{C}

Donc enfin, les matrice densités ϱ_{x} et ϱ′_{x} correspondant respectivement à BCJL-commit(x) et à BCJL-commit’(x) sont :

ϱ_{x} = \frac{1}{α_{x}} ∑_{C∈A_{x}} ρ_{C} = \frac{1}{α_{x}} ∑_{C∈A_{x}} ρ′_{C} = ϱ′_{x} où A_{x} = \{C | C ⊙ R = x\} et α_{x} = |A_{x}|

On constate que les matrices obtenues pour BCJL-commit coïncident à celles obtenues pour BCJL-commit’. D’aprés le théorème 5.2, on déduit donc que Bob est capable de tirer exactement la même information sur C (et sur x) dans les deux protocoles. Mais dans BCJL-commit’, Bob obtient toute l’information possible sur C (et sur x) en mesurant les photons π_{i} dans la base (|B⟩, |B^{⊥}⟩) puisqu’ils sont polarisés dans cette même base. Donc en particulier aucune mesure cohérente ne peut donner plus d’informations...

\underline{Theoreme} 2.10— Si Alice est honnête, il existe une constante α ∈ [0, 1[ telle que :

\frac{1}{2} − α^{n} ≤ \{ \begin{matrix}Pr(x = 0 | C′) \\ Pr(x = 1 | C′) \end{matrix} \} ≤ \frac{1}{2} + α^{n}

\underline{Protocole} 2.10— BCJL-unveil(x, B, C, B′, C′)

1. Alice révèle x, B et C à Bob.

2. Bob calcule δ ← ∑_{i|b′_{i}=b_{i}} \frac{c_{i} ⊕ c′_{i}}{n/2} .

3. Si (δ < 1.4ε) et (x = C ⊙ R) alors Bob accepte et refuse sinon.

\underline{Proposition} 2.9— BCJL-unveil a une complexité en n.

\underline{Theoreme} 2.11— Si Bob est honnête, il existe une constante α ∈ [0, 1[ telle que la probabilité qu’à Alice d’annoncer dans BCJL-unveil à sa guise (0, B^{0}, C^{0}) ou (1, B^{1}, C^{1}) et que Bob accepte soit majorée par α^{n}.

\underline{Theoreme} 2.12 Si Alice est honnête, il existe une constante α ∈ [0, 1[ telle que la probabilité qu’un honnête Bob rejete (B, C, x) dans BCJL-unveil soit majorée par α^{n}.

Conclusion :

Il est clair que ce protocole de mise en gage est révolutionnaire en lui même et le premier en son genre. Il ne reste qu’à ajuster les constantes et à attendre que les techniques suivent pour pouvoir espérer une implémentation réelle à grande échelle : on ne peut guerre actuellement dépacer les 32cm et minimiser les erreurs de transmissions à moins de 4%... Mais cette version laisse tout de même entrevoir les choses de façon optimiste !

2.3 Transfert équivoque – Transfert inconscient

2.3.1 Définitions

\underline{Definition} 2.3— Un protocole P est un protocole de transfert équivoque s’il se résume en un protocole du type :

– Alice envoie un bit x à P.

– P envoie (t, x′) à Bob tel que \{ \begin{matrix}x′ = 0 & si t = 0 \\ x′ = x & si t = 1 \end{matrix} avec Pr(t = 0) = Pr(t = 1) = \frac{1}{2}.

et tel qu’Alice ne sait pas si Bob a reçu x (i.e. si t = 1) ou pas.

\underline{Definition} 2.4— Un protocole P est un protocole de transfert inconscient s’il se résume en un protocole du type :

– Alice envoie deux bit x_{0} et x_{1} à P.

– Bob envoie un bit c à P.

– P envoie x_{c} à Bob.

et tel qu’Alice ne sait pas quel bit Bob a reçu, et Bob ne peut connaître qu’un seul des deux bits envoyés par Alice.

2.3.2 Un transfert équivoque faible

Le protocole :

\underline{Protocole} 2.11— OT_{f}(x)

1. Alice choisit aléatoirement un bit b et fixe (|φ⟩, |φ^{⊥}⟩) ← [ ↕ ↔, ↗ ↙ ↘ ↖]_{b}.

2. Bob choisit aléatoirement un bit b′ et fixe (|φ′⟩, |φ′^{⊥}⟩) ← [ ↕ ↔, ↗ ↙ ↘ ↖]_{b}′.

3. Alice envoie à Bob un photon π de polarisation [|φ⟩, |φ^{⊥}⟩]_{x}.

4. Bob mesure le photon π dans la base (|φ′⟩, |φ′^{⊥}⟩).

5. Bob fixe y ← \{ \begin{matrix}0 & si la mesure donne φ′ \\ 1 & sinon \end{matrix} .

6. Alice envoie à Bob b.

7. Bob établie \{ \begin{matrix}(t, x′) = (1, y) & si b′ = b \\ (t, x′) = (0, 0) & sinon \end{matrix}.

\underline{Proposition} 2.10— OT_{f} a une complexité bornée.

Etude :

\underline{Proposition} 2.11 Si Alice et Bob sont honnêtes, alors OT_{f} est un transfert équivoque.

Remarque : Alice n’a rien à gagner à tricher i.e. polariser dans une mauvaise base ou ne pas annoncer le b correcte ne lui apporte rien car elle ne sait pas la valeur que Bob a reçue. De plus utiliser des photons EPR n’apporte rien pour les mêmes raisons que pour QT défini en introduction. On ne regarde que le cas où Bob est malhonnête en supposant donc Alice honnête.

Une attaque possible pour Bob est de lire les photons dans la base (|B⟩, |B^{⊥}⟩). Dans ce cas Pr(x′ = x) ≈ 85% mais Bob ne sera jamais sur si x′ = x. L’attaque redoutable, appelée delayed measurements, consiste pour Bob à stoquer le photon π jusqu’à ce qu’Alice lui annonce b. Pratiquement le stoquage des photons étant si délicat, comme nous l’avons déjà évoqué, que ceci ne pose guère de problèmes, mais tout de même... En fait, plus généralement pour les transferts équivoque et inconscient, les protocoles quantiques consistent à envoyer des informations partielles (à cause du principe d’incertitude) à Bob, dont il connait leur validité quand Alice lui transmet une certaine information (la base de polarisation). Si cela n’avait pas d’importance pour la mise en gage, Il faut donc ici forcer la lecture des photons par Bob à leur réception ou du moins avant de passer à l’étape révélatrice d’Alice. Une implémentation de la mise en gage est possible, mais elle doit être judicieuse pour ne rien révéler à Alice...

2.3.3 Un transfert inconscient

Nous allons à partir du transfert équivoque faible précédent construire un transfert inconscient...

Voici un théorème justifiant le bon fonctionnement du protocole qui suit, sauf avec une probabilité exponentiellement faible en n.

\underline{Theoreme} 2.13 (Bernsthein)— Soit X = (x_{1}, x_{2}, …, x_{n}), un vecteur booléen, tel que ∀i ∈ {1, 2, …, n} , Pr(x_{i} = 1) = p, alors

∀δ ∈]0, p(p − 1)], Pr (|\frac{1}{n} ∑_{i=1}^{n} x_{i} − p| ≥ δ) ≤ 2^{−nδ^{2}}

Démonstration:

cf. [Kra86].

Le protocole :

\underline{Protocole} 2.12— \binom{2}{1} -OT(x_{0}, x_{1}, c)

1. Alice choisit aléatoirement un vecteur de n bits R.

2. DO_{i=1}^{n}: Alice effectue avec Bob OT_{f}(r_{i}), Bob obtenant le couple (t_{i}, r′_{i}).

3. Bob selectionne aléatoirement deux ensembles disjoints I_{0} = {i_{1}, i_{2}, …, i_{n/3}} et I_{1} = {i_{n/3+1}, i_{n/3+2}, …, i_{2n/3}} tels que, si possible, ∀i ∈ I_{0}, t_{i} = 1.

4. Bob envoie à Alice (J_{0}, J_{1}) ← (I_{c}, I_{1−c}).

5. Alice stoppe si J_{0} et J_{1} ne sont pas disjoints ou de mauvaises tailles.

6. Alice effectue, pour k = 0, 1, x̃_{k} ← x_{k} ⊕ ⨁_{i∈J_{k}} r_{i}

7. Alice envoie à Bob x̃_{0} et x̃_{1}.

8. Bob effectue x ← x̃_{c} ⊕ ⨁_{i∈I_{0}} r′_{i}.

Remarque : Ce principe est un un principe général pour tranformer un transfert équivoque en transfert inconscient. Il est tiré de [Cré88, Cré90a].

\underline{Proposition} 2.12— \binom{2}{1} -OT a une complexité en n.

Etude :

On ne regarde que le cas où Bob est malhonnête et Alice honnête.

\underline{Theoreme} 2.14— Si Bob mesure indépendamment chaque photon reçu dans une base, alors Bob ne peut pas avoir plus d’informations qu’un des deux bits d’Alice à une probabilité exponentiellement fiable en n près.

Démonstration:

Etant donné que Pr [∀i ∈ I_{1}, t_{i} = 1] est exponentiellement faible en n, si Bob suit le protocole, il ne peut tirer aucune information de x̃\overline{c} sauf dans une situation de probabilité d’existence exponentiellement faible en n. La tactique optimale de Bob serait de mesurer chaque photon dans la base (|B⟩, |B^{⊥}⟩). Or la proposition suivante nous permet de conclure (sa démonstration se fait par récurence) avec p_{i} = κ^{2} :

\underline{Proposition} 2.13— Soient 2n bits aléatoires c_{1}, c_{2}, …, c_{n}, c′_{1}, c′_{2}, …, c′_{n}. Si pour tout i ∈ {1, 2, …, n} on a Pr(c_{i} = c′_{i}) = p_{i} alors

Pr (⨁_{i=1}^{n} c_{i} = ⨁_{i=1}^{n} c′_{i}) = \frac{1}{2} + \frac{∏_{i=1}^{n}(2p_{i} − 1)}{2}

Pour empêcher Bob de stocker les photons reçus, il suffit qu’Alice demande à Bob, après l’étape 4 de OT_{f}, de mettre en gage à chaque photon reçu le bit lu et le bit correspondant au choix de base de Bob, qu’Alice demandera avec la probabilité 1/2 de révéler a la fin de OT_{f}. Lorsque cela ne correspondera pas, Alice mettra fin au protocole.

En ce qui concerne les mesures cohérentes, une étude similaire à celle de [\underline{BCJL93}] montre qu’elles n’apportent rien.

Bilan

\underline{Theoreme} 2.15— Ce transfert inconscient est inviolable par Bob.

\underline{Theoreme} 2.16— Disposant d’un protocole de mise en gage et un protocole de transfert inconscient, on peut construire un protocole de transfert inconscient de bits mis en gage, i.e. contraindre les participants à utiliser tout au long du protocole les bonnes entrées (x_{0}, x_{1}, c).

Démonstration:

cf. [Cré90b] qui met en évidence un algorithme de passage des deux protocoles de départ à celui d’arriver de complexité en m^{3}, où m est tel que les probabilités de réussites de fraudes des protagonistes sont exponentiellement faible en m.

Problèmes pratiques :

– Le problème des multiphotons donne un avantage pour Bob. Ce n’est pas très grave en pratique, on a un transfert équivoque à 50% + ε et ε ≈ 1% si la probabilité d’envoyer plusieurs photons est faible.

– Le problème du “zero-photon” : Bob annonce à Alice qu’il n’a pas reçu de photon avant qu’Alice ne lui annonce la base de polarisation. Si Bob dit qu’il ne reçoit pas de photon alors qu’il en reçoit, on se retrouve dans le cas précédent. Donc Alice doit faire des statistiques de son dispositif...

– \underline{Erreurs de transmission}. C’est le plus gros problème, car même si on n’a qu’1% d’erreurs, d’après la proposition 2.13, on aura au résultat quelque chose de quasi aléatoire! Il faut donc un système de codes correcteurs qui permette de corriger (r_{i})_{i∈I_{0}} et non (r_{i})_{i∈I_{1}}.

Pour plus de précisions quant à l’implémentation pratique de ce protocole, on consultera [\underline{BBCS92}].

2.3.4 Comment avoir un transfert équivoque fort?

Nous allons en fait reprendre le principe du protocole précédent pour pouvoir à partir de OT_{f} faire un transfert équivoque (fort) en implémentant des mises en gage. Je n’ai trouvé ce protocole nulle part, mais il n’est pas inintéressant de le citer :

\underline{Protocole} 2.13— OT(x) 1. Alice choisit aléatoirement un vecteur de n bits R.

2. DO_{i=1}^{n}: Alice effectue avec Bob OT_{f}(r_{i}), Bob obtenant le couple (t_{i}, r′_{i}).

3. Bob selectionne aléatoirement deux ensembles disjoints I_{0} = {i_{1}, i_{2}, …, i_{n/3}} et I_{1} = {i_{n/3+1}, i_{n/3+2}, …, i_{2n/3}} tels que, si possible, ∀i ∈ I_{0}, t_{i} = 1.

4. Bob choisit aléatoirement un bit c.

5. Bob envoie à Alice (J_{0}, J_{1}) ← (I_{c}, I_{1−c}).

6. Alice stoppe si J_{0} et J_{1} ne sont pas disjoints ou de mauvaises tailles.

7. Alice choisit aléatoirement c′

8. Alice effectue x̃ ← x ⊕ ⨁_{i∈J_{c′}} r_{i}.

9. Alice envoie à Bob (c′, x̃).

10. Bob effectue y ← x̃ ⊕ ⨁_{i∈I_{0}} r′_{i}.

11. Bob établie \{ \begin{matrix}(t, x′) = (1, y) & si c′ = c \\ (t, x′) = (0, 0) & sinon \end{matrix}.

Remarque : Alice s’assure donc que Bob mesure les photons au fur et à mesure en lui demandant, après l’étape 4 de OT_{f}, de mettre en gage à chaque photon reçu son bit lu et son choix de base qu’Alice demandera avec la probabilité 1/2 de révéler a la fin de OT_{f}.

Distribution de clefs quantiques

3.1 Introduction

Deux participants, appelés Alice et Bob, n’ayant aucune information secrète en commun intialement, désirent échanger des messages secrets résistants aux attaques d’un troisième protagoniste que nous appellerons Eve. Ils vont donc établir une clef secrète dont ils se serveront dans algorythme de codage sûr comme le one-time pad. On suppose dans cette partie qu’Alice et Bob sont honnêtes, et de plus l’existence d’un canal public classique dans le sens qu’il n’offre aucune sécurité contre l’espionnage, mais qu’il peut être utilisé sans craintes que les données transmises ne soit modifiées par Eve (existence justifiée dans [Bra92]).

3.2 Un Protocole de distribution de clefs quantiques

3.2.1 Le protocole théorique

\underline{Protocole} 3.1—

1. Alice choisit aléatoirement un vecteur de n bits B.

2. Alice choisit aléatoirement un vecteur de n bits C.

3. Bob choisit aléatoirement un vecteur de n bits B′.

4. DO_{i=1}^{n}:

– Alice envoie dans la base (|φ_{i}⟩, |φ_{i}^{⊥}⟩) ← [ ↕ ↔, ↗ ↙ ↘ ↖]_{b_{i}} le photon π_{i} de polarisation [|φ_{i}⟩, |φ_{i}^{⊥}⟩]_{c_{i}} à Bob.

– Bob lit dans la base (|φ′_{i}⟩, |φ′_{i}^{⊥}⟩) ← [ ↕ ↔, ↗ ↙ ↘ ↖]_{b′_{i}} le photon π_{i} reçu.

– Bob fixe c′_{i} ← \{ \begin{matrix}0 & si la mesure donne φ′_{i} \\ 1 & sinon \end{matrix} .

5. Bob envoie publiquement à Alice B′.

6. Alice envoie publiquement à Bob I = {i | b_{i} = b′_{i}}.

7. Alice et Bob fixent aléatoirement et publiquement un ensemble I′ ⊂ I et comparent publiquement si ∀i ∈ I′, b_{i} = b′_{i}.

8. Si le test précédent est concluant, Alice et Bob établissent la clef ← (c_{i})_{i∈I\I′}, sinon ils concluent qu’ils ont été espionnés.

Remarque : On peut améliorer le test de l’étape 7. Par exemple on peut uniquement comparer la parité du nombre de bits b_{i} = 1 et de bits b′_{i} = 1 en faisant varier I′. Ainsi il n’est pas nécessaire de retrancher I′ de I à l’étape 8.

Exemple :

1.  ↗ ↙ ↕ ↘ ↖ ↔ ↕ ↕ ↔ ↔ ↘ ↖ ↗ ↙ ↕ ↘ ↖ ↗ ↙ ↗ ↙ ↕
2.  ↕ ↔ ↗ ↙ ↘ ↖ ↗ ↙ ↘ ↖ ↕ ↔ ↕ ↔ ↗ ↙ ↘ ↖ ↗ ↙ ↘ ↖ ↕ ↔ ↗ ↙ ↘ ↖ ↕ ↔ ↗ ↙ ↘ ↖ ↗ ↙ ↘ ↖ ↗ ↙ ↘ ↖ ↗ ↙ ↘ ↖ ↕ ↔
3.  ↕ ↗ ↙ ↘ ↖ ↔ ↕ ↗ ↙ ↗ ↙ ↔ ↘ ↖ ↕ ↘ ↖ ↘ ↖ ↗ ↙ ↗ ↙ ↕
4.  ↕ ↔ ↗ ↙ ↘ ↖ ↗ ↙ ↘ ↖ ↕ ↔ ↕ ↔ ↗ ↙ ↘ ↖ ↗ ↙ ↘ ↖ ↕ ↔ ↗ ↙ ↘ ↖ ↕ ↔ ↗ ↙ ↘ ↖ ↗ ↙ ↘ ↖ ↗ ↙ ↘ ↖ ↗ ↙ ↘ ↖ ↕ ↔
5.  √ √ √  √ √  √ √ √ √
6.  1 0 1  0 1  1 0 0 1

1. Alice envoie à Bob une suite aléatoire de photons polarisés horizontalement (↔), verticalement ( ↕), à π/4 (↗ ↙) ou à 3π/4 (↘ ↖).

2. Bob mesure la polarisation de chacun de ces photons aléatoirement, soit de façon rectiligne ( ↕ ↔), soit de façon diagonale (↗ ↙ ↘ ↖).

3. Résultat des mesures de Bob.

4. Bob révèle publiquement à Alice les mesures effectuées pour chacun des photons détectés, mais pas le résultat de ces mesures.

5. Alice dit à Bob lesquelles de ses mesures étaient adéquates.

6. Ces données sont interprétées comme une suite de bits selon la convention arbitraire ↔=↗ ↙= 0 et ↕=↘ ↖= 1.

3.2.2 Etude de l’attaque d’Eve

Attaque primaire

On suppose ici qu’Eve mesure les photons qu’elle décide d’intercepter dans ↕ ↔ ou ↗ ↙ ↘ ↖ et en les réémettant dans l’une de ces bases. Il est très aisé de voir qu’Alice a une chance sur deux d’avoir lu le bon bit (Eve ne le sait qu’après la révélation des bases communes d’Alice et Bob), i.e. Eve obtient un demi-bit espéré d’information, et une chance sur quatre de se faire détecter par Alice et Bob si ce bit donne lieu à un bit de la clef.

Attaque de Breidbart

Eve mesure les photons qu’elle intercepte dans la base de Breidbart, et renvoie un photon de même polarisation que le résultat de la mesure précédente. Dans ce cas, Eve lit le bon bit avec une probabilité de κ^{2} ≈ 85%, mais elle ne sera jamais sure de la bonne valeur de ce bit. Ceci représente donc au sens de Shannon une information de 1+κ^{2} log_{2}(κ^{2})+(1−κ^{2}) log_{2}(1−κ^{2}) ≈ 0.399bit espéré d’information. De plus, la probabilité P de se faire détecter est définie par :

P = Pr(Eve lit bon bit et Bob lit bit opposé d’Eve) + Pr(Eve lit mauvais bit et Bob lit même bit qu’Eve)
= (1 − κ^{2})κ^{2} + κ^{2}(1 − κ^{2})
= \frac{1}{4}

Attaque plus générale

On suppose ici qu’Eve mesure les photons interceptés dans une base fixée (|φ⟩, |φ^{⊥}⟩), et les réemet dans une autre base fixée (|φ′⟩, |φ′^{⊥}⟩). Donc on peut définir P = Pr(Eve lise bon bit), et P′ = Pr(Bob lise même bit qu’Eve) comme suit : P = (⟨φ| ↔⟩ + ⟨φ| ↗ ↙⟩)/2 = (cos^{2}(θ) + cos^{2}(θ − π/4))/2, et de même P′ avec un θ′ bien choisi; donc (P, P′) ∈ [1/4, κ^{2}]^{2}.

– Détection de l’espionnage d’Eve : La probabilité pour qu’Eve se fasse détecter est donnée par P(1 − P′) + (1 − P)P′ = P + P′(1 − 2P). Trois cas se présentent :

1. P = 1/2 : la valeur de P′ n’importe pas.

2. P > 1/2 : il faut maximiser P′.

3. P < 1/2 : ceci revient au cas 1 où prendrait l’opposé du bit lu, ce qui ne change rien quant à la détection d’Eve.

Donc Eve a intérêt à prendre dans tous les cas P′ = κ^{2}, i.e. à renvoyer les photons dans la base (|B⟩, |B^{⊥}⟩), alors sa probabilité de se faire détecter est P(1 − 2κ^{2}) + κ^{2} ≥ P/4. Et donc à P′ fixé, si P ≠ 1/2 Eve a intérêt à maximiser P. En conclusion, Eve se fait le moins repérer (avec une probabilité de 1/4 sur les bits en communs entre Alice et Bob) en applicant l’attaque primaire ou de Breidbart.

– Quantité de bit espéré d’information révélée : En moyenne, Eve lit un bit avec une probabilité d’authenticité de P, et donc en terme d’information de Shannon la quantité de bit espéré d’information est 1 + P log_{2}(P) + (1 − P) log_{2}(1 − P) ≤ P/2.

Conclusion

Aucune mesure d’un photon en cours de route, effectuée par Eve qui ne sera informé qu’après coup de la bonne mesure à faire, ne peut révéler plus qu’un demi-bit espéré d’information à propos du bit effectivement codé par ce photon, même si Eve effectue une mesure non standart sur le photon. De plus, toute mesure produisant b bit d’information espérée (b ≤ 1/2) doit introduire un désaccord entre le bit envoyé par Alice et celui reçu par Bob avec une probabilité d’au moins b/2, si bien sûr ce photon donne lieu à un bit de la clef à l’issue du protocole.

3.2.3 L’implémentation pratique

Problèmes pratiques:

1. Utilisation délicate de photons isolés.

2. Erreurs de transmissions même en l’absence d’espionnage sur le canal quantique.

Des solutions sont apportées dans [\underline{BBBSS90}] où il est fait un description du premier montage expérimental de cryptographie quantique effectivement réalisé. Nous allons en exposer les idées de base ci-dessous.

1. On utilise des impulsions dans lesquelles le nombre de photons suit une loi de distribution de Poisson de moyenne contrôlable. D’un point de vue pratique, cette utilisation est plus aisée car elle permet de fixer des polarisations bien définies par des polariseurs, et grâce à une cellule de Pockels, on peut alterner facilement de polarisation entre deux pulsations. Cependant, on se trouve confronté à un problème de multiphotons, qui favorise l’attaque d’Eve. Pour y lutter on fixe par exemple un nombre moyen de photons par impulsion de 1/10. En moyenne, Eve peut trouver alors jusqu’à 10% de bits de la clef finale en utilisant les multiphotons ainsi produits.

2. On peut utiliser un code correcteur suffisamment redondant pour que Bob puisse corriger sans ambiguïté sa clef, mais aussi suffisamment non redondant pour pas dévoiler trop d’informations à Eve.

Le résultat de l’expérience de [\underline{BBBSS90}] du 27 février 1991

715 000 impulsions d’intensité moyenne 0.12 photon par impulsion ont été transmises d’Alice vers Bob distants de 32cm. On a pu obtenir une clef de 2000 bits contenant 79 erreurs, soit environ 4% d’erreurs de transmission. La correction d’erreurs a permis de corriger toutes les erreurs en ne révélant que 550 bits à Eve suite à l’espionnage du canal publique uniquement. On a de plus estimé qu’Eve avait une probabilité infime d’avoir obtenu plus de 601 des 2000 bits avant la correction d’erreurs. Donc en sacrifiant 1172 bits, Alice et Bob ont obtenu une clef finale de 828 bits, avec un rythme de transmission d’environ un bit par seconde, telle que la probabilité qu’Eve en connaisse un bit soit inférieure à 10^{−6}.

3.3 Autres méthodes

3.3.1 Photons EPR

cf. [Eke91] et [BBM92].

Dans le protocole précédent, il reste un petit problème : où stoquer la clef ainsi construite pour qu’elle ne soit pas espionnée? Même si elle est utilisée tout de suite, théoriquement on peut envisager une maneuvre d’Eve lui révélant des informations sur cette clef. Pour contrer cette ultime attaque, Artur Ekert a imaginé un protocole à base de photons EPR. Grâce à cette approche, la clef ne prend forme classique qu’au moment précis où elle sera utilisée comme masque jetable. Cependant cette sophistication n’est toutefois pas à la portée de la technologie actuelle.

3.3.2 Interférométrie

cf. [ERTP92].

Comme nous l’avons vu, l’un des problèmes du montage expérimental pour la distribution de clefs est la distance maximale entre Alice et Bob de 32cm. Néanmoins, Artur Ekert, John Rarity, Paul Tapster et Massino Palma travaillent actuellement sur une approche utilisant l’interférométrie et des fibres optiques, ce qui permettrait d’espérer une distance d’une centaine de kilomètres.

Conclusion

Nous avons montré à quel point la mécanique quantique apportait un nouveau regard aux problèmes de cryptographie. La perfection mathématique de la mécanique quantique semble se transporter vers la cryptogaphie, et permet ainsi d’envisager des solutions parfaites. Les obstacles restants sont essentiellement pratiques et leur levées nécessitent d’une part l’assouplissement des solutions existantes, ce qui les rend plus complexes et plus techniques, par l’implémentation de codes correcteurs, dont la maîtrise devient donc fondamentale, et d’autre part des progrès de physique expérimentale envisageables comme par exemple une amélioration du taux d’erreurs des detecteurs de photons, de la production de photons isolés, et surtout de la distance entre Alice et Bob. Notons que les protocoles cryptographiques quantiques évoqués dans ce mémoire ont déjà une utilité puisque leur implémentation pratique serait utile même sur une courte distance.

Dans ce mémoire, nous n’avons fait que citer l’une des applications de la mécanique quantique à l’informatique. La cryptographie quantique a pour fondements l’information quantique dont on pourra trouver une introduction aux principaux concepts dans l’appendice de ce mémoire. Citons aussi, le concept de l’ordinateur quantique de David Deutsch [Deu85, Deu86] qui permet en théorie l’accélération exponentielle de certains calculs [DJ91, Joz91, BB92]. Si l’ordinateur quantique parvenait un jour à factoriser très rapidement de grands entiers, la mécanique quantique pourrait d’une part probablement mettre en échec les systèmes de codages à clef publique, mais d’autre part apporterait, comme nous l’avons vu, de nouvelles solutions effectivement inviolables.

Pour conclure, je remercie Alain Finkel pour m’avoir fait découvrir ce sujet et m’avoir permis de rencontrer Claude Crépeau dont les cours de DEA et documentations fournies par lui-même m’ont été d’une utilité fondamentale, les bibliothèques d’Orsay et d’Ulm, AleX pour son initiation TEX, et tous ceux que j’oublie.

Appendice : l’information quantique

Source principale : [CTDL]

5.1 Généralités - Postulats

\underline{Postulat} 5.1— A un instant t_{0} fixé, l’état d’un système physique est défini par la donnée d’un vecteur d’état (fonction d’onde solution de l’équation de Schröninger) appartenant à l’espace de Hilbert des états (E, ⟨|⟩).

Notations : on appelle ket un vecteur |ψ⟩ et bra sa forme linéaire associée

⟨ψ| : φ ↦ ⟨ψ|φ⟩

Remarque : le vecteur d’état ayant une interprétation probabiliste, on le supposera normé par défaut.

\underline{Postulat} 5.2— A toute grandeur physique mesurable (position, vitesse, polarisation...) A est associée un opérateur A agissant dans E; cet opérateur est hermitien.

Remarques :

1. en fait l’opérateur est une observable, ce qui représente une notion plus forte en dimension ∞ et qui assure entre autre l’existence d’une base de Hilbert de vecteurs propres...

2. Contrairement à la mécanique classique, la mécanique quantique décrit de façon fondamentalement différente l’état d’un système et les grandeurs physiques associées : un état est représenté par un vecteur normé, une grandeur physique par un opérateur.

5.2 Mesure des grandeurs physiques

\underline{Postulat} 5.3— La mesure d’une grandeur physique A ne peut donner comme résultat qu’une des valeurs propres de l’observable A correspondante.

Remarques :

1. Une mesure de A donnera toujours une valeur réelle, puisque A est par définition hermitien.

2. Si le spectre de A est discret, les résultats que l’on peut obtenir en mesurant A sont quantifiés.

Exemples d’observables :

1. coordonnée x du vecteur position : opérateur X qui est l’opérateur multiplication par x.

2. coordonnée p_{x} du vecteur quantité de mouvement : opérateur P_{x} qui est \frac{h̄}{i} \frac{∂}{∂x}.

3. tester si un photon passe ou pas par un filtre polarisant orienté horizontalement est traduit

par l’observable ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ).

\underline{Postulat} 5.4— (cas d’un spectre discret) Lorsqu’on mesure la grandeur physique A sur un système dans l’état |ψ⟩ normé, la probabilité P(a_{n}) d’obtenir comme résultat la valeur propre a_{n} de l’observable A correspondante vaut :

P(a_{n}) = ∑_{i=1}^{g_{n}} |⟨u_{n}^{i}|ψ⟩|^{2}

où g_{n} est la multiplicité de a_{n}, et (|u_{n}^{i}⟩)_{i=1,2,...,g_{n}} est un système orthonormé de vecteurs formant une base dans le sous-espace propre E_{n} associé à la valeur propore a_{n} de A.

Remarque : Dans le cas d’un spectre continu, on généralise ceci en parlant de densité de probabilité...

5.3 Réduction du paquet d’ondes (cas d’un spectre discret)

Supposons que l’on veuille mesurer, à un instant donné, la grandeur physique A. Si l’on connaît le ket |ψ⟩ qui représente l’état du système avant la mesure, le postulat 5.4 permet de prédire les probabilités d’obtenir les divers résultats possibles. Mais, lorsqu’on effectue réellement la mesure, on obtient évidemment un seul de ces résultats possibles. Immédiatement après cette mesure, on sait quelle valeur a été effectivement obtenue. On possède donc une information supplémentaire, et il est compréhensible que l’état du système après la mesure, qui doit incorporer cette information, soit différent de |ψ⟩. Il vient donc naturellement le postulat suivant...

\underline{Postulat} 5.5— Si la mesure de la grandeur physique A sur le système dans l’état |ψ⟩ donne le résultat a_{n}, l’état du système immédiatement après la mesure est la projection normée de |ψ⟩ sur le sous-espace propre associé à a_{n}, soit \frac{P_{n}|ψ⟩}{\sqrt{⟨ψ|P n|ψ⟩}}.

5.4 Quelques conséquences

\underline{Proposition} 5.1— La valeur moyenne de l’observable A dans l’état |ψ⟩ est

⟨A⟩_{ψ} = ⟨ψ|A|ψ⟩

\underline{Proposition} 5.2— Lorsque deux observables A et B commutent, la mesure de B ne fait pas perdre les informations préalables fournies par une mesure de A (et réciproquement), mais au contraire les complète; de plus, l’ordre dans lequel on mesure les deux observables A et B est sans importance..

Remarque : dans le cas contraire, on peut ,par exemple, en considérant X et P_{x} démontrer le principe d’incertitude de Heisenberg.

5.5 L’opérateur densité

5.5.1 Position

Dans cette partie, nous ne considérons plus un sytème d’état ψ déterminé, mais défini de façon statistique i.e. :

∃ (ψ_{i})_{i∈I} , ψ ∈ {ψ_{i}}_{i∈I} et Pr(ψ = ψ_{i}) = p_{i} avec bien sûr ∑_{i∈I} p_{i} = 1

On dit qu’on a affaire à un mélange statistique des états (ψ_{i})_{i∈I} avec les probabilités (p_{i})_{i∈I}. On supposera de plus tous les vecteurs d’états normés.

5.5.2 Cas pur

\underline{Definition} 5.1— On appelle opérateur densité associé à l’état ψ l’opérateur ρ défini par

ρ = |ψ⟩⟨ψ|

\underline{Proposition} 5.3— Les propriétés suivantes sont vraies :

– tr(ρ) = 1.

– ⟨A⟩_{ψ} = tr(ρA).

– P(a_{n}) = tr(P_{n}ρ).

– ρ est un opérateur hermitien positif.

Démonstration: Plaçons nous dans une base hilbertienne (|u_{n}⟩)_{n}. On a donc

|ψ⟩ = ∑_{n} c_{n}|u_{n}⟩ avec ∑_{n} |c_{n}|^{2} = 1

⟨u_{i}|A|u_{j}⟩ = a_{i,j}

⟨A⟩_{ψ} = ⟨ψ|A|ψ⟩ = ∑_{i,j} \overline{c_{i}}c_{j}a_{i,j}

ρ_{i,j} = ⟨u_{i}|ρ|u_{j}⟩ = \overline{c_{i}}c_{j}

Il suffit de réécrire les propriétés avec ces notations pour les démontrer...

Remarque : Donc dans un cas pur, un système peut être décrit aussi bien par un opérateur densité que par un vecteur d’état. De plus on y gagne quelques avantages comme la linéarité ds formules utilisant cet opérateur.

5.5.3 Cas non-pur : mélange statique d’états

\underline{Definition} 5.2— Soit un systéme défini par le mélange statistique (ψ_{i}, p_{i})_{i∈I} comme au 5.5.1. Alors on définit l’opérateur densité du système comme suit

ρ = ∑_{k} p_{k}|ψ_{k}⟩⟨ψ_{k}| (= ∑_{k} p_{k}ρ_{k})

\underline{Proposition} 5.4— Les propriétés suivantes sont vraies :

– tr(ρ) = 1.

– ⟨A⟩_{ψ} = tr(ρA).

– P(a_{n}) = tr(P_{n}ρ).

– ρ est un opérateur hermitien positif.

\underline{Theoreme} 5.1— Il est impossible de distinguer physiquement les divers types de mélanges statistiques qui conduisent à la même matrice densité.

Démonstration:

Il suffit de voir que toutes les prévisions physiques ne dépendent que de la matrice densité, ce qui a été établi à la proprosition 5.4.

Remarque : ρ_{n,n} = ∑_{k} p_{k} |c_{n}^{k}|^{2} (où c_{n}^{k} = ⟨u_{n}|ψ_{k}⟩) représente la probabilité moyenne de trouver le système dans l’état |u_{n}⟩ après mesure par l’observable A.

5.6 Produit tensoriel d’états

5.6.1 Introduction

La notion de produit tensoriel d’espaces d’états permet, entre autre, de résoudre le problème suivant. Soit deux systèmes physiques isolés (S_{1}) et (S_{2}) d’espaces d’états correspondants respectifs E_{1} et E_{2}. Si nous considérons maintenant l’ensemble de ces deux systèmes comme un unique système (S), quel est l’espace des états E associé?

5.6.2 Définitions

\underline{Definition} 5.3— Par définition, l’espace vectoriel E est appelé produit tensoriel de E_{1} et E_{2}, noté E = E_{1} ⊗ E_{2}, si à tout couple de vecteurs, (|ψ_{1}⟩, |ψ_{2}⟩) ∈ E_{1} × E_{2}, on associe un vecteur de E, noté |ψ_{1}⟩ ⊗ |ψ_{2}⟩ et appelé produit tensoriel de |ψ_{1}⟩ et |ψ_{2}⟩, tel que cette correspondance soit linéaire par rapport à la multiplication par des scalaires, et distributive par rapport à l’addition vectorielle :

[λ|ψ_{1}⟩] ⊗ |ψ_{2}⟩ = λ [|ψ_{1}⟩ ⊗ |ψ_{2}⟩] = |ψ_{1}⟩ ⊗ [λ|ψ_{2}⟩]
[|ψ_{1}⟩ + |ψ′_{1}⟩] ⊗ |ψ_{2}⟩ = |ψ_{1}⟩ ⊗ |ψ_{2}⟩ + |ψ′_{1}⟩ ⊗ |ψ_{2}⟩
|ψ_{1}⟩ ⊗ [|ψ_{2}⟩ + |ψ′_{2}⟩] = |ψ_{1}⟩ ⊗ |ψ_{2}⟩ + |ψ_{1}⟩ ⊗ |ψ′_{2}⟩

et tel que si (|u_{1}^{i}⟩)_{i} et (|u_{2}^{j}⟩)_{j} sont respectivement des bases de E_{1} et E_{2}, alors (|u_{1}^{i}⟩ ⊗ |u_{2}^{j}⟩)_{i,j} est une base de E.

Notation : On note plus généralement |ψ_{1}⟩ ⊗ |ψ_{2}⟩ = |ψ_{1}⟩|ψ_{2}⟩ = |ψ_{1}ψ_{2}⟩.

\underline{Definition} 5.4— On peut définir sur E = E_{1} ⊗ E_{2} le produit scalaire suivant :

⟨ψ_{1}ψ_{2}|ψ′_{1}ψ′_{2}⟩ = ⟨ψ_{1}|ψ′_{1}⟩⟨ψ_{2}|ψ′_{2}⟩

Remarque : on définit de même le produit tensoriel d’opérateurs.

5.6.3 Application

\underline{Theoreme} 5.2— On peut considérer qu’un état produit |ψ_{1}⟩ ⊗ |ψ_{2}⟩ représente la simple juxtaposition de deux systèmes, l’un dans l’état |ψ_{1}⟩, l’autre dans l’état |ψ_{2}⟩. On dit encore que, dans un tel état, les deux systèmes sont sans corrélations (de manière plus précise, les résultats de deux types de mesures portant soit sur un système, soit sur l’autre, correspondent à des variables aléatoires indépendantes). Une telle situation est réalisée lorsque les deux systèmes ont été préparés séparément dans les états |ψ_{1}⟩ et |ψ_{2}⟩ et qu’on les réunit ensuite, sans qu’ils interagissent.

\underline{Proposition} 5.5— Si le système global est dans un état produit |ψ⟩ = |ψ_{1}⟩ ⊗ |ψ_{2}⟩, alors son opérateur densité sécrit ρ = ρ_{1} ⊗ ρ_{2}, où ρ_{1} et ρ_{2} sont respectivement les opérateurs densités de ψ_{1} et ψ_{2}.

Références

[\underline{BB84}] C.H. Bennet, G. Brassard. Quantum cryptography : Public key distribution and coin tossing, Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, 1984, pp. 175-179.

[BB92] A. Berthiaume, G. Brassard. The quantum challenge to structural complexity theory, Proceedings of 7th Annual IEEE Conference on Structure in Complexity Theory, juin 1992, pp. 132-137.

[\underline{BBBSS90}] C.H. Bennett, F. Bessette, G. Brassard, L. Salvail, et J. Smolin. Experimental quantum cryptography, Advances in Cryptology - Eurocrypt’ 90 Proceedings, avril 1990, Springer-Verlag, pp. 253-265. Nouvelle édition dans Journal of Cryptology, vol. 5, no. 1, 1992, pp. 3-28.

[BBBW82] C.H. Bennett, G. Brassard, S. Breidbart, et S. Wiesner. Quantum cryptography, or unforgeable subway tokens, Advances in Cryptology : Proceedings of Crypto’ 82, août 1982, Plenum, New York, pp. 267-275.

[\underline{BBCS92}] C.H. Bennett, G. Brassard, C. Crépeau, M.-H. Skubiszewska. Pratical quantum oblivious transfer protocols, Advances in Cryptology : Proceedings of Crypto’ 91, vol. 576 de Lecture Notes in Computer Science, pp. 351-366. Springer-Verlag, 1992.

[\underline{BBE92}] C.H. Bennett, G. Brassard, A.K. Ekert. Quantum cryptography, Scientific American, octobre 1992, pp. 50-57.

[BBM92] C.H. Bennett, G. Brassard, N.D. Mermin. Quantum cryptography without Bell’s theorem, Physical Review Letters, vol. 68, 3 février 1992, pp. 557-559.

[\underline{BC91}] G. Brassard, C. Crépeau. Quantum bit commitment and coin tossing protocols, Advances in Cryptology : Proceedings of Crypto’ 90, vol. 537 de Lecture Notes in Computer Science, pp. 49-61. Springer-Verlag, 1991.

[\underline{BCJL93}] G. Brassard, C. Crépeau, Richard Jozsa, Denis Langlois. A quantum bit commitment scheme provably unbreakable by both parties, en préparation, 1993.

[Bra92] G. Brassard. Cryptologie contemporaine, chez Masson.

[Cré88] C. Crépeau. Equivalence between two flavours of oblivious transfers, Advances in Cryptology : Proceedings of Crypto’ 87, vol. 293 de Lecture Notes in Computer Science, pp. 350-354. Springer-Verlag, 1988.

[Cré90a] C. Crépeau. Correct and Private Reductions among Oblivious Transfers. PhD thesis, Department of Elec. Eng. and Computer Science, Massachusetts Institute of Technology, 1990. Supervisée par Silvio Micali.

[Cré90b] C. Crépeau. Verifiable disclosure of secrets and applications, Advances in Cryptology : Proceedings of Eurocrypt’ 89, vol. 434 de Lecture Notes in Computer Science, pp.181-191. Springer-Verlag, 1991.

[\underline{Cré93}] C. Crépeau. Cryptographic primitives and quantum theory, Proceedings of the second Physics of Computation Workshop, PhysComp’ 92, pp. 200-204, 1993.

[CTDL] C. Cohen-Tannoudji, B. Diu, F. Laloë. Mécanique quantique.

[Del92] J.-P. Delahaye. Cryptographie quantique, Pour la science, no. 178, août 1992, pp. 101-106.

[Deu85] D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer, Proceedings of the Royal Society, Londres, vol. A400, 1985, pp. 97-117.

[Deu86] D. Deutsch. Three connections between Everett’s interpretation and experiment, Quantum Concepts in Space and Time, R. Penrose et C. Isham, Clarendon Press, Oxford, 1986, pp. 215-225.

[Deu89] D. Deutsch. Quantum communication thwarts eavesdroppers, New Scientist, 9 décembre 1989, pp. 25-26.

[DJ91] D. Deutsch, R. Jozsa. Rapid solution of problems by quantum computation, distribué par les auteurs, décembre 1991.

[Eke91] A.K. Ekert. Quantum cryptography based on Bell’s theorem, Physical Review Letters, vol. 67, 5 août 1991, pp. 661-663.

[EPR35] A. Einstein, P. Podolsky, N. Rosen. Can quantum-mechanical description of physical reality be considered complete?, Physical Review, vol. 47, 1988, pp. 42-52.

[ERTP92] A.K. Ekert, J. Rarity, P. Tapster, G.M. Palma. Practical quantum cryptography based on two-photon interferometry, Physical Review Letters, vol. 69, 31 août 1992, pp. 1293-1296.

[Joz91] R. Jozsa. Characterizing classes of functions computable by quantum parallelism, Proceedings of the Royal Society, Londres, vol. A435, 1991, pp. 563-574.

[Got89] A. Gottlieb. Conjugal secrets - The untappable quantum telephone, The Economist, vol. 311, no. 7599, 22 avril 1989, p. 81.

[Kra86] E. Kranakis. Primality and cryptography. John Wiley and Sons, 1986.

[MS77] F.J MacWilliams, N.J.A Sloane. The THeory of Error-Correcting Codes, North-Holland, 1977.

[Pet90] I. Peterson. Bits of uncertainly : Quantum security, Science News, vol. 137, 2 juin 1990, pp. 342-343.

[Wal89] P. Wallich. Quantum cryptography, Scientific American, vol. 260, no. 5, mai 1989, pp. 28-30.

[Wie83] S. Wiesner. Conjugate coding, écrit vers 1970, non publié jusqu’en 1983 dans Sigact News, vol. 15, no. 1, 1983, pp. 78-88.

[WZ82] W.K. Wootters, W.H. Zurek. A single quantum state cannot be cloned, Nature, vol. 299, 1982, pp. 802-803.