Amplifying Randomized Encodings & Applications

Dans le vaste paysage de la cryptographie moderne, il existe une tension fondamentale entre sécurité et efficacité. Nous voulons des systèmes qui soient incroyablement difficiles à briser, tout en étant assez simples pour fonctionner sur des appareils du quotidien. Pour y parvenir, les cryptographes s'appuient souvent sur des « fonctions à sens unique », des opérations mathématiques faciles à effectuer dans un sens, mais presque impossibles à inverser sans une clé secrète. L'existence de ces fonctions est le socle de la confidentialité numérique, pourtant, depuis des décendes, les mathématiciens peinent à prouver qu'elles existent en se basant sur les problèmes les plus difficiles de l'informatique. Au lieu de s'appuyer sur des hypothèses spécifiques et potentiellement fragiles, les chercheurs ont longtemps cherché à démontrer que les fonctions à sens unique doivent exister simplement parce que certaines classes larges de problèmes sont intrinsèquement difficiles à résoudre. Parmi ces classes de problèmes difficiles figurent les « preuves à divulgation nulle de connaissance » (zero-knowledge proofs), une méthode par laquelle une partie peut convaincre une autre qu'elle connaît un secret sans pour autant révéler de détails sur ce secret lui-même. La question demeure : si ces problèmes de divulgation nulle de connaissance sont difficiles à résoudre dans le pire des scénarios, cela garantit-il l'existence des fonctions à sens unique nécessaires à un chiffrement sécurisé ?

Une équipe de chercheurs a maintenant franchi une étape importante vers la réponse à cette question en développant une nouvelle façon d'amplifier la fiabilité des « encodages randomisés ». Imaginez un encodage randomisé comme un moyen de traduire un problème complexe en une version simplifiée et brouillée. Le but est de créer une traduction qui ne révèle rien du problème d'origine, hormis la réponse finale, tout en étant beaucoup plus facile à calculer que l'original. Les chercheurs se sont concentrés sur un type spécifique de ces traductions où la garantie de sécurité ne tient que pour les réponses « oui », un scénario connu sous le nom d'encodage à sens unique. Ils ont découvert que même si ces encodages sont initialement imparfaits — signifiant qu'ils peuvent laisser fuiter une petite quantité d'information ou donner occasionnellement une mauvaise réponse — ils peuvent être systématiquement améliorés. En appliquant une nouvelle technique basée sur le concept de « réductions avec perte » (lossless reductions), qui mesure la quantité d'information rejetée lors d'une transformation, l'équipe a prouvé que ces encodages défectueux peuvent être amplifiés jusqu'à ce que les erreurs et les fuites d'informations deviennent dérisoires, devenant ainsi négligeables.

Ce processus d'amplification est la clé pour débloquer des connexions plus profondes en informatique. Les chercheurs ont montré que si un problème peut être encodé avec un niveau même modeste de confidentialité et de correction, il peut être transformé en une version pratiquement parfaite. Ils ont appliqué ce résultat à la classe de problèmes connue sous le nom de NISZK, qui traite des preuves à divulgation nulle de connaissance non interactives. Pendant des années, il était question de savoir si la propriété de divulgation nulle de connaissance de ces preuves pouvait être renforcée, passant d'une garantie faible de type inverse-polynomiale à une garantie forte de type négligeable. L'équipe a prouvé qu'elle le peut, résolvant ainsi un problème qui était resté sans réponse depuis la fin des années 1990. Cela signifie que tout problème possédant une preuve à divulgation nulle de connaissance faible peut être converti en un problème doté d'une garantie de divulgation nulle de connaissance pratiquement parfaite, à condition que le problème sous-jacent soit suffisamment difficile.

Les implications de ce travail s'étendent directement à l'existence des fonctions à sens unique. Les chercheurs ont démontré que si les versions du pire cas de ces problèmes à divulgation nulle de connaissance sont effectivement difficiles à résoudre, alors les fonctions à sens unique doivent exister, à condition qu'une procédure spécifique de suppression d'erreurs pour les encodages à sens unique puisse être établie. Ils y sont parvenus en montrant que la capacité de supprimer les erreurs des encodages à sens unique est suffisante pour combler le fossé entre la difficulté de ces problèmes spécifiques et la création d'outils cryptographiques sécurisés. Bien que l'article établisse que cette suppression d'erreurs serait suffisante, il laisse explicitement la construction d'un tel algorithme de suppression d'erreurs comme une question ouverte pour des travaux futurs. De plus, ils ont exploré le domaine quantique, montrant que des principes similaires s'appliquent aux encodages quantiques, ce qui implique par extension l'existence de « générateurs d'états à sens unique », un équivalent quantique des fonctions à sens unique. Cela suggère que la difficulté fondamentale de ces problèmes est assez robuste pour soutenir la cryptographie classique et quantique.

L'étude a également abordé la nature de l'« obfuscation par indistinguabilité » (indistinguishability obfuscation), un outil cryptographique puissant qui cache les rouages internes d'un programme informatique tout en préservant sa fonction. Des recherches antérieures avaient montré que l'obfuscation n'implique des fonctions à sens unique que sous des conditions très strictes où le programme est soit parfaitement caché, soit présente un taux d'erreur très faible. Le nouveau travail prouve que même si l'obfuscation est faible et imparfaite — laissant fuiter une quantité significative d'informations et commettant des erreurs fréquentes — elle implique toujours l'existence de fonctions à sens unique, tant qu'une structure théorique majeure de l'informatique, connue sous le nom de Hiérarchie Polynomiale, ne s'effondre pas. Cette découverte élargit considérablement les conditions sous lesquelles nous pouvons être certains qu'une cryptographie sécurisée est possible, suggérant que la barrière pour la construire est plus basse et plus robuste qu'on ne le pensait auparavant.

En établissant ces connexions, les chercheurs ont fourni une carte plus claire des fondements théoriques de la cryptographie. Ils ont montré que la difficulté de résoudre certaines classes larges de problèmes n'est pas seulement une curiosité mathématique abstraite, mais une source directe de la sécurité nécessaire à notre monde numérique. Leur travail confirme que si nous pouvons considérer que ces problèmes complexes sont difficiles à résoudre dans le pire des cas, et si la question ouverte de la suppression d'erreurs pour les encodages à sens unique est résolue, nous pouvons compter sur l'existence des fonctions à sens unique qui protègent nos données. Les résultats ne font pas que suggérer une possibilité ; ils offrent une preuve rigoureuse que le chemin allant des problèmes difficiles au chiffrement sécurisé est ouvert, sous réserve du succès du perfectionnement des techniques d'encodage pour éliminer les erreurs. Cela rapproche la communauté théorique d'une compréhension définitive de la raison pour laquelle la cryptographie fonctionne et de ce qu'il faut réellement pour la construire.