Supposément plus efficace que l’algorithme de Shor vieux de 30 ans
Un algorithme quantique menace de rendre inutiles nos principaux systèmes cryptographiques plus rapidement que prévu. Dans un article de recherche publié récemment, un informaticien à l’université de New York décrit un nouvel algorithme quantique qui serait une version améliorée de l’algorithme de Shor, un algorithme quantique qui factorise un entier naturel n en temps O((\log N)^{3}) et en espace O(\log N). Une analyse préliminaire estime que l’algorithme découvert par le chercheur de l’université de New York propose un schéma qui pourrait réduire considérablement le nombre de portes, ou d’étapes logiques, nécessaires pour factoriser de très grands nombres.
Un nouvel algorithme quantique menace les systèmes de chiffrement actuels sur Internet
L’informatique quantique fait l’objet d’un battage médiatique constant, mais des points d’interrogation importants subsistent quant à l’utilité réelle des ordinateurs quantiques. L’on espère que l’informatique quantique va contribuer aux processus de recherche de données volumineuses, ainsi qu’au développement rapide de l’IA et de l’apprentissage automatique. L’informatique quantique pourrait même révolutionner nos sources d’énergie domestique, en fournissant de l’énergie électrique basée sur les processus de fusion nucléaire. Cependant, on ne sait toujours pas dans quelle mesure les ordinateurs quantiques seront plus pratiques et plus rapides.
Les chercheurs semblent toutefois unanimes sur un point : un ordinateur quantique suffisamment puissant pourrait craquer les algorithmes de chiffrement existants. Il remettrait ainsi en cause la sécurité des données en ligne et exposerait des systèmes hautement sensibles à toute sorte de violation. Les énigmes mathématiques qui sous-tendent les principaux systèmes cryptographiques actuels sont pratiquement insolubles pour les ordinateurs classiques, mais elles seraient tout à fait accessibles à un ordinateur quantique suffisamment puissant. Toutefois, les processeurs quantiques d’aujourd’hui sont loin d’atteindre l’échelle requise pour les craquer.
En 1994, Peter Shor, chercheur en mathématiques appliquées au MIT, s’est lancé sur cette voie et a proposé un algorithme révolutionnaire pour y parvenir. Connu pour son travail sur le calcul quantique, Shor a montré comment un ordinateur quantique pouvait être exponentiellement plus rapide qu’un ordinateur classique pour trouver les facteurs premiers de grands nombres. Ces nombres premiers composent les clés secrètes utilisées pour sécuriser la plupart des informations chiffrées envoyées sur Internet. Depuis sa découverte, il y a 30 ans, l’algorithme de Shor est considéré comme un exemple des promesses des ordinateurs quantiques.
Aujourd’hui, Oded Regev, un informaticien de l’université de New York, a révélé un nouvel algorithme quantique qui pourrait être meilleur que celui de Shor. Dans un article publié sur le serveur arXiv le 12 août, Regev propose un schéma qui pourrait réduire considérablement le nombre de portes, ou d’étapes logiques, nécessaires pour factoriser de très grands nombres. En principe, cela pourrait permettre à un ordinateur quantique plus petit de découvrir les clés de cryptage secrètes ou à une machine plus grande de les décoder plus rapidement. « Cela aura-t-il un effet réel ? Mon sentiment est que oui, cela pourrait avoir une chance », a-t-il déclaré.
Les cryptographes indépendants ayant évalué le travail semblent intrigués. « Dans le monde de l’informatique quantique, deux ou trois nouvelles idées sont apparues au cours des 30 dernières années, depuis Shor. On ne voit pas ces nouvelles idées tous les jours, et c’est ce qui nous donne de l’espoir », note Vinod Vaikuntanathan, informaticien au MIT. Kenneth Brown, chercheur en informatique quantique à l’université de Duke, affirme : « comme tout le monde étudie l’algorithme de Shor depuis longtemps, ce résultat est surprenant et super cool ». Il s’attend à une salle comble le mois prochain lorsque Regev présentera son nouvel algorithme en novembre.
Les chercheurs affirment qu’une amélioration de l’algorithme de Shor serait une prouesse
Comme tous les algorithmes quantiques, l’algorithme de Shor repose sur les propriétés mystérieuses des bits quantiques (qubits) qui peuvent être réglés sur des valeurs non seulement 0 et 1, mais également sur une superposition de 0 et 1 en même temps. De petits nombres de ces qubits peuvent être assemblés pour former des portes, qui exécutent les opérations logiques d’un algorithme. Pour factoriser un nombre de n bits, l’algorithme de Shor nécessite un circuit quantique de n2 portes. Selon un récent article de Science, la plupart des chiffrements sur Internet reposent désormais sur des nombres d’au moins 2 048 bits.
Ainsi, trouver leurs facteurs premiers avec l’algorithme de Shor nécessiterait donc des ordinateurs quantiques dotés d’au moins 4 millions de portes. Or, les plus puissants ordinateurs quantiques à ce jour ne possèdent que quelques centaines de qubits. « Aucun d’entre eux n’atteint la puissance nécessaire pour factoriser des nombres qui nous intéressent », explique Brown. En outre, le bruit ambiant détruit souvent les délicats états de superposition des qubits, ruinant ainsi l’opération. Selon Vaikuntanathan, il est possible de remédier au bruit en corrigeant les erreurs, mais cela nécessite encore plus de qubits – des millions, voire des milliards.
« La correction d’erreurs fait vraiment exploser le système. C’est pourquoi nous sommes encore loin de pouvoir factoriser des nombres à 1 000 chiffres. L’amélioration de la correction des erreurs serait utile, mais l’amélioration de l’algorithme de Shor le serait tout autant », explique-t-il. Dans son rapport, Regev affirme avoir trouvé un moyen d’y parvenir. L’algorithme de Shor est 1D. Il recherche les facteurs premiers en élevant un seul nombre à des puissances élevées. Plusieurs grands nombres doivent être multipliés ensemble avant d’obtenir un résultat. Regev a réalisé qu’il pouvait multiplier plusieurs nombres dans différentes dimensions.
Les puissances d’un même nombre ne sont pas aussi élevées. Selon une analyse préliminaire, bien que les algorithmes de Shor et de Regev nécessitent à peu près le même nombre total de multiplications, le caractère multidimensionnel de celui de Regev signifie que les nombres multipliés ne sont pas aussi grands avant d’obtenir un résultat. Finalement, il a constaté qu’il n’avait besoin que de n1,5 portes pour factoriser un entier de n bits. « Il s’agit de la première amélioration substantielle de l’algorithme de Shor depuis 30 ans. Personne n’a vraiment réussi à faire mieux que de réduire un peu la taille de l’algorithme », affirme Vaikuntanathan.
Le nouvel algorithme quantique de Regev présente également quelques inconvénients
Martin Ekerå, chercheur en informatique quantique auprès du gouvernement suédois, explique que l’algorithme de Regev présente aussi des inconvénients. Regev dit avoir consulté le chercheur Ekerå pour comprendre les implications pratiques de son travail. « Sa structure semble nécessiter une mémoire quantique pour stocker les valeurs intermédiaires pendant le calcul, ce qui signifie qu’il faut davantage de ces qubits si délicats. Cela augmente le coût de l’algorithme », explique Ekerå. Regev reconnaît que les exigences en matière de mémoire posent problème, mais il estime que l’algorithme pourrait tout de même s’avérer utile.
« Cet algorithme pourrait s’avérer très utile lorsque la mémoire sera moins chère et que nous nous préoccuperons plutôt du nombre d’opérations », a déclaré Regev. Il est difficile de prédire le moment où cela arrivera en raison des progrès relativement lents dans le domaine de l’informatique quantique. Selon le rapport Science, lorsque les ordinateurs quantiques seront prêts à trouver les facteurs premiers en appliquant l’algorithme de Regev ou de Shor, le chiffrement d’Internet aura peut-être évolué. Conscients de la menace, les experts en cryptographie se dépêchent pour mettre au point de nouveaux algorithmes qui seront à l’épreuve des quanta.
Certains chercheurs se tournent déjà vers des solutions telles que la cryptographie dite en treillis, qui serait à l’abri du piratage quantique. La cryptographie basée sur les treillis utilise une simple algèbre linéaire pour chiffrer les données. Elle comprend des treillis, des vecteurs et des bases qui sont utilisés pour construire un modèle difficile. Le National Institute of Standards and Technology (NIST) des États-Unis travaille également sur le sujet et a recommandé l’année dernière la normalisation de nouveaux algorithmes cryptographiques afin de garantir la protection des données à mesure que les ordinateurs quantiques deviennent plus performante.
Mais les chercheurs en informatique quantique affirment que cela n’écarte pas totalement les risques que posent les ordinateurs quantiques. « Des algorithmes comme ceux de Regev et Shor pourraient être appliqués rétroactivement, pour déchiffrer le trafic enregistré dans le présent et le passé récent », explique Ekerå. Sans les ordinateurs quantiques, l’un des quatre algorithmes de chiffrement recommandés par le NIST comme étant susceptibles de résister aux quanta a été craqué en une heure par des chercheurs utilisant un seul cœur d’un processeur Intel Xeon, sorti en 2013. Ils se sont appuyés sur les mathématiques pures pour le craquer.
Quoi qu’il en soit, Brown estime que la nouveauté même des travaux de Regev est susceptible d’inspirer et de générer d’autres idées nouvelles dans le domaine de la cryptographie quantique, qui a eu du mal à faire des percées significatives. « J’essaie moi-même de réfléchir à des moyens d’aller plus loin », a déclaré Brown.
source : developpez
