L’algorithme quantique de Daniel Simon menace-t-il ML-KEM et ML-DSA ?

L’enjeu est important : depuis les travaux d’Oded Regev, le DCP sert de point de passage théorique vers certains problèmes de réseaux, eux-mêmes au cœur d’une grande partie de la cryptographie post-quantique . Mais entre une revendication mathématique et une attaque exploitable contre des standards comme ML-KEM ou ML-DSA, il reste plusieurs étapes — et la première consiste à vérifier la preuve.

Ce que revendique la prépublication

Un solveur du DCP en temps polynomial

Le DCP est un problème lié à la récupération d’une information cachée dans des états quantiques associés à une structure diédra​​le. Il est étudié comme une instance particulière du problème des sous-groupes cachés, un domaine où les ordinateurs quantiques ont déjà produit des accélérations spectaculaires dans certains cas.

Simon affirme que son algorithme résout le DCP en temps polynomial sur un ordinateur quantique. Sa démarche s’appuie notamment sur la réduction publiée par Regev en 2002, qui relie le problème du sous-groupe diédral au DCP .

Une lacune théorique d’environ vingt ans

Depuis que ces réductions ont établi un lien avec les problèmes de réseaux, une question restait ouverte : cette connexion pouvait-elle être exploitée par un algorithme quantique réellement efficace pour le DCP ?

Si la démonstration de Simon est correcte, elle comblerait cette lacune restée ouverte depuis environ 2004 . Ce serait une avancée fondamentale en théorie de la complexité quantique, indépendamment de toute attaque immédiate contre un protocole déployé.

Une technique dite « block-and-query »

La contribution technique centrale consiste, selon la prépublication, à remplacer un oracle utilisé dans des approches antérieures par une méthode de type « block-and-query ». Celle-ci vise à extraire l’information du sous-groupe caché à partir d’échantillons quantiques imparfaits ou bruités .

Le document affirme également que l’algorithme pourrait fonctionner malgré un taux d’échantillons défectueux allant jusqu’à 1/O(log n). Cette tolérance serait nécessaire pour le combiner efficacement aux réductions existantes vers des problèmes de réseaux .

Pourquoi les problèmes de réseaux sont concernés

La prépublication affirme que l’algorithme de Simon peut être combiné à la réduction de Regev, ainsi qu’aux améliorations proposées par Brakerski, Kirshanova, Stehlé et Wen . Cette combinaison fournirait des algorithmes quantiques en temps polynomial pour plusieurs problèmes de réseaux, notamment :

• une approximation à facteur polynomial du problème du plus court vecteur (SVP) ;
• le problème Learning With Errors (LWE), qui consiste à retrouver une structure mathématique à partir d’équations volontairement brouillées par du bruit .

C’est ce lien avec LWE qui explique l’attention portée à cette annonce. Toutefois, il faut éviter un raccourci important : « résoudre certains problèmes de réseaux » ne signifie pas automatiquement « casser ML-KEM et ML-DSA ».

Une vérification encore loin d’être acquise

Au 7-8 août 2026, la réaction dominante est la prudence, voire un scepticisme marqué .

Pas encore d’évaluation par les pairs

Le document est une prépublication, et non un article accepté par une revue ou une conférence. Plusieurs étapes normales de la vérification scientifique — lecture détaillée par des spécialistes, tentatives de reproduction et confrontation des paramètres — restent donc à venir .

Des preuves essentielles présentées sous forme d’esquisses

Des analyses préliminaires signalent que plusieurs arguments déterminants sont seulement esquissés. La dernière conséquence annoncée pour les paramètres de SVP et de LWE s’appuierait en partie sur des communications personnelles non publiées, plutôt que sur des dérivations accessibles dans la littérature .

Ces réserves ne réfutent pas le résultat. Elles signifient que les points dont dépend toute la conclusion doivent encore être examinés ligne par ligne.

Aucune confirmation indépendante

Dans les jours qui ont suivi la mise en ligne, aucune vérification ni réfutation indépendante n’avait encore été publiée . La position de nombreux observateurs peut se résumer ainsi : établir les faits avant de réagir aux conséquences les plus spectaculaires.

Ce que cela change — et ne change pas — pour ML-KEM et ML-DSA

Pour les organisations qui déploient ou évaluent les standards post-quantiques du NIST, la conclusion immédiate est simple : il n’y a pas de raison de changer de stratégie sur la base de cette seule prépublication .

Aucun cassage de standard

Le document ne présente pas d’attaque implémentée contre ML-KEM, le mécanisme d’encapsulation de clés défini par FIPS 203, ni contre ML-DSA, l’algorithme de signature défini par FIPS 204 . Aucun jeu de paramètres du NIST n’a été attaqué .

Un lien théorique, pas une attaque directe

ML-KEM repose sur Module-LWE, tandis que ML-DSA repose notamment sur Module-SIS et des hypothèses de réseaux structurés. Le DCP est relié à des problèmes de réseaux par des réductions connues, mais il faut encore démontrer que cette chaîne produit une attaque concrète contre ces hypothèses précises .

Autrement dit, même si le DCP était effectivement résoluble en temps polynomial, l’impact sur les standards dépendrait des détails de la réduction, de sa portée et de sa traduction en attaque sur les structures modulaires utilisées par ML-KEM et ML-DSA.

Le contexte des résultats précédents

En 2025, Bai, Jangir, Kirshanova, Ngo et Youmans ont présenté un algorithme quantique en temps quasi polynomial pour une variante restreinte du DCP : l’extrapolated Dihedral Coset Problem sur des modules puissances de deux .

La revendication de Simon — un temps polynomial pour le DCP complet — représenterait donc un saut important par rapport à ce résultat. Elle s’inscrit dans une progression réelle des travaux sur la famille de problèmes, mais reste à confirmer.

La réponse des experts : vérifier avant de s’alarmer

Les premiers commentaires d’analystes de la sécurité post-quantique évoquent un « scepticisme marqué », principalement en raison du caractère esquissé de certaines preuves et du recours à des références non publiées .

Les conséquences pour la cryptographie sur réseaux sont aussi conditionnelles : elles dépendent de la validité de la preuve et du chemin exact suivi par les réductions, et non de la seule affirmation selon laquelle le DCP serait facile à résoudre .

Aucune prise de position institutionnelle majeure du NIST, de laboratoires universitaires ou d’organismes de normalisation n’avait encore été publiée au moment des premières réactions, ce qui n’a rien d’étonnant pour un document rendu public quelques jours auparavant .

Conclusion : une alerte scientifique, pas une crise opérationnelle

La prépublication de Daniel Simon pourrait, si elle résiste à l’examen, modifier profondément la compréhension théorique de certains problèmes de réseaux face aux ordinateurs quantiques. Elle mérite donc une analyse attentive et indépendante.

Mais elle ne constitue pas aujourd’hui une attaque contre ML-KEM, ML-DSA ou un autre standard post-quantique. Les paramètres du NIST restent inchangés, et les organisations n’ont pas de raison immédiate d’interrompre leurs migrations ou de revoir leurs calendriers de déploiement sur la seule base de cette revendication .

Le bon réflexe est donc moins la panique que la veille : suivre les vérifications de la preuve, les éventuelles corrections de la prépublication et les travaux qui chercheront à établir — ou à exclure — un lien concret avec les hypothèses exactes des standards post-quantiques.