Certified Randomness with Optimal Rate

Dans le monde numérique, la confiance est une denrée fragile. Lorsque nous votons en ligne, générons des codes secrets pour les opérations bancaires ou élisons des dirigeants pour des réseaux décentralisés, nous comptons sur un hasard qui est véritablement imprévisible. Si ce hasard est prévisible ou biaisé, l'ensemble du système s'effondre. Depuis des décennies, les scientifiques cherchent un moyen de générer un tel hasard sans avoir besoin de faire confiance à la machine qui le produit. Le scénario idéal implique un dispositif qui produit une chaîne de bits — des zéros et des uns — si chaotique et uniforme que personne, pas même le propriétaire du dispositif, n'aurait pu deviner le résultat à l'avance. C'est le saint graal du « hasard certifié » : une garantie mathématique que le résultat est véritablement aléatoire, vérifiable par n'importe qui, sans nécessiter de graine (seed) secrète préexistante.

Le défi a toujours été que les méthodes existantes produisaient soit un hasard faible qui pouvait être facilement manipulé, soit nécessitaient qu'un humain de confiance fournisse un petit nombre de départ aléatoire. Une nouvelle étude de Siddhartha Jain, Saachi Mutreja et Bhaskar Roberts répond à cette limitation fondamentale. Ils ont développé un protocole qui permet à un ordinateur quantique de prouver qu'il a généré une chaîne de bits dotée d'un hasard quasi parfait, même si l'ordinateur est malveillant et que la personne vérifiant le résultat est complètement déterministe, ne possédant aucun nombre aléatoire propre. Cette percée élimine le besoin de tout point de départ de confiance, atteignant un taux de hasard aussi élevé que théoriquement possible.

Les chercheurs ont travaillé dans un cadre connu sous le nom de modèle de l'oracle aléatoire quantique, un cadre théorique où toutes les parties ont accès à une fonction aléatoire publique et parfaite qui agit comme un hachage universel. Dans cet environnement, ils ont construit un système où un prouveur quantique peut générer une longue chaîne de bits et fournir une preuve courte que la chaîne est véritablement aléatoire. L'innovation clé est que le vérificateur, qui vérifie la preuve, n'a pas besoin d'être aléatoire lui-même ; il peut être un algorithme fixe et déterministe. Les tentatives précédentes pour y parvenir échouaient soit à garantir un hasard de haute qualité, soit reposaient sur le fait que le vérificateur possède une petite graine aléatoire de confiance pour amorcer le processus. Le nouveau protocole élimine entièrement cette graine, prouvant qu'un vérificateur déterministe peut tout de même être convaincu du hasard d'une longue chaîne générée par un dispositif quantique non fiable.

Pour comprendre l'importance de cette avancée, il faut observer ce qui se passe lorsqu'un système n'est pas parfaitement aléatoire. Si une chaîne de bits n'est que « faiblement » aléatoire, elle peut paraître chaotique, mais elle peut tout de même présenter un biais vers certains motifs, la rendant vulnérable à la prédiction. Les chercheurs ont prouvé que leur méthode garantit un niveau d'entropie, ou de désordre, qui est presque maximal. En termes pratiques, cela signifie que pour une chaîne d'une longueur spécifique, le nombre de bits qui sont véritablement imprévisibles est presque égal à la longueur totale de la chaîne. La seule perte infime de hasard est une quantité logarithmique, ce qui est inévitable en raison de la nature des lois de la physique et de l'informatique. Il s'agit d'une amélioration considérable par rapport aux méthodes précédentes, qui produisaient souvent des chaînes où la quantité de hasard garanti n'était qu'une infime fraction de la longueur totale.

Le protocole fonctionne en deux étapes principales. Premièrement, le dispositif quantique génère une source « faiblement » aléatoire en utilisant une construction mathématique spécifique qui a été prouvée sûre contre les attaques quantiques. Cette source n'est pas encore assez bonne pour les applications à enjeux élevés. Dans la seconde étape, le dispositif fait passer cette source à travers une fonction de compression, qui agit comme un filtre. Ce filtre condense la source faible en une chaîne de bits plus courte et beaucoup plus forte. Les chercheurs ont démontré que même si un adversaire tente de manipuler le processus en choisissant des entrées spécifiques ou en observant le comportement de la fonction, il ne peut pas forcer le résultat final à être prévisible. La chaîne finale conserve un niveau élevé d'entropie minimale (min-entropy), une mesure de la difficulté de deviner le résultat le plus probable, même lorsque l'adversaire a vu tout l'historique de l'interaction.

Un composant critique de ce travail est le concept d'entropie minimale « conditionnelle ». Dans de nombreuses applications réelles, telles qu'un phare de hasard public (randomness beacon) qui diffuse un nouveau nombre aléatoire chaque heure, la sécurité du nombre actuel dépend du fait qu'il ne peut pas être prédit même si un attaquant connaît tout ce qui précède. Les chercheurs ont montré que leur protocole garantit que chaque nouvelle impulsion de hasard est imprévisible, même lorsqu'elle est conditionnée par tous les messages et données qui l'ont précédée. Ceci est essentiel pour des applications comme l'élection de leaders dans les réseaux blockchain ou la génération de chaînes aléatoires communes pour les protocoles cryptographiques, où l'intégrité du tour actuel dépend de l'imprévisibilité du passé.

L'équipe a également abordé les limites de ses propres travaux avec une honnêteté rigoureuse. Ils ont prouvé qu'il est impossible d'atteindre un hasard uniforme parfait avec un vérificateur déterministe si l'adversaire est autorisé à s'exécuter pendant un temps polynomial. Un attaquant pourrait théoriquement utiliser une technique appelée échantillonnage par rejet (rejection sampling) pour fixer un petit nombre de bits dans la sortie, « jouant » ainsi avec le système pour produire un résultat légèrement biaisé. Cependant, les chercheurs ont montré que leur protocole atteint le meilleur résultat possible sous ces contraintes : il garantit que le nombre de bits qui peuvent être fixés par un attaquant est si faible que le hasard restant est toujours suffisant pour toutes les applications cryptographiques pratiques. La perte est négligeable, et la sécurité tient face à tout adversaire doté d'une puissance de calcul réaliste.

Ce travail a des implications immédiates pour l'avenir des communications sécurisées et des systèmes décentralisés. En supprimant le besoin d'une graine de confiance, le protocole permet la création de phares de hasard qui peuvent être exécutés sur un seul dispositif quantique non fiable. Un tel phare pourrait publier périodiquement des nombres aléatoires frais et imprévisibles que n'importe qui peut vérifier. La sécurité de ces nombres ne dépendrait pas de l'honnêteté de l'opérateur du dispositif, mais des lois de la mécanique quantique et de la structure mathématique du protocole lui-même. Bien que l'implémentation actuelle repose sur des modèles théoriques, le chemin vers une application pratique est plus clair que jamais, offrant un moyen de générer le hasard de confiance dont la société numérique moderne a désespérément besoin sans que nous ayons à faire confiance à la machine.

Cette étude constitue une réponse définitive à une question posée par des chercheurs précédents concernant les limites du hasard certifié. Elle confirme que, bien que l'uniformité parfaite soit mathématiquement hors de portée pour un vérificateur déterministe, un niveau de hasard effectivement indiscernable du parfait est réalisable. Les chercheurs n'ont pas seulement amélioré le taux de hasard ; ils ont redéfini les frontières de ce qui est possible dans un environnement sans confiance (trustless). Leur construction fournit une garantie de sécurité robuste et inconditionnelle dans le modèle de l'oracle aléatoire quantique, établissant un nouveau standard pour notre conception du hasard à l'ère quantique. Le résultat est un protocole qui est à la fois théoriquement solide et pratiquement pertinent, comblant le fossé entre la théorie quantique abstraite et les besoins concrets d'une infrastructure numérique sécurisée.