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)...
La fin de cet article est réservée aux abonnés. Soutenez le Club Developpez.com en prenant un abonnement pour que nous puissions continuer à vous proposer des publications.
Envoyé par floyer
).