Comment confirmer son identité à un distributeur sans devoir saisir son code secret ? Un protocole sécurisé s’appuyant sur le principe de "preuve à divulgation nulle de connaissance" et sur la relativité restreinte a été mis au point. Quand vous retirez de l’argent à un distributeur, vous devez taper votre code secret sur un clavier pour confirmer votre identité. Cette opération est un point faible du système. De toute évidence, vous devez entrer votre code à l’abri de regards indiscrets. Mais, plus difficile à détecter, certains escrocs équipent les distributeurs de faux claviers ou de faux lecteurs de cartes qui enregistrent toutes vos informations. Existe-t-il une solution pour sécuriser cette étape d’identification ? En 1985, Shafi Goldwasser et Silvio Micali, du MIT (l’institut de technologie du Massachusetts), et Charles Rackoff, de l’Université de Toronto, ont introduit le concept de "preuve à divulgation nulle de connaissance".
Ce protocole permet, dans le cas du distributeur de billets, de confirmer votre identité sans révéler votre code secret qu’un tiers mal intentionné pourrait exploiter. Mais pour des raisons techniques, il était difficile de mettre en œuvre ce protocole. Sébastien Designolle, avec ses collègues de l’Université de Genève et de l’Université McGill à Montréal, vient d’en faire une démonstration concrète en s’appuyant sur le fait que l’information ne peut être transmise à une vitesse plus grande que celle de la lumière, comme le stipule la théorie de la relativité restreinte.
En quoi consistent les preuves à divulgation nulle de connaissance ? Imaginez que vous avez résolu un des problèmes mathématiques du millénaire mis à prix un million de dollars, ou que vous avez inventé une machine révolutionnaire, mais que vous avez peur qu’on vous vole vos idées. Comment prouver que vous avez une démonstration ou une invention sans en révéler les détails ? C’est là qu’intervient la preuve à divulgation nulle de connaissance. Imaginez qu’Alice (le "fournisseur de preuve") ait découvert une technique infaillible pour distinguer du Coca-Cola de toute autre marque de cola simplement en regardant les liquides, et elle veut le prouver à Bob (le "vérificateur").
Grâce à un jeu de questions-réponses, Bob peut s’assurer qu’Alice a bien en sa possession ce qu’elle affirme. Il sert deux verres de cola. Grâce à sa technique, Alice identifie celui qui contient le Coca et l’indique à Bob. Bob répète l’expérience de nombreuses fois pour s’assurer qu’Alice n’a pas simplement eu un coup de chance. À la fin des tests, Bob ne connaît pas la technique, mais il sait qu’Alice peut détecter correctement le Coca (cet exemple a été imaginé par Gilles Brassard, un spécialiste en cryptographie de l’Université de Montréal).
La plupart des protocoles conventionnels de preuve à divulgation nulle d’information, comme ceux développés en 1988 par Adi Shamir (un des inventeurs du protocole RSA qui sert à sécuriser de nombreuses communications sur internet), impliquent de résoudre des problèmes mathématiques difficiles comme la décomposition d’un grand nombre en ses facteurs premiers. La robustesse du système dépend donc de la puissance des ordinateurs utilisés pour résoudre le problème mathématique. Or les spécialistes savent déjà qu’un algorithme quantique, proposé en 1995 par le mathématicien américain Peter Shor, pourra factoriser des nombres premiers très rapidement quand les ordinateurs quantiques seront assez puissants.
En 1988, Avi Wigderson, mathématicien à l’Institut des études avancées de Princeton et lauréat du prix Abel 2021, et ses collègues, ont montré qu’il était possible d’implémenter le protocole de preuve à divulgation nulle d’information tout en contournant le problème des capacités de calcul suffisantes pour casser le code. L’idée consiste à avoir plusieurs fournisseurs de preuve qui doivent convaincre le vérificateur, un peu comme des enquêteurs qui interrogent plusieurs suspects d’un braquage en même temps dans deux cellules différentes pour voir si leurs réponses concordent ou s’ils se contredisent et sont donc en train de mentir.
Dans son expérience, l’équipe des Universités de Genève et de McGill, au Canada, ne cherchait pas à factoriser des grands nombres mais à analyser un graphe colorié avec trois couleurs. Un graphe est constitué de sommets reliés par des arêtes. Pour un graphe donné, il est très difficile de montrer qu’il est possible de le colorier avec juste trois couleurs de sorte que toutes les paires de sommets reliés par une arête soient de couleurs différentes. En revanche, il est très simple de vérifier qu’une solution fonctionne. Pour ces raisons, les mathématiciens classent le coloriage des graphes en trois couleurs dans la catégorie des problèmes de complexité dite "NP" (ce qui est aussi le cas de la factorisation des grands nombres). En choisissant un problème de complexité NP, les chercheurs s’assurent qu’un tiers mal intentionné ne peut pas déterminer facilement le coloriage d’un graphe.
Ici, les fournisseurs de preuve partagent un graphe dont ils connaissent le coloriage. Le vérificateur choisit au hasard une paire de sommets connectés par une arête, puis interroge simultanément les deux fournisseurs et demande à chacun d’annoncer la couleur d’un des deux sommets. Le vérificateur itère de nombreuses fois cette opération pour s’assurer de la cohérence des réponses des deux fournisseurs de preuve. Dans l’expérience, le graphe contient 588 sommets et 1 097 arêtes. Le vérificateur reproduit le test environ 500 000 fois pour garantir la sécurité du protocole. Il peut ainsi confirmer l’identité des fournisseurs de preuve, sans pour autant connaître le coloriage du graphe (pour être précis, les fournisseurs de preuve partagent une série de coloriages qu’ils changent de la même façon à chaque question).
Comme pour les suspects d’un braquage, les deux fournisseurs de preuve ne doivent pas pouvoir communiquer pour synchroniser leurs réponses : il faut que le système de question-réponse fonctionne plus rapidement que le temps nécessaire à un signal pour transiter d’un fournisseur de preuve à l’autre. Rappelons que la lumière se déplace dans le vide à la vitesse de 300 000 kilomètres par seconde, une vitesse qui ne peut être dépassée, d’après la théorie de la relativité restreinte. Avec un distributeur de billets large d’un mètre, Alice utiliserait deux dispositifs servant de fournisseurs de preuve de son identité qu’elle doit insérer aux deux extrémités de la machine. Le système devrait alors réaliser chaque test en moins de 3,3 nanosecondes, ce qui semblait techniquement impossible !
Avec un protocole optimisé, les chercheurs ont mis en place ce dispositif dans deux expériences. Dans la première, les deux fournisseurs de preuve sont distants de 400 mètres et les questions sont synchronisées grâce à une horloge GPS ; dans la seconde, la distance est de seulement 60 mètres et la synchronisation se fait avec une fibre optique. Chaque test est effectué assez vite de sorte que les fournisseurs de preuve ne puissent pas communiquer entre eux, contraints par la vitesse finie de transmission de l’information. L’ensemble du processus de confirmation de l’identité est réalisé en une seconde.
Ce résultat montre que le protocole d’identification sans divulgation d’information peut être implémenté sur des distances assez courtes, et il serait encore possible de les réduire. Les chercheurs envisagent de nombreuses applications en dehors des distributeurs, par exemple pour les systèmes de vote électronique, la signature de contrats électroniques, etc. « Cette approche est vraiment intéressante », souligne Nicolas Brunner, de l’Université de Genève, « car la sécurité du système repose sur les lois de la physique, et non plus sur une hypothèse limitant le pouvoir de calcul ou le niveau de technologie de l’espion ».
Par ailleurs, des questions intéressantes émergent quand on ajoute la mécanique quantique dans le dispositif. Que se passe-t-il si les deux fournisseurs de preuve sont intriqués ? L’intrication quantique est un phénomène dans lequel deux objets (typiquement deux particules) ont des propriétés corrélées et forment un système lié. De nombreuses expériences ont permis de montrer que l’intrication quantique est un phénomène non local, c’est-à-dire qu’une opération menée sur une particule altère instantanément les propriétés de l’autre, peu importe la distance qui les sépare. Ce phénomène pourrait-il aider les fournisseurs de preuve à déjouer le test d’identification ? « Nous avons des raisons de penser que notre protocole est sûr face à des fournisseurs de preuve quantique », note Nicolas Brunner, « mais nous n’avons pas encore de preuve formelle. C’est une question intéressante à laquelle les théoriciens doivent s’atteler ».
Article rédigé par Georges Simmonds pour RT Flash
