33
28
La Lettre
© senoldo - Fotolia
propres à la cryptographie. Il est facile d’imaginer des situations où l’on désire convaincre un tiers que
nous sommes en possession d’un code secret, sans pour autant le révéler explicitement ; une preuve à
divulgation nulle se charge de cette tâche. Dans le même esprit, je peux vous convaincre que je sais colo-
rier un graphe avec trois couleurs sans pour autant vous révéler la moindre information sur le coloriage en
question. Moyennant l’existence de « fonctions à sens unique » - l’outil fondamental de la cryptographie -,
qui veulent que l’antécédent d’une image est difficile à trouver, tout problème dans NP admet une preuve
à divulgation nulle.
Une notion encore plus étonnante est celle de « preuve à vérification instantanée » (
Probabilistically
Checkable Proof
, PCP). Supposons que j’aie calculé la millionième décimale de π, qui se trouve être 1 :
comment vous convaincre en quelques secondes que c’est en effet 1 ? Je peux vous donner accès à
un ordinateur qui contient le programme de calcul de π, vous tapez 1 000 000 et, après un temps court
de calcul, la réponse s’inscrit sur l’écran : oui, c’est bien 1. C’est rapide, mais cela ne constitue pas une
preuve, car vous êtes obligé de me faire confiance sur le bon fonctionnement du programme, de l’ordi-
nateur, du compilateur, etc. À l’inverse, je peux écrire dans un (gros) livre toutes les étapes de calcul du
développement en série de π qui m’a amené à cette millionième décimale : elles constituent une preuve
de mon affirmation qui ne requiert aucune confiance de votre part, mais il vous sera impossible de vérifier
rapidement que je n’ai fait aucune erreur de calcul !
Il n’y aurait donc pas d’alternative : ou vous me faites confiance, et la vérification se passe très vite, ou
vous vous méfiez, et votre tâche devient alors longue et rude. En fait, cette dichotomie est illusoire :
je peux en effet vous convaincre très rapidement de la véracité de mon calcul sans exiger de vous la
moindre confiance, grâce à l’algorithme PCP. Son utilisation me permet de réécrire la longue preuve dans
un format spécial dont vous pourrez
extraire au hasard une dizaine de
caractères : leur examen rapide vous
conduira à convenir que j’ai raison,
ou à rejeter mon affirmation. Le mi-
racle est que, dans tous les cas de
figure, vous n’errerez qu’avec une
probabilité infime, par exemple de
l’ordre d’une chance sur mille. Bien
sûr, plus vous piochez de caractères,
plus cette probabilité d’erreur chute,
avec une rapidité exponentielle.
Ce résultat est général : si je pré-
tends avoir une démonstration de
l’hypothèse de Riemann, je peux
également vous en convaincre de
façon quasi instantanée. Existe-t-
il une version non probabiliste de
