OpenAI revendique une percée en cryptographie, sans menace immédiate pour le bitcoin

OpenAI affirme que son système d’IA a réfuté l’hypothèse du temps exponentiel (ETH), une hypothèse ancienne sur la difficulté de calcul de certains problèmes logiques. L’annonce du 26 octobre a conduit des chercheurs à organiser un examen indépendant. Le résultat divulgué ne démontre pas d’attaque pratique contre le bitcoin. Dans ce contexte, le sigle ETH désigne l’hypothèse du temps exponentiel, et non l’ether. L’hypothèse porte sur 3SAT, qui demande aux ordinateurs d’attribuer des valeurs vrai ou faux satisfaisant un ensemble de conditions logiques. Elle postule que les solutions dans le pire des cas exigent un temps qui croît exponentiellement avec le nombre de variables. Le manuscrit, daté du 17 octobre et révisé le 25 octobre, revendique un algorithme déterministe pour compter exactement les affectations satisfaisantes de formules booléennes à largeur fixe. Il fait état d’un temps d’exécution sous-exponentiel et d’un espace polynomial. Un temps sous-exponentiel croît plus lentement qu’une borne exponentielle à mesure que la taille du problème augmente, sans pour autant signifier que les ordinateurs actuels peuvent résoudre facilement le problème. La borne divulguée n’établit pas un algorithme en temps polynomial et ne résout pas P=NP. La question P=NP demande si tout problème de décision dont les solutions sont vérifiables en temps polynomial admet aussi des solutions calculables en temps polynomial. OpenAI indique que l’assistant de preuve Lean a vérifié le résultat. La note de périmètre Lean décrit toutefois une borne de temps sous-exponentielle plus faible que la revendication la plus forte du manuscrit. Les chercheurs qui organisent l’examen indépendant ont explicitement refusé de certifier le résultat. Leur lettre précise : « Notre participation ne doit pas être considérée comme une certification de la revendication. » CryptoSlate n’a examiné que les pages introductives 1 à 8, et non la preuve complète. Le minage de bitcoin et l’autorisation de dépenser relèvent de tâches de sécurité distinctes. Les mineurs cherchent un hachage d’en-tête de bloc inférieur à une cible. Les signatures prouvent le droit de dépenser. Bitcoin utilise les signatures ECDSA et Schnorr sur la courbe elliptique secp256k1, comme le décrit le BIP340. Les hypothèses de sécurité du BIP340 reposent sur les logarithmes discrets sur courbe elliptique et sur les fonctions de hachage. La récupération de clé consiste à déterminer si un attaquant peut obtenir une clé privée à partir de la clé publique correspondante. Réfuter une hypothèse SAT dans le pire des cas ne démontre pas en soi comment contourner ces mécanismes de sécurité précis. Une attaque pratique exigerait un encodage approprié, une implémentation opérationnelle et une comparaison des coûts pour la tâche visée. Le nombre de variables d’une formule SAT ne peut pas être substitué à la longueur en bits d’une clé cryptographique ou d’un hachage. Le périmètre Lean exprime la borne en fonction des variables de la formule encodée et de la longueur d’entrée. Insérer un nombre de bits cryptographiques dans la borne contournerait la représentation nécessaire du problème réel. Bitcoin ajuste la cible de minage tous les 2 016 blocs. Cet ajustement régit la production de blocs, non l’autorisation par signature. Il n’éliminerait pas l’importance d’un avantage privé en matière de minage. Le 7 octobre, Justin Drake a appelé à se préparer au « bunker mode » après une précédente annonce mathématique d’OpenAI. Son avertissement portait sur une attaque future potentielle, alors que l’annonce antérieure n’avait démontré aucune attaque pratique contre ECDSA ou RSA. La revendication du 26 octobre d’OpenAI concerne un résultat distinct. Ryan Williams a indiqué que lui-même, Russell Impagliazzo et Mohan Paturi avaient été chargés d’organiser un examen ouvert et indépendant, sans accords de confidentialité ni paiement. Williams a précisé séparément avoir demandé à OpenAI de vérifier si des cryptosystèmes existants étaient compromis, et avoir relayé qu’ils semblaient rester sûrs. Son compte rendu est une information de seconde main sur une vérification demandée à OpenAI, non un audit cryptographique indépendant. OpenAI affirme que des recherches supplémentaires substantielles sont nécessaires pour obtenir des améliorations pratiques. Williams a déclaré ne pas savoir si les développeurs en bénéficieraient, laissant ouvertes aussi bien une avancée sous 12 mois qu’une absence de développement. Les organisateurs prévoient de publier leurs conclusions pendant l’examen.