From madore@news.ens.fr
Path: eleves!not-for-mail
From: madore@news.ens.fr (GroTeXdieck)
Newsgroups: ens.forum.sciences.physique,ens.forum.informatique.crypto,ens.forum.sciences.maths
Subject: Re: =?iso-8859-1?Q?Allegre_plus_vite_que_la_lumi=E8re?=
Date: 16 Mar 1999 01:30:41 GMT
Lines: 204
Sender: madore@clipper.ens.fr
Message-ID: <7ckc81$p0o$1@clipper.ens.fr>
References: <7c72po$mp5$1@clipper.ens.fr> <7cbdqk$rvj$2@clipper.ens.fr> <7cbg56$5f8$1@clipper.ens.fr> <7cj1mi$fhc$4@clipper.ens.fr> <7cj2mh$hlr$1@clipper.ens.fr> <7cj4gt$fhc$7@clipper.ens.fr>
NNTP-Posting-Host: clipper.ens.fr
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: clipper.ens.fr 921547841 25624 129.199.129.1 (16 Mar 1999 01:30:41 GMT)
X-Complaints-To: forum@clipper.ens.fr
NNTP-Posting-Date: 16 Mar 1999 01:30:41 GMT
X-Newsreader: Flrn (0.3.1 - 12/98)
X-Censorship: yes
Xref: eleves ens.forum.sciences.physique:71 ens.forum.informatique.crypto:144 ens.forum.sciences.maths:427

[Beware.  The following message contains a large amount of rant and
mumbo jumbo.  The surgeon general advises you that large quantities of
rant and mumbo jumbo have been known to cause mindlessness on
laboratory animals.]

[Oui, j'ai bien une raison de crossposter dans les groupes où je
crossposte.  Il faut cependant lire jusqu'au bout pour comprendre
cette raison.]

[Les différentes parties de cet article sont indépendantes :-]

Si je me souviens bien, le protocole expérimental épuré qui conduit à
une expérience de type EPR est le suivant : on considère la
désintégration d'une particule de spin 0 en deux particules de spin
1/2 (typiquement, pion zéro -> électron plus positron), qui doivent
alors avoir des spins orientés dans des directions opposées.  Deux
expérimentateurs, situés à une distance très grande, de part et
d'autre du lieu de désintégration, mesurent chacun le spin d'une de
ces particules émise lorsqu'elle parvient jusqu'à lui.

Une mesure consiste à choisir un axe et à observer le spin le long de
cet axe : les deux réponses possibles sont « oui » (le spin sur cet
axe est dans cette direction) ou « non » (il est dans la direction
opposée).  Si le spin de la particule et l'axe de mesure font un angle
theta, la probabilité de lire « oui » est cos^2(theta/2) et celle de
lire « non » est donc sin^2(theta/2)=cos^2((pi-theta)/2).  (Entre
autres, si theta=0 on lit « oui » et si theta=pi, axes opposés, on lit
« non ».)  Ces détails sont finalement peu importants.  Il convient de
noter qu'on ne peut pas refaire une mesure : si on a mesuré le spin
suivant un axe, le spin est alors (après la mesure) forcément dirigé
suivant l'axe ou opposé à lui.

Les physiciens ont au préalable convenu de trois axes, A, B et C,
suivant lesquels ils peuvent mesurer le spin, ces axes étant séparés
de 2pi/3 (120 degrés).

Le résultat théorique (qui doit être, j'imagine, confirmé par
l'expérience) est le suivant : si les deux physiciens choisissent le
même axe, leurs mesures sont certaines d'être opposées (oui/non ou
non/oui, chaque possibilité ayant probabilité 1/2), tandis que s'ils
choisissent des axes différents les mesures ont une probabilité 3/4
(i.e. sin^2(pi/3)) d'être semblables (oui/oui ou non/non, chaque
possibilité ayant probabilité 3/8) et 1/4 d'être différentes (oui/non
ou non/oui, chaque possibilité ayant probabilité 1/8).

Ce qui constitue le paradoxe EPR, c'est que de telles probabilités ne
peuvent *pas* résulter d'une théorie de variables cachées.

En effet, résumons ce que serait la situation avec des variables
cachées : on a en jeu deux physiciens et deux « dieux ».  Les dieux
communiquent entre eux en secret au début de l'expérience (et peuvent
consulter le hasard).  Puis chaque dieu accompagne un physicien et les
deux dieux ne peuvent plus communiquer.  Le physicien lui pose la
Question A, la Question B ou la Question C, et le dieu doit répondre
« oui » ou « non », de sorte que la probabilité sur chaque question
individuellement soit 1/2 pour chaque réponse, que si les deux
physiciens posent la même question les réponses soient forcément
différentes et que si les deux physiciens posent des questions
différentes les réponses aient 3 chances sur 4 d'être les mêmes et 1
chance sur 4 d'être différentes.  (Je vous conseille d'essayer de
trouver la difficulté avant de lire la suite.)

Que peuvent faire les dieux ?  Il faut forcément qu'ils aient convenu
de la réponse à chaque question puisque les réponses au physicien L
(de gauche) pour chaque question doivent être à coup sûr différentes
des réponses faites au physicien R (de droite).  On peut donc dire que
les dieux conviennent des réponses qui devraient être faites au
physicien L, celles qui devraient être faites au physicien R s'en
déduisant.  Les choix possibles sont NNN, NNY, NYN, NYY, YNN, YNY, YYN
ou YYY.  Pour des raisons évidentes de symétrie, NNN et YYY doivent
avoir la même probabilité, disons p/2 chacune, et les six autres la
même probabilité, disons q/6 chacune, avec q=1-p.  On voit alors que
si les physiciens posent des questions différentes, disons A et B, les
possibilités dans lesquelles les réponses sont les mêmes sont NYN,
NYY, YNN et YNY (cela correspond aux cas où les deux premières lettres
diffèrent parce que les réponses faites à R sont opposées aux réponses
faites à L), soit une probabilité totale de 2q/3.  Pour les
possibilités dans lesquelles les réponses diffèrent, c'est p+q/3 =
1-2q/3 (logique), et on doit avoir finalement 2q/3=3/4 soit q=9/8 et
p=-1/8, ce qui fait mal pour des probas.

Donc une interprétation de type « variable cachée » ne tient pas, et
il n'est pas sensé, dans le Dogme de Copenhague, de supposer que les
dieux se soient concertés à l'avance sur toutes les réponses
possibles, la seule possibilité étant alors qu'ils aient communiqué
après la séparation, donc plus vite que la lumière.  Cela ne permet
cependant pas aux physiciens d'en profiter pour faire voyager de
l'information plus vite que la lumière.

Pour expliciter ça, je vais rendre le paradoxe plus flagrant, ce qui
va me permettre de faire le lien avec l'informatique (et, notamment,
la crypto).

Pour rendre le paradoxe plus flagrant, je multiplie le nombre
d'options, et je transforme ce minable 3/4 en un sublime 1.  Supposons
donc qu'on ait une boîte à mille pièces.  J'appuie sur un bouton et
chaque pièce devient soit pile soit face.  Mais je n'ai le droit d'en
regarder qu'une seule ou deux (ou zéro :-) après le tirage.  Si j'en
regarde une, elle a une chance sur deux d'être pile et une chance sur
deux d'être face.  Jusque là, rien de magique.  Si j'en regarde deux,
alors il est certain qu'elles soient sur des côtés différents.  Là, on
voit bien le paradoxe (comment mettre mille pièces sur pile ou face en
étant sûr que deux quelconques d'entre elles sont sur des côtés
différents ? - s'il n'y avait que deux pièces ce ne serait pas un
problème, mais mille c'est assez dur).  Il faudrait des probabilités
négatives là-aussi (une probabilité de (2^-998)-1, presque -1, que
toutes les pièces soient sur le même côté).  Ou alors une
communication, c'est-à-dire que quand on observe la première, toutes
les autres passent sur l'autre côté.  Dans le paradoxe EPR, on permet
essentiellement aux deux physiciens d'avoir de telles boîtes
synchronisées, et l'un observe une pièce et l'autre une autre.  Il y a
de la magie dans l'air mais pas de transmission supraluminique de
l'information : le fait que deux personnes puissent observer la même
variable aléatoire, ou des projections de cette variable, ne permet
pas de transmettre de l'information, puisqu'ils ne peuvent pas agir
sur la variable, cette variable prît-elle des probabilités négatives
(auquel cas ce sera forcément des projections de la variable,
puisqu'on ne peut jamais observer un phénomène mettant en jeu des
probabilités négatives).

Comment ferait-on en crypto ?  D'abord, je rappelle brièvent ce que
c'est qu'une fonction de hash : c'est une fonction (connue et
calculable) des suites finies (enfin bref, des machins en entrée) à
valeur dans un truc fini fixé (les suites de 0 et de 1 d'une certaine
longueur, p.e. 128 pour md5) telle que personne ne sache trouver deux
entrées différentes produisant la même sortie (« collision »), encore
moins une entrée ayant pour image une sortie donnée ou une deuxième
entrée produisant une même sortie qu'une entrée donnée.  L'intérêt
d'une fonction de hash est de permettre de synchroniser l'échange
d'information : si je prends une information, que je lui concatène une
clé aléatoire (permettant d'éviter la recherche sur l'espace des
entrées) et que je publie le hash de cette concaténation, alors
personne ne peut déduire l'information mais on pourra déduire, si je
publie ultérieurement la clé, que je connaissais l'information à ce
moment-là.

[Exemple pour éclairer la digression : je veux jouer à pile ou face
par email.  Alors j'écris un fichier avec sur la première ligne soit
le nombre 0 soit le nombre 1 et sur la deuxième une phrase (aléatoire)
de mon choix.  Mon correspondant fait de même.  Nous nous échangeons
les hashs md5 de nos fichiers, puis, quand nous avons reçu le hash de
l'autre, les vrais fichiers eux-même (qu'il est trop tard pour
modifier puisque le correspondant a déjà le hash).  Si les deux
nombres sont égaux, on dit que c'était pile, sinon, que c'était face.
De cette manière, si au moins un des correspondants le veux, il peut
assurer que ce soit vraiment un jeu de pile ou face.  (Cependant, si
les deux collaborent ils peuvent truquer le jeu.  Il y a des façons de
remédier à ça mais c'est hors propos.)]

Revenons à nos moutons.  Il y a un protocole cryptographique
intéressant, c'est celui de la certification (probabiliste) de preuve
sans divulgation.  Ce protocole me permet de laisser tout le monde
vérifier que je sais démontrer quelque chose sans pour autant que je
fournisse une preuve de cette chose.  L'exemple de base (à partir
duquel, paraît-il, tous les autres se déduisent, mais je ne sais pas
comment), c'est le n-coloriage d'un graphe.  On convient d'un graphe
G.  Je sais le colorier avec n couleurs (i.e. sans avoir deux graphes
reliés par une arête de la même couleur).  Mon correspondant veut
vérifier que je le sais bien (de manière probabiliste, mais avec une
certitude aussi grande qu'il le désire) mais je ne veux pas lui
transmettre le coloriage que je connais.  Le protocole est alors le
suivant.  On fait un certain nombre de « tours » (autant que mon
correspondant le souhaite).  À chaque tour je commence par choisir une
permutation aléatoire des couleurs sur le coloriage que je connais (ou
sur un des coloriages que je connais, peu importe).  Je choisis une
clé aléatoire pour chaque sommet du graphe.  Pour chaque sommet, je
calcule le hash de la couleur (permutée) plus (concaténé avec) la clé
aléatoire, et j'envoie tous ces hashs à mon correpondant (étiquetés
par les sommets du graphes).  Mon correspondant en retour choisit une
arête et me l'envoie.  Je lui donne alors les couleurs et les clés
pour les deux sommets de cette arête.  Il peut vérifier que les
couleurs sont différentes et que je connaissais bien des couleurs
avant l'échange (parce que je ne peux pas gruger sur les hashs).  Si
je ne connais pas de coloriage, forcément à chaque tour il y aura deux
sommets reliés par une arête et de la même couleur, et mon
correspondant a une certaine probabilité de tomber dessus et alors je
suis démasqué.  En faisant assez de tour mon correspondant peut rendre
négligeable la probabilité que je le gruge.  [Plus de précisions sur
ce protocole et sur bien d'autres dans l'article « Cryptography » de
R. L. Rivest (himself), in « Handbook of Theoretical Computer
Science », édité par J. van Leeuwen, volume A.]

Quel rapport avec EPR ?  Eh bien la boîte magique à mille pièces dont
je parlais plus haut fournit une certification probabiliste du fait
que le graphe complet K_100 à 100 sommets est coloriable par deux
couleurs, ce qui est certainement faux.  Autrement dit, les dieux de
la mécanique quantique peuvent nous pipoter cryptographiquement qu'ils
savent colorier des graphes incoloriables.  Enfin, bien sûr, en
matière de certification de non intéraction, ils ne fournissent pas
des hashs mais simplement un éloignement important dans l'espace.
Apparemment ce n'est pas suffisant.

Conclusion : si votre partie et une autre partie se proposent
d'échanger des informations, exigez un protocole à base de hashs.  Il
n'est *pas* suffisant d'utiliser un protocole comme celui-ci : un
membre de votre partie transmet une information à un membre de la
partie adverse pendant qu'en même temps ou presque un membre de la
partie adverse, situé à un parsec de là, transmet l'information
échangée à un membre de votre partie.  Avec un tel protocole, en
utilisant des moyens quantiques, on peut arriver à une gruge.  Comme
arriver à vous faire croire qu'on connaît une démonstration sans la
connaître.

C'était le message cryptoquantique de la semaine.