Quantum Time-Lock Puzzles in the Quantum Random Oracle Model

Dans le monde de la cryptographie, il existe un désir de longue date : envoyer un message qui ne peut être lu qu'après qu'un certain laps de temps se soit écoulé. Imaginez une lettre numérique scellée à l'intérieur d'une boîte qui nécessite une clé, mais la clé ne peut être forgée qu'en accomplissant une tâche qui demande exactement un an de travail continu et étape par étape. Ce concept, connu sous le nom de puzzle à verrouillage temporel (time-lock puzzle), est le fondement de technologies telles que le chiffrement à libération différée, où un secret est révélé uniquement après une date précise, ou les enchères à offres scellées où les offres restent cachées jusqu'à une échéance. Le défi a toujours été de s'assurer que la personne créant le puzzle puisse le faire rapidement, tandis que la personne tentant de le résoudre est contrainte d'attendre, même si elle dispose de milliers d'ordinateurs puissants travaillant de front. Pendant des décennies, les chercheurs ont cru que, dans un environnement informatique standard, un tel puzzle était impossible à construire de manière sécurisée. La logique était simple : si le puzzle n'est qu'une pièce de donnée, un attaquant avisé pourrait simplement copier cette donnée et répartir le travail entre de nombreux processeurs, résolvant ainsi le problème presque instantanément plutôt que d'attendre le temps requis.

Cette impossibilité était vraie pour les ordinateurs classiques, mais une équipe de chercheurs vient de démontrer que les règles changent lorsque le puzzle lui-même est un objet quantique. Dans une nouvelle étude, Prabhanjan Ananth et Yao-Ting Lin démontrent qu'en encodant le puzzle dans un état quantique délicat, ils peuvent créer un verrouillage temporel qui est sécurisé même contre les ordinateurs quantiques les plus puissants, à condition que ces ordinateurs ne puissent pas fonctionner pendant la durée totale requise. Leur travail résout une question restée ouverte pendant plus de quinze ans : si les lois de la mécanique quantique peuvent être utilisées pour imposer un délai qui ne peut être contourné par le traitement parallèle. Ils ont construit un système où le puzzle est généré en un éclair, mais sa résolution nécessite un temps séquentiel spécifique qui ne peut être raccourci, créant ainsi une capsule temporelle numérique qui repose sur la nature fondamentale de l'information quantique pour garder ses secrets en sécurité.

Le cœur du problème réside dans la différence entre la création d'un puzzle et sa résolution. Dans un contexte classique, si un puzzle n'est qu'une chaîne de bits, un attaquant peut copier cette chaîne et la distribuer à mille ordinateurs différents. Chaque ordinateur tente une partie différente de la solution simultanément, et le puzzle est résolu en une fraction du temps qu'il aurait fallu à un seul ordinateur. Cette capacité de copier et de paralléliser est ce qui a rendu les puzzles à verrouillage temporel classiques impossibles à sécuriser dans les modèles standards utilisés par les cryptographes. Les chercheurs ont réalisé que la solution résidait dans la propriété unique des états quantiques : ils ne peuvent pas être copiés parfaitement. Si le puzzle est un état quantique spécifique, un attaquant est limité à une seule copie du puzzle. Cette contrainte de copie unique est cruciale car elle empêche l'attaquant de distribuer des doublons à un réseau d'ordinateurs. Au lieu de cela, il doit travailler de manière séquentielle sur la solution, une étape après l'autre, exactement comme l'a prévu le créateur du puzzle. Même s'il dispose de nombreux processeurs parallèles, il ne peut pas contourner ce processus.

Pour construire cela, les chercheurs ont conçu un système où le puzzle consiste en une collection de minuscules particules quantiques, chacune préparée dans une configuration spécifique et délicate. Le créateur du puzzle génère ces particules et y attache quelques indices classiques, puis envoie l'ensemble du paquet au destinataire. Le destinataire doit ensuite effectuer une série d'opérations pour trouver un code caché. Le processus est conçu de telle sorte que le créateur puisse générer le puzzle presque instantanément, mais que le destinataire doive passer beaucoup de temps à effectuer une séquence de vérifications qui ne peuvent être sautées ou accélérées par l'utilisation de plus d'ordinateurs. Les chercheurs ont prouvé que même si un attaquant possède une puissance de calcul illimitée et peut utiliser un nombre polynomial de processeurs parallèles, il ne peut pas résoudre le puzzle plus rapidement que le délai prévu, à moins d'être prêt à attendre la durée complète des étapes séquentielles requises.

La sécurité de ce système repose sur une utilisation habile de fonctions aléatoires et de la manière dont les états quantiques interagissent avec elles. Le puzzle comprend un ensemble de jetons quantiques, chacun lié à un nombre caché. Pour trouver la solution, le résolveur doit tester différentes possibilités contre une fonction aléatoire, un processus qui agit comme une serrure qui ne s'ouvre que lorsque la bonne clé est essayée. Dans un monde classique, un attaquant pourrait essayer toutes les clés à la fois. Dans cette version quantique, parce que le puzzle est un état à copie unique, l'attaquant ne peut pas simplement dupliquer le puzzle pour essayer des clés en parallèle sur différentes copies. Bien que l'attaquant soit autorisé à effectuer plusieurs requêtes parallèles au sein d'un seul cycle de calcul, la nature à copie unique du puzzle le force à progresser à travers une séquence de cycles qui ne peut être contournée. Les chercheurs ont montré que même avec les algorithmes quantiques les plus avancés, l'attaquant ne peut pas obtenir d'avantage significatif en essayant de deviner la réponse ou en utilisant le traitement parallèle au-delà de la largeur polynomiale autorisée. La seule façon de réussir est de suivre le chemin long et lent que le puzzle impose.

Les chercheurs ont également traité la question de la vérification de la découverte de la bonne réponse sans révéler la réponse prématurément. Ils ont inclus un tag de vérification, une petite pièce d'information classique qui permet au résolveur de vérifier s'il a trouvé le bon nombre caché. Ce tag est généré de manière à être étroitement lié à l'état quantique, mais ne révèle pas la solution. Si le résolveur tente de deviner la réponse sans effectuer tout le travail, le tag de vérification échouera presque certainement, le forçant à recommencer. Ce mécanisme garantit que le résolveur ne peut pas tenter de contourner le travail requis en devinant et en vérifiant, mais doit plutôt effectuer la séquence complète d'opérations requise pour déverrouiller le message.

L'un des aspects les plus importants de ce travail est qu'il s'inscrit dans un cadre théorique connu sous le nom de modèle de l'oracle aléatoire quantique (quantum random oracle model). Ce modèle suppose que toutes les parties ont accès à une fonction aléatoire parfaite qui peut être interrogée de manière quantique. Bien qu'il s'agisse d'une construction théorique, elle fournit une base solide pour prouver que le système est sécurisé contre toute attaque respectant les lois de la mécanique quantique. Les chercheurs ont démontré que leur construction est efficace, ce qui signifie que le puzzle peut être généré rapidement, et qu'il reste sécurisé même si l'attaquant a accès à un grand nombre de processeurs parallèles. Ils ont prouvé que pour tout délai souhaité, comme un an, le puzzle peut être généré en un temps qui croît très lentement par rapport au délai, tandis que sa résolution nécessite un temps qui croît linéairement avec le délai.

Les implications de cette découverte sont profondes pour l'avenir des communications sécurisées. Cela ouvre la porte à de nouveaux types de protocoles cryptographiques qui reposent sur le temps plutôt que sur la seule difficulté mathématique. Par exemple, cela pourrait permettre la signature de contrats équitables où les deux parties ont la garantie que l'autre ne pourra pas se rétracter une fois le délai passé, ou des systèmes de vote sécurisés où les votes ne sont comptabilisés qu'après une échéance spécifique. Les chercheurs ont également noté que leur approche évite le besoin d'hypothèses mathématiques complexes qui pourraient être brisées par les progrès futurs de l'informatique. Au lieu de cela, la sécurité repose sur les propriétés fondamentales de la mécanique quantique, que l'on considère comme inviolables.

Dans leur construction, les chercheurs ont utilisé un type spécifique d'état quantique appelé état BB84, qui est une méthode bien connue pour encoder l'information dans les systèmes quantiques. Ils ont combiné ces états avec une série de fonctions aléatoires pour créer un puzzle qui est à la fois simple à générer et difficile à résoudre. Le puzzle consiste en un grand nombre de ces états quantiques, chacun portant une partie de l'information cachée. Le résolveur doit traiter ces états dans un ordre spécifique, et toute tentative de sauter une étape ou de les traiter dans le désordre entraînera un échec de la récupération du message. Les chercheurs ont montré que la probabilité qu'un attaquant devine la solution correcte sans faire le travail est si faible qu'elle est pratiquement nulle pour toute application pratique.

L'article clarifie également ce qui n'est pas possible. Il confirme que si le puzzle était un objet classique, ou si le résolveur était un ordinateur classique, la sécurité s'effondrerait. Les résultats d'impossibilité pour les puzzles classiques restent valables, et le travail des chercheurs ne change pas cela. La percée est spécifiquement dans le domaine quantique, où le puzzle lui-même est un état quantique et le résolveur est un ordinateur quantique. Cette distinction est cruciale, car elle souligne les capacités uniques de l'information quantique à imposer des contraintes impossibles dans le monde classique.

La preuve des chercheurs est rigoureuse et repose sur une série d'étapes logiques qui se construisent les unes sur les autres. Ils ont d'abord montré qu'un puzzle quantique unique est sécurisé contre un attaquant capable d'effectuer un nombre limité de requêtes. Ensuite, ils ont étendu ce résultat pour montrer que la sécurité est maintenue même lorsque l'attaquant est autorisé à utiliser de nombreux processeurs parallèles, à condition qu'il soit restreint à une copie unique du puzzle. Enfin, ils ont démontré que le système est sécurisé contre un attaquant qui peut utiliser n'importe quelle stratégie quantique possible, y compris celles impliquant l'intrication du puzzle avec d'autres systèmes quantiques. Le résultat est une preuve complète que le puzzle à verrouillage temporel est sécurisé selon les conditions qu'ils ont définies.

Ce travail représente une étape importante dans le domaine de la cryptographie quantique. Il montre que les limites de l'informatique classique peuvent être surmontées en embrassant les propriétés uniques de la mécanique quantique. La capacité de créer un puzzle à verrouillage temporel sécurisé contre les attaquants quantiques ouvre de nouvelles possibilités pour les communications sécurisées. Bien que la technologie soit encore théorique, la preuve qu'un tel système est possible fournit une base solide pour les développements futurs. Les chercheurs ont montré qu'avec la bonne approche, il est possible de créer une capsule temporelle numérique qui est véritablement verrouillée par le temps, offrant un nouveau niveau de sécurité pour l'ère numérique.