Avertissement : Cet algorithme s'autodétruira après son utilisation

Imaginez deux millionnaires - Alice et Bob - qui veulent décider qui est le plus riche mais sans révéler leur richesse. Comment font-ils pour résoudre leur énigme ? Il s'agit du problème du millionnaire de Yao, conçu par l'informaticien Andrew Yao en 1982.

Une solution potentielle est un programme informatique unique. Ce programme permet à Alice et Bob d'entrer leurs données en privé, d'effectuer le calcul une fois, de donner la réponse puis de se détruire. Cela garantit que personne ne peut accéder aux données d'origine ou à la manière dont elles ont été traitées. Et cela donne à Alice et Bob leur réponse sans compromettre leurs détails financiers.

Les experts en sécurité informatique affirment que les programmes ponctuels sont un outil extrêmement important en matière de cybersécurité. Ou ils le seraient, si quelqu'un pouvait les construire.

Il s'avère qu'il est impossible de construire un programme unique idéal qui s'exécute une fois puis se détruit. Un ordinateur classique de ce type devrait être physiquement détruit pour s'assurer qu'il ne peut plus être utilisé, et il n'existe aucun moyen connu de le garantir.

Un ordinateur quantique pourrait sembler offrir plus de potentiel, car les informations quantiques sont facilement détruites et impossibles à copier. Mais il s'avère qu'un ordinateur quantique ne peut pas donner une réponse déterministe à un calcul ponctuel.

Ainsi, le rêve d'un programme ponctuel qui se détruit après un seul calcul semble voué à l'échec.

Entrez Marie-Christine Roehsner à l'Université de Vienne et Joshua Kettlewell à l'Université nationale de Singapour et quelques copains. Aujourd'hui, ils disent avoir trouvé un moyen de créer un programme ponctuel et avoir construit et démontré un dispositif de preuve de principe pour la première fois.

La nouvelle méthode repose sur une façon différente de penser les programmes ponctuels exécutés par les ordinateurs quantiques. Jusqu'à présent, les experts en sécurité ont toujours attendu une solution définitive : la valeur de Bob est soit supérieure, soit inférieure à celle d'Alice.

Mais la mécanique quantique est un processus intrinsèquement probabiliste, ce qui signifie qu'elle ne peut donner la bonne réponse que dans certaines limites de probabilité, disons 75 % du temps. Tant qu'Alice et Bob sont prêts à accepter la possibilité d'une erreur de calcul, il est alors possible de garantir que leurs informations resteront sécurisées, que le programme ne s'exécutera qu'une seule fois puis s'autodétruira.

Nous assouplissons la définition des programmes ponctuels pour permettre une certaine probabilité d'erreur dans la sortie et montrons que la mécanique quantique offre des avantages de sécurité par rapport aux ressources purement classiques, disent les chercheurs.

L'approche est simple. Alice encode secrètement sa richesse dans les états d'un ensemble de qubits stockés dans un ordinateur quantique. Cet ordinateur est programmé pour comparer ce nombre avec celui entré par Bob et lui dire si sa richesse est supérieure ou inférieure à celle d'Alice.

Ce traitement quantique est lui-même un processus irréversible, ce qui empêche Bob d'entrer d'autres nombres pour déterminer la richesse d'Alice.

Mais le matériel est fixe et une faiblesse potentielle de cette approche est que Bob peut désosser le programme en déterminant comment les portes logiques sont câblées.

Roehsner et co ont une astuce pour empêcher cela, cependant. Bien qu'ils ne puissent pas masquer le câblage physique, ils peuvent masquer les tables de vérité qui régissent le comportement de chaque porte logique. En effet, notre approche consiste à coder la table de vérité pour les portes individuelles comme un programme ponctuel à part entière, disent-ils.

Cela permet aux informations d'Alice d'être encodées dans le choix précis des portes logiques et non sur les connexions entre elles. De cette façon, il reste caché à Bob.

Roehsner et co ont testé cette idée dans une expérience de preuve de principe. Celui-ci encode les informations de polarisation des photons et les traite à l'aide de différents types de portes logiques optiques. La probabilité moyenne de succès pour chacune des portes est de 75 %, ce qui, selon l'équipe, est en bon accord avec la valeur attendue.

L'équipe a ensuite utilisé cette configuration pour résoudre le problème du millionnaire de Yao pour des nombres composés de quatre bits qui diffèrent d'un seul bit. Le programme fonctionne en comparant chaque bit pour décider lequel est le plus grand.

Les résultats rendent la lecture intéressante. L'équipe affirme que la probabilité de succès augmente avec le nombre de bits utilisés pour la correction d'erreurs, mais cela réduit également la sécurité du système. Il y a donc un compromis évident entre précision et sécurité. Néanmoins, l'équipe affirme que la sécurité est meilleure que celle qui peut être obtenue avec l'informatique classique seule.

Nos résultats démontrent que la physique quantique permet de meilleurs compromis de sécurité pour certaines tâches informatiques sécurisées que ce qui est possible dans le monde classique, même lorsqu'une sécurité parfaite ne peut pas être atteinte, disent-ils.

De plus, la méthode est réalisable avec la technologie actuelle, et des progrès relativement modestes devraient encore accroître la sécurité.

C'est un travail intéressant qui montre le potentiel des technologies quantiques pour augmenter considérablement la sécurité en utilisant la technologie disponible aujourd'hui. Nous pensons que le travail présenté fait fortement allusion à un riche domaine de protocoles quantiques pour améliorer la sécurité du calcul classique, avant même que des ordinateurs quantiques à grande échelle puissent être réalisés, disent Roehsner et co.

Il sera intéressant de voir comment le travail est reçu.

Réf : arxiv.org/abs/1709.09724 : Avantage quantique pour les programmes probabilistes ponctuels

cacher