OpenAI a annoncé le 26 octobre 2026 que l’un de ses systèmes d’IA avait réfuté l’hypothèse du temps exponentiel (« Exponential Time Hypothesis », abrégée ETH), et une partie des réseaux sociaux crypto a lu le titre « ETH is false » comme une nouvelle sur Ethereum. blockchain that runs exactly as written when it is called, holding and moving funds according to its code, without an intermediary able to change the outcome.">smart contract holding reserves of two or more tokens, supplied by users, that a decentralized exchange uses to execute trades automatically at a price set by a formula.">pool diverge, compared with simply holding the same tokens in a wallet. It becomes permanent when the provider withdraws.">Il n’en est rien. Ici, ETH désigne une conjecture d’informatique théorique de 1999, formulée par Russell Impagliazzo et Ramamohan Paturi, sur la difficulté d’un problème de logique appelé 3-SAT. Selon son annonce, OpenAI a publié sur son dépôt GitHub public un manuscrit de 67 pages et une formalisation en Lean.
L’affirmation n’a pas été vérifiée de façon indépendante. Les trois informaticiens qu’OpenAI a chargés de superviser le contrôle, Impagliazzo et Paturi (UC San Diego) et Ryan Williams (MIT), écrivent dans une lettre ouverte publiée le même jour : « Notre participation ne doit pas être prise pour une certification de l’affirmation. » Rien dans le manuscrit ne s’en prend à SHA-256, la fonction de hachage qui sous-tend le minage et les adresses de bitcoin, ni aux signatures sur courbe elliptique qui protègent les clés bitcoin. Le seul passage du texte sur l’inversion de fonctions porte sur une famille de constructions théoriques, et même là, les auteurs précisent que leur résultat n’exclut pas qu’une fonction soit à sens unique face à des algorithmes polynomiaux.
Le bitcoin s’échangeait vers 80 850 $ à 05 h 43 UTC le 28 octobre, en hausse de 1,39 % sur 24 heures. Rien dans les données de marché ne relie ce mouvement à cette affaire. Aucune conséquence ne ressort non plus, à ce stade, pour les détenteurs en euros : nous n’avons trouvé aucune réaction de régulateur, en France comme ailleurs en Europe.
Ce qu’OpenAI affirme sur l’hypothèse du temps exponentiel
L’hypothèse du temps exponentiel (ETH) affirme que 3-SAT n’admet aucun algorithme sous-exponentiel : il existerait une constante fixe c strictement positive telle que, dans le pire cas, décider si une formule 3-SAT à n variables est satisfiable demande au moins environ 2 puissance c fois n étapes. Une formule 3-SAT est une longue liste de petites conditions sur des variables vrai-ou-faux, trois variables par condition, et la question est de savoir s’il existe une affectation qui les satisfait toutes à la fois. Les chercheurs s’appuient depuis des décennies sur cette hypothèse comme hypothèse de travail : la page d’OpenAI indique qu’elle sert dans des centaines d’articles pour établir des résultats de difficulté en théorie des graphes, en bases de données, en géométrie algorithmique et en biologie computationnelle.
Le manuscrit, intitulé « The Exponential Time Hypothesis is False » (« L’hypothèse du temps exponentiel est fausse ») et attribué à « OpenAI », est daté du 17 octobre et révisé le 25 octobre 2026. Il décrit un algorithme déterministe qui compte exactement le nombre d’affectations satisfaisant n’importe quelle formule k-CNF (la version générale, avec k variables par condition, pour tout k fixé supérieur ou égal à 2). Le temps d’exécution croît comme 2 puissance n divisé par environ la racine carrée de log n, avec une mémoire polynomiale. Compter est au moins aussi difficile que décider s’il existe une solution : si l’algorithme et son analyse sont corrects, l’hypothèse est donc fausse. Pour l’instant, c’est ce que revendique OpenAI, et cela reste à établir.
La page d’OpenAI le formule ainsi : « our system has recently proved that the ETH is false, a result that was subsequently verified in Lean », soit « notre système a récemment démontré que l’ETH est fausse, un résultat ensuite vérifié en Lean ». Elle date les étapes : l’IA a trouvé son argument en langage naturel le 16 octobre, et l’équipe l’a formalisé en Lean, un programme qui contrôle un raisonnement mathématique ligne par ligne, le 17 octobre. La page prévient aussi que transformer cela en algorithmes plus rapides en pratique « exigera des recherches supplémentaires importantes ».
Les auteurs tracent eux-mêmes les limites. Les bornes de temps de ce type ne survivent pas aux réductions polynomiales générales, écrivent-ils, de sorte que « notre résultat n’implique pas que les problèmes NP généraux admettent des algorithmes sous-exponentiels ». Il n’y a ici aucun algorithme polynomial, et la question P contre NP reste ouverte. Ce qui en découle, selon le texte, c’est un comptage plus rapide qu’exponentiel pour quelques problèmes de graphes, comme les ensembles indépendants, les colorations propres et les couplages parfaits.
Qui vérifie, et ce que couvre la vérification Lean
Le travail « sera vérifié et accompagné », d’après OpenAI, par un groupe mené par Impagliazzo, Paturi et Williams. Impagliazzo et Paturi, avec Francis Zane, sont les auteurs originels de l’hypothèse. OpenAI note que Williams a lui-même réfuté des versions fortes de celle-ci. Dans leur lettre ouverte à leurs collègues, les trois écrivent qu’« un résultat de cette importance exige un examen minutieux et indépendant ». Ils demandent à la communauté de l’informatique théorique de les aider à examiner l’argument, proposent une réunion virtuelle avant la fin de 2026, et indiquent un dépôt communautaire, un formulaire de réponse et un blog de discussion pour contribuer.
Ils écrivent aussi : « Si l’affirmation est correcte, elle changera une partie importante de l’informatique théorique. » La lettre ne dit rien de la cryptographie. Selon OpenAI, l’entreprise a accepté de rendre publiques toutes les données brutes et de financer une conférence sur les implications, à la demande du groupe.
La vérification Lean est plus étroite que la borne annoncée en titre. La note de périmètre d’OpenAI indique que Lean démontre un temps d’exécution un peu plus faible, avec (log log n) au carré dans l’exposant au lieu de log log n, et que la valeur plus fine vient du manuscrit du 25 octobre. La borne plus faible reste inférieure à l’exponentiel : si l’énoncé Lean traduit fidèlement l’hypothèse et l’algorithme, la seule partie vérifiée par machine suffirait à la contredire. Reste à savoir si c’est bien le cas, et les relecteurs ne se sont pas encore prononcés là-dessus.
| Énoncé | Temps d’exécution (n variables) | Origine |
|---|---|---|
| Hypothèse du temps exponentiel (la conjecture) | 3-SAT exige au moins 2cn dans le pire cas, pour une constante c > 0 | Impagliazzo et Paturi, 1999 |
| Manuscrit d’OpenAI, toute formule k-CNF | 2O(n log log n / √log n) | Article, théorème 1.1 (25 octobre) |
| Manuscrit d’OpenAI, formules clairsemées | 2O(n / √log n) | Article, théorème 1.1 |
| Énoncé vérifié par Lean | 2O(n (log log n)² / √log n) | Note de périmètre Lean d’OpenAI |
| Dépôt d’Anthropic, comptage #3-SAT | 2O(n log log n / √log n) | README d’Anthropic (formal-math) |
Les constantes cachées dans chaque O(…) ne sont pas fournies. Sans elles, impossible de dire à partir de ces formules à quelle taille, si tant est qu’il y en ait une, la méthode battrait la recherche exhaustive qui essaie toutes les affectations.
Anthropic a publié un résultat similaire
Anthropic, l’éditeur de Claude, a publié un article intitulé « A 2^o(n) Time Algorithm for 3-SAT », attribué à « Claude (Anthropic) », dans son dépôt public formal-math ; selon Decrypt, l’article est daté du 26 octobre, jour de l’annonce d’OpenAI. Le README indique que l’algorithme compte les solutions de 3-SAT avec le même type de borne, que le résultat a été trouvé par un modèle Claude de recherche interne, et que les preuves Lean ne reposent que sur les trois axiomes standard de Lean. Il ajoute sa propre réserve : Lean vérifie les preuves, mais aucune machine ne vérifie que le fichier d’énoncés dit bien ce que dit l’article. Il précise également : « Le résultat est purement asymptotique et ne dit rien de la résolution de formules en pratique. »
Ce que les spécialistes de la complexité ont dit en premier
Le théoricien de la complexité Scott Aaronson a écrit le 26 octobre sur son blog Shtetl-Optimized qu’un modèle d’OpenAI « a désormais réfuté l’hypothèse du temps exponentiel », avec un temps de 3-SAT qui évolue à peu près comme exp(n/√log(n)). Dans les commentaires, il a fait passer sa probabilité personnelle que P soit égal à NP « de 3 % à 5 % » et résumé l’écart qui subsiste : « une clôture d’un pied de haut a été franchie, alors qu’une clôture de la hauteur de l’Empire State Building reste debout ».
Il insiste aussi sur le fait que le résultat ne concerne que k-SAT, écrivant que « nous n’avons toujours rien de vraiment meilleur que la force brute pour CircuitSAT ou FormulaSAT », les problèmes plus généraux. Interrogé le 27 octobre par un lecteur sur d’éventuelles tentatives d’entreprises d’IA pour casser des algorithmes cryptographiques, il a répondu : « Je n’ai aucune nouvelle d’un cassage de codes cryptographiques. »
Pourquoi SHA-256 et les signatures de bitcoin sont d’autres problèmes
La crainte exprimée dans les fils crypto tenait en un raisonnement : si une IA peut faciliter un problème difficile et célèbre, la cryptographie de bitcoin pourrait être la suivante. Ce raisonnement saute au moins quatre étapes.
Premièrement, l’hypothèse parle de croissance. Elle décrit comment le coût dans le pire cas de 3-SAT se comporte quand le nombre de variables tend vers l’infini. Elle ne dit rien d’une formule précise de taille fixe. Les primitives de bitcoin sont des objets fixes : SHA-256 traite des blocs de 512 bits et renvoie 256 bits, et les clés de signature de bitcoin vivent sur une seule courbe précise, secp256k1. Un énoncé sur ce qui se passe quand n croît sans limite ne change pas, à lui seul, le coût d’une attaque contre une fonction fixe.
Deuxièmement, le gain sur l’exposant est faible et progresse très lentement. Par rapport à 2 puissance n, l’exposant est réduit d’un facteur d’environ la racine carrée de log n, une quantité qui bouge à peine : elle passe d’environ 3 à environ 4 quand n va de dix mille à dix millions de variables. Les constantes n’étant pas publiées, l’article ne donne aucun temps d’exécution pour une formule réelle, aucune implémentation et aucun test de performance.
Troisièmement, la traduction a un coût. Une recherche de préimage de SHA-256 peut en principe s’écrire comme une formule SAT, mais chaque bit intermédiaire du calcul de hachage devient une variable : la formule compte plusieurs milliers de variables, bien plus que les 256 bits de sortie. La nouvelle borne se mesure en variables de la formule, pas en bits du secret. L’article fait lui-même la remarque générale : les bornes de cette forme ne « se transfèrent pas sous des réductions polynomiales générales », car un codage qui gonfle le nombre de variables peut annuler un gain aussi mince. Il ne traite pas du tout de SHA-256. Pour les bases, voir notre guide sur ce qu’est la cryptographie et comment elle protège les cryptomonnaies.
Quatrièmement, les signatures de bitcoin reposent sur un autre problème. Les signatures ECDSA et Schnorr sur secp256k1 dépendent du problème du logarithme discret sur courbe elliptique : retrouver une clé privée à partir d’une clé publique dans un groupe d’environ 2256 éléments. C’est un problème algébrique, et les meilleures attaques classiques connues demandent environ 2128 opérations. Comme presque tout problème dont on peut vérifier la réponse, il pourrait en principe être réécrit en formule SAT, mais l’arithmétique sur courbe elliptique transformerait une clé de 256 bits en une formule comptant beaucoup plus de variables, et la réserve sur les réductions vaut de nouveau. Le manuscrit ne contient rien sur le logarithme discret, les courbes elliptiques ou les fonctions de hachage. Notre explication sur le fonctionnement des clés privées et publiques détaille le lien entre les deux.
Le minage est encore un cas à part. Les mineurs n’ont pas à inverser SHA-256 pour une sortie donnée : ils le calculent sans cesse, à la recherche d’un en-tête de bloc dont le hachage tombe sous une cible que le réseau ajuste tous les 2 016 blocs. La même confusion entre hachages et signatures était au cœur d’une alerte précédente, que nous avons couverte lorsque le scénario d’IA « bitcoin à zéro » de Chamath Palihapitiya mélangeait les deux le 24 octobre.
Le seul passage sur l’inversion, et la limite qu’il s’impose
Le manuscrit aborde la cryptographie à un seul endroit, l’annexe C.2, aux pages 52 et 53. Le corollaire C.2 traite des fonctions booléennes dont chaque bit de sortie ne dépend que d’un nombre constant de bits d’entrée, une propriété appelée localité de sortie constante. Pour de telles fonctions, dit l’article, on peut compter les entrées qui donnent une sortie fixée, et en trouver une, dans le même temps sous-exponentiel.
Il cite ensuite une famille couverte : les versions à localité constante de fonctions à sens unique candidates proposées par Oded Goldreich en 2000, une construction de recherche étudiée par les théoriciens. Pour celles-ci, selon l’article, son résultat exclut une difficulté d’inversion de la forme 2 puissance une constante fois n. La phrase suivante trace la limite : « Cela n’exclut pas le caractère à sens unique face aux algorithmes polynomiaux. »
SHA-256 n’appartient pas à cette famille. Après ses tours de mélange, chaque bit de sortie de SHA-256 dépend de nombreux bits d’entrée, pas d’une poignée fixe. Même là où l’article parle d’inverser des fonctions, il s’agit donc d’une classe théorique construite exprès pour être locale, et les auteurs énoncent la limite dans la foulée.
Ce qu’il faudrait démontrer pour menacer bitcoin
Une affirmation crédible contre la cryptographie de bitcoin demanderait davantage qu’une nouvelle borne asymptotique. Il faudrait un codage explicite d’une recherche de préimage SHA-256 ou d’un logarithme discret sur secp256k1, les constantes de l’algorithme, un code fonctionnel, et une estimation de coût qui batte 2256 opérations génériques pour les préimages ou 2128 pour les logarithmes discrets. Rien de tout cela n’a été publié par OpenAI, par Anthropic ou par ceux qui relisent leurs articles.
La vraie question de long terme pour les signatures de bitcoin reste l’informatique quantique : l’algorithme de Shor résoudrait, sur une machine assez grande, le problème du logarithme discret sur courbe elliptique. C’est un sujet différent, avec sa propre trajectoire de recherche, que nous avons suivi lorsque Google a divisé par 40 les erreurs des états magiques quantiques plus tôt ce mois-ci.
Nous n’avons trouvé ni mouvement de marché ni déclaration réglementaire liés à cette affirmation. Aucune déclaration des développeurs de Bitcoin Core n’avait été trouvée au 28 octobre, et la lettre des relecteurs ne mentionne pas la cryptographie.
Ce qui reste ouvert, et les prochaines dates
Savoir si l’argument est correct est la première question, et elle n’a pas de réponse : aucun relecteur indépendant n’avait publié de verdict au matin du 28 octobre. La deuxième est de savoir si l’énoncé Lean correspond à ce que revendique l’article. La troisième tient au lien entre les résultats d’OpenAI et d’Anthropic, puisque les deux sont arrivés à quelques jours d’intervalle et décrivent le même type de borne ; nous n’avons trouvé aucune explication de ce recoupement de la part de l’une ou l’autre entreprise.
La réunion virtuelle proposée par les relecteurs, prévue avant la fin de 2026, est la prochaine échéance à surveiller. D’ici là, les signaux utiles seraient une relecture publiée depuis le dépôt communautaire, une prise de position sur la formalisation Lean venant de quelqu’un d’extérieur à OpenAI, ou un codage assorti d’un test de performance qui chiffrerait un usage cryptographique de la réfutation revendiquée de l’hypothèse du temps exponentiel. Aucun des trois n’était paru au matin du 28 octobre.