Un algorithme quantique menace de rendre inutiles nos principaux systmes cryptographiques plus rapidement que prvu. Dans un article de recherche publi rcemment, un informaticien l’universit de New York dcrit un nouvel algorithme quantique qui serait une version amliore 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 prliminaire estime que l’algorithme dcouvert par le chercheur de l’universit de New York propose un schma qui pourrait rduire considrablement le nombre de portes, ou d’tapes logiques, ncessaires pour factoriser de trs grands nombres.
Un nouvel algorithme quantique menace les systmes de chiffrement actuels sur Internet
L’informatique quantique fait l’objet d’un battage mdiatique constant, mais des points d’interrogation importants subsistent quant l’utilit relle des ordinateurs quantiques. L’on espre que l’informatique quantique va contribuer aux processus de recherche de donnes volumineuses, ainsi qu’au dveloppement rapide de l’IA et de l’apprentissage automatique. L’informatique quantique pourrait mme rvolutionner nos sources d’nergie domestique, en fournissant de l’nergie lectrique base sur les processus de fusion nuclaire. 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 scurit des donnes en ligne et exposerait des systmes hautement sensibles toute sorte de violation. Les nigmes mathmatiques qui sous-tendent les principaux systmes 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 mathmatiques appliques au MIT, s’est lanc sur cette voie et a propos un algorithme rvolutionnaire 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 cls secrtes utilises pour scuriser la plupart des informations chiffres envoyes sur Internet. Depuis sa dcouverte, il y a 30 ans, l’algorithme de Shor est considr comme un exemple des promesses des ordinateurs quantiques.
Aujourd’hui, Oded Regev, un informaticien de l’universit de New York, a rvl un nouvel algorithme quantique qui pourrait tre meilleur que celui de Shor. Dans un article publi sur le serveur arXiv le 12 aot, Regev propose un schma qui pourrait rduire considrablement le nombre de portes, ou d’tapes logiques, ncessaires pour factoriser de trs grands nombres. En principe, cela pourrait permettre un ordinateur quantique plus petit de dcouvrir les cls de cryptage secrtes ou une machine plus grande de les dcoder plus rapidement. Cela aura-t-il un effet rel ? Mon sentiment est que oui, cela pourrait avoir une chance , a-t-il dclar.
Les cryptographes indpendants ayant valu le travail semblent intrigus. Dans le monde de l’informatique quantique, deux ou trois nouvelles ides sont apparues au cours des 30 dernires annes, depuis Shor. On ne voit pas ces nouvelles ides 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 rsultat est surprenant et super cool . Il s’attend une salle comble le mois prochain lorsque Regev prsentera son nouvel algorithme en novembre.
Les chercheurs affirment qu’une amlioration de l’algorithme de Shor serait une prouesse
Comme tous les algorithmes quantiques, l’algorithme de Shor repose sur les proprits mystrieuses des bits quantiques (qubits) qui peuvent tre rgls sur des valeurs non seulement 0 et 1, mais galement sur une superposition de 0 et 1 en mme temps. De petits nombres de ces qubits peuvent tre assembls pour former des portes, qui excutent les oprations logiques d’un algorithme. Pour factoriser un nombre de n bits, l’algorithme de Shor ncessite un circuit quantique de n2 portes. Selon un rcent article de Science, la plupart des chiffrements sur Internet reposent dsormais sur des nombres d’au moins 2 048 bits.
Ainsi, trouver leurs facteurs premiers avec l’algorithme de Shor ncessiterait donc des ordinateurs quantiques dots d’au moins 4 millions de portes. Or, les plus puissants ordinateurs quantiques ce jour ne possdent que quelques centaines de qubits. Aucun d’entre eux n’atteint la puissance ncessaire pour factoriser des nombres qui nous intressent , explique Brown. En outre, le bruit ambiant dtruit souvent les dlicats tats de superposition des qubits, ruinant ainsi l’opration. Selon Vaikuntanathan, il est possible de remdier au bruit en corrigeant les erreurs, mais cela ncessite encore plus de qubits – des millions, voire des milliards.
La correction d’erreurs fait vraiment exploser le systme. C’est pourquoi nous sommes encore loin de pouvoir factoriser des nombres 1 000 chiffres. L’amlioration de la correction des erreurs serait utile, mais l’amlioration 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 leves. Plusieurs grands nombres doivent tre multiplis ensemble avant d’obtenir un rsultat. Regev a ralis qu’il pouvait multiplier plusieurs nombres dans diffrentes dimensions.
Les puissances d’un mme nombre ne sont pas aussi leves. Selon une analyse prliminaire, bien que les algorithmes de Shor et de Regev ncessitent peu prs le mme nombre total de multiplications, le caractre multidimensionnel de celui de Regev signifie que les nombres multiplis ne sont pas aussi grands avant d’obtenir un rsultat. 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 premire amlioration substantielle de l’algorithme de Shor depuis 30 ans. Personne n’a vraiment russi faire mieux que de rduire un peu la taille de l’algorithme , affirme Vaikuntanathan.
Le nouvel algorithme quantique de Regev prsente galement quelques inconvnients
Martin Eker, chercheur en informatique quantique auprs du gouvernement sudois, explique que l’algorithme de Regev prsente aussi des inconvnients. Regev dit avoir consult le chercheur Eker pour comprendre les implications pratiques de son travail. Sa structure semble ncessiter une mmoire quantique pour stocker les valeurs intermdiaires pendant le calcul, ce qui signifie qu’il faut davantage de ces qubits si dlicats. Cela augmente le cot de l’algorithme , explique Eker. Regev reconnat que les exigences en matire de mmoire posent problme, mais il estime que l’algorithme pourrait tout de mme s’avrer utile.
Cet algorithme pourrait s’avrer trs utile lorsque la mmoire sera moins chre et que nous nous proccuperons plutt du nombre d’oprations , a dclar Regev. Il est difficile de prdire le moment o cela arrivera en raison des progrs relativement lents dans le domaine de l’informatique quantique. Selon le rapport Science, lorsque les ordinateurs quantiques seront prts 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 dpchent pour mettre au point de nouveaux algorithmes qui seront l’preuve des quanta.
Certains chercheurs se tournent dj vers des solutions telles que la cryptographie dite en treillis, qui serait l’abri du piratage quantique. La cryptographie base sur les treillis utilise une simple algbre linaire pour chiffrer les donnes. Elle comprend des treillis, des vecteurs et des bases qui sont utiliss pour construire un modle difficile. Le National Institute of Standards and Technology (NIST) des tats-Unis travaille galement sur le sujet et a recommand l’anne dernire la normalisation de nouveaux algorithmes cryptographiques afin de garantir la protection des donnes 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 appliqus rtroactivement, pour dchiffrer le trafic enregistr dans le prsent et le pass rcent , explique Eker. Sans les ordinateurs quantiques, l’un des quatre algorithmes de chiffrement recommands par le NIST comme tant susceptibles de rsister aux quanta a t craqu en une heure par des chercheurs utilisant un seul cur d’un processeur Intel Xeon, sorti en 2013. Ils se sont appuys sur les mathmatiques pures pour le craquer.
Quoi qu’il en soit, Brown estime que la nouveaut mme des travaux de Regev est susceptible d’inspirer et de gnrer d’autres ides nouvelles dans le domaine de la cryptographie quantique, qui a eu du mal faire des perces significatives. J’essaie moi-mme de rflchir des moyens d’aller plus loin , a dclar Brown.
Source : rapport de l’tude
Et vous ?
Quel est votre avis sur le sujet ?
Que pensez-vous de l’algorithme de factorisation quantique dcrit ci-dessus ?
Que reprsente cette dcouverte pour les systmes de chiffrement classiques ?
Les ordinateurs quantiques capables d’exploiter ces algorithmes sont-ils pour bientt ?
Pensez-vous que les algorithmes de chiffrement actuels rsisteront encore longtemps aux quanta ?
Voir aussi