💻 computer science

Lower Bounds on Black-Box Constructions of Pseudorandom Functions

Cet article établit qu'aucune construction entièrement boîte noire d'une fonction pseudoaléatoire (PRF) à partir d'un générateur pseudoaléatoire (PRG) ne peut atteindre $o(n/\log n)$ appels non adaptatifs au PRG, même pour des PRF faibles avec des sorties d'un bit, fournissant ainsi des bornes inférieures fortes sur l'efficacité de telles constructions et laissant la possibilité d'une construction à invocation unique comme un défi majeur ouvert.

Auteurs originaux : Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

Publié 2026-08-17

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Le dilemme du serrurier numérique

Imaginez que vous êtes un maître serrurier essayant de construire une porte de coffre-fort incassable. Dans le monde de la sécurité numérique, ce « coffre-fort » est une Fonction Pseudo-aléatoire (PRF). Voyez la PRF comme une machine magique : vous lui donnez une clé secrète et une entrée spécifique (comme un numéro de chambre), et elle recrache une chaîne de nombres qui semble complètement aléatoire pour quiconque observe. Cependant, si vous utilisez la même clé secrète à nouveau, elle produit toujours exactement la même chaîne « aléatoire ». Cette cohérence est ce qui la rend utile pour verrouiller vos e-mails, sécuriser vos transactions bancaires et protéger vos mots de passe.

Pour construire cette machine magique, les cryptographes commencent souvent par quelque chose de plus simple appelé un Générateur Pseudo-aléatoire (PRG). Un PRG est comme une petite graine efficace qui se transforme en une forêt massive et d'apparence aléatoire. Il prend une courte chaîne secrète et l'étire en une chaîne beaucoup plus longue qui semble aléatoire pour tout programme informatique. La grande question en cryptographie a été : Combien de fois devons-nous utiliser cette machine d'« étirement de graine » pour construire notre « porte de coffre-fort » ?

Pendant des décennies, la recette standard (connue sous le nom de construction GGM) a consisté à utiliser la machine d'étirement de graine encore et encore, dans une structure arborescente, environ $\omega(\log n)$ fois (où $n$ est la taille de la graine). Cela fonctionne très bien, mais cela semble un peu lourd. Existe-t-il un raccourci ? Pourrions-nous construire une porte de coffre-fort parfaite en utilisant la machine d'étirement de graine une seule fois ? Ou peut-être seulement quelques fois ? Ce document plonge profondément dans cette question, agissant comme un détective essayant de prouver que, peu importe votre ingéniosité, vous ne pouvez tout simplement pas construire une porte de coffre-fort sécurisée avec trop peu d'étirements de la graine.

La grande découverte du papier : Le problème du « Trop peu »

Ce document, écrit par Bar Alon, Itai Dinur et Muthuramakrishnan Venkitasubramaniam, s'attaque à la question fondamentale : Quel est le nombre absolu minimum de fois que nous devons appeler un Générateur Pseudo-aléatoire (PRG) pour construire une Fonction Pseudo-aléatoire (PRF) ?

Les auteurs prouvent que pour un type de construction spécifique et très raisonnable, la réponse est « bien plus que ce que vous espérez ». Plus précisément, ils montrent que vous ne pouvez pas construire une PRF sécurisée en utilisant une méthode « boîte noire totale » si vous n'appelez le PRG qu'un nombre infime de fois — spécifiquement, moins de $n / \log n$ fois environ (où $n$ est la longueur de l'entrée du PRG).

Pour comprendre leur preuve, imaginez un jeu de « Détecter le faux ».

La Configuration : Une « Réduction » (le constructeur) tente de créer une PRF en utilisant un PRG. Ils disposent également d'un « Adversaire » (un hacker) qui tente de déterminer si la PRF est réelle ou s'il s'agit d'une fonction aléatoire.
L'Astuce : Les auteurs imaginent un scénario où le constructeur est « limité en requêtes » (query-bounded). Cela signifie que le constructeur peut demander de l'aide à l'adversaire, mais le nombre de fois qu'il peut demander ne dépend pas de manière explosive du nombre de questions posées par l'adversaire.
La Contre-Attaque : Les auteurs construisent un « Adversaire Réel » et un « Adversaire Idéal ».
- L'Adversaire Idéal est un ordinateur surpuissant et lent qui peut vérifier chaque clé secrète possible pour voir si elle correspond aux données. Il peut facilement distinguer si une fonction est une PRF ou une fonction aléatoire.
- L'Adversaire Réel est celui que le constructeur utilise réellement. Il n'a pas de super-pouvoirs ; il voit seulement les questions limitées que le constructeur a posées au PRG.
La Révélation : Les auteurs prouvent que si le constructeur utilise trop peu d'appels au PRG, l'« Adversaire Réel » peut parfaitement imiter l'« Adversaire Idéal » sans pour autant briser la sécurité du PRG. Cela crée un paradoxe : si le constructeur pouvait construire une PRF sécurisée avec si peu d'appels, il pourrait également briser le PRG lui-même en utilisant une méthode trop lente pour être pratique, ce qui contredit l'hypothèse selon laquelle le PRG est sécurisé.

Le Résultat Principal :
Le papier prouve que pour les constructions non-adaptatives (où le constructeur décide de toutes les questions au PRG avant de voir la moindre réponse), il est impossible de construire une PRF avec moins de $o(n / \log n)$ appels au PRG. Cela reste vrai même si la PRF ne produit qu'un seul bit (un 0 ou un 1) et même si le hacker est restreint à poser des questions simples et aléatoires.

Le Résultat de la « Longue Sortie » :
Les auteurs ont également examiné les PRF qui produisent de longues chaînes de données (et pas seulement un seul bit). Ils ont prouvé que même si le constructeur est autorisé à être « adaptatif » (posant les questions une par une et utilisant les réponses pour décider de la question suivante), il existe toujours une limite dure. Si le PRG étire l'entrée d'un petit montant, vous avez besoin d'au moins environ $out / \log n$ appels. Si le PRG l'étire d'un grand montant, vous avez besoin d'au moins $out / r$ appels.

Ce que cela signifie pour le rêve de l'appel unique

Pendant longtemps, les cryptographes se sont demandé si une construction à « appel unique » était possible — construire une PRF parfaite en étirant la graine une seule fois.

Pour les méthodes non-adaptatives : Ce papier l'exclut de fait. Vous ne pouvez pas construire une PRF sécurisée avec un nombre constant d'appels (comme 1, 2 ou 10) si la taille de l'entrée augmente. Les mathématiques ne le permettent tout simplement pas.
Pour les méthodes adaptatives : Le papier n'exclut pas une construction à appel unique pour tous les scénarios adaptatifs. Au lieu de cela, il montre que pour les PRF avec des sorties longues, le nombre d'appels doit être proportionnel à la taille de la sortie. Vous ne pouvez pas vous contenter d'un nombre infime et fixe d'appels pour une porte de coffre-fort massive si la sortie est grande. La question de savoir si une construction à appel unique adaptatif existe pour les PRF avec des sorties courtes reste ouverte.

La mise en garde du « Limité en requêtes »

Les auteurs sont très prudents quant à leurs hypothèses. Ils se concentrent sur une classe de réductions qu'ils appellent « limitées en requêtes » (query-bounded). En langage clair, cela signifie que l'interaction du constructeur avec l'adversaire est limitée de telle sorte qu'elle ne dépend pas du nombre de questions posées par l'adversaire. Les auteurs soutiennent que presque toutes les constructions de l'histoire de la cryptographie entrent dans cette description. Ils reconnaissent que si quelqu'un inventait une méthode étrange et non standard de construction de PRF où le constructeur poserait des millions de questions à l'adversaire simplement parce que l'adversaire a posé une seule question, leur preuve pourrait ne pas s'appliquer. Mais pour toutes les conceptions cryptographiques pratiques et standards, les limites inférieures qu'ils ont trouvées restent fermes.

À retenir

Ce document ne se contente pas de suggérer une limite ; il fournit une preuve mathématique que le « raccourci » pour construire des PRF est une impasse. Si vous voulez une PRF boîte noire sécurisée, vous ne pouvez pas sauter des étapes. Vous devez payer le coût de l'appel du PRG suffisamment de fois pour garantir que l'« entropie » (le caractère aléatoire et imprévisible) est assez élevée pour tromper n'importe quel hacker. La célèbre construction GGM, qui utilise environ $\omega(\log n)$ appels, s'avère être presque optimale. Le rêve de construire une forteresse avec une seule brique est mathématiquement impossible dans ce contexte.

Résumé Technique : Bornes Inférieures sur les Constructions en Boîte Noire de Fonctions Pseudorandom

Énoncé du Problème

Le papier traite d'une question ouverte fondamentale en cryptographie : quel est le nombre minimal d'invocations d'un générateur de nombres pseudoaléatoires (PRG) requis pour construire une fonction pseudorandom (PRF) via une construction entièrement en boîte noire ?

Le travail séminal de Goldreich, Goldwasser et Micali (GGM) a établi qu'une PRF peut être construite à partir d'un PRG en utilisant une approche basée sur un arbre. Lorsqu'elle est combinée avec la technique d'extension de domaine de Levin, cette construction nécessite $\omega(\log n)$ appels au PRG, où $n$ est la longueur d'entrée du PRG. Bien que des travaux récents de Beimel, Malkin et Mazor aient prouvé l'optimalité de GGM pour une classe spécifique de « constructions en arbre », le cas général reste non résolu. Plus précisément, on ignore si une PRF peut être construite avec moins de $\omega(\log n)$ appels, ou même avec un seul appel, en utilisant des techniques générales en boîte noire.

Ce travail étudie cette question dans le cadre des constructions entièrement en boîte noire, où la construction et la réduction de sécurité sont toutes deux en boîte noire. Les auteurs se concentrent spécifiquement sur une classe de réductions nommées réductions à requêtes bornées (query-bounded reductions), où le nombre d'interactions de la réduction avec l'adversaire est borné par un polynôme indépendant de la complexité de requêtes de l'adversaire (pourvu que celui-ci soit suffisamment efficace).

Méthodologie

Les auteurs emploient le paradigme de méta-réduction pour établir leurs bornes inférieures. Cette technique consiste à construire un adversaire « réel » inefficace capable de simuler un adversaire « idéal » (qui casse la PRF) sans accès direct au PRG sous-jacent, brisant ainsi la sécurité du PRG en utilisant moins de requêtes que ce qui est autorisé.

Composantes Techniques Clés :

Réductions à Requêtes Bornées : Les auteurs définissent une réduction comme étant à requêtes bornées si le nombre de fois qu'elle interroge l'adversaire de distinction est limité par un polynôme $d(n)$ , quel que soit le nombre de requêtes que l'adversaire effectue sur son oracle. Cette classe capture la plupart des réductions connues dans la littérature, y compris GGM et les constructions de Goldreich-Levin.
Adversaires Idéal vs Réel :
- Adversaire Idéal ( $A_{ideal}$ ) : Un adversaire inefficace qui possède un accès exponentiel à l'oracle du PRG. Il tente de casser la PRF en trouvant une clé cohérente avec une grande fraction de paires entrée-sortie.
- Adversaire Réel ( $A_{real}$ ) : Un adversaire inefficace qui n'a pas accès au PRG. Au lieu de cela, il reçoit les paires requête-réponse générées par l'interaction de la réduction avec le PRG. Il tente de simuler $A_{ideal}$ en estimant la probabilité qu'une clé soit cohérente avec les sorties observées.
Fonctions de Score et Indépendance :
- Le défi central est que les sorties de la PRF sur différentes entrées peuvent être dépendantes si elles partagent des graines (seeds) de PRG.
- Les auteurs introduisent une procédure pour identifier les « graines fréquentes » (graines utilisées par de nombreuses entrées) et remplacer leurs sorties par des valeurs fixes. Cela réduit le nombre d'appels actifs au PRG.
- Pour les entrées restantes, ils utilisent un argument combinatoire (Claim 3/6) pour montrer que soit un grand ensemble d'entrées utilise des graines de PRG mutuellement disjointes (permettant des arguments d'indépendance via l'inégalité de Hoeffding), soit le nombre de ces clés est négligeable.
- Pour gérer la distance statistique entre l'adversaire idéal et l'adversaire réel, les auteurs utilisent un seuil aléatoire (échantillonné uniformément de $[0.8, 1]$ ) plutôt qu'un seuil fixe. Cela lisse la frontière de décision, garantissant que la distribution de sortie de l'adversaire réel est statistiquement proche de celle de l'adversaire idéal, à condition que le nombre d'entrées $m$ soit suffisamment grand par rapport au nombre de requêtes de la réduction $d$ .
Arguments d'Entropie pour Sorties Longues : Pour le second résultat (Theorem 2), les auteurs utilisent un argument basé sur l'entropie. Ils construisent un PRG spécifique qui applique l'aléa uniquement à un petit préfixe de la graine. Cela limite l'entropie de la sortie de la PRF à être significativement inférieure à celle d'une fonction purement aléatoire, permettant à un discriminateur de casser la construction si le nombre d'appels est trop faible.

Contributions Clés et Résultats

1. Borne Inférieure pour les Appels Non-Adaptatifs (Theorem 1)

Le papier prouve qu'aucune construction entièrement en boîte noire d'une PRF à partir d'un PRG n'existe en utilisant des appels non-adaptatifs et des réductions à requêtes bornées si le nombre d'appels $c$ satisfait :
$c = o\left(\frac{n}{\log n}\right) \quad \text{et} \quad c = o\left(\frac{in}{\log in}\right)$
où $n$ est la longueur d'entrée du PRG et $in$ est la longueur d'entrée de la PRF.

Portée : Ce résultat est valable même pour les PRFs faibles (où l'adversaire est restreint à des requêtes i.i.d. uniformes) et pour les PRFs avec une sortie d'un bit.
Implication : Cela exclut la possibilité de construire une PRF avec un nombre constant d'appels non-adaptatifs (par exemple, un seul appel) pour des PRFs avec des longueurs d'entrée $in = \omega(\log n)$ , résolvant un cas spécifique du problème ouvert pour les réductions à requêtes bornées.

2. Borne Inférieure pour les Sorties Longues (Theorem 2)

Le papier établit une borne inférieure pour les PRFs avec des sorties longues ($out$) qui tient même pour les constructions adaptatives et ne nécessite pas que la réduction soit à requêtes bornées.

Résultat : Il n'existe aucune construction entièrement en boîte noire d'une PRF avec une longueur de sortie $out$ à partir d'un PRG avec un étirement (stretch) $r$ en utilisant moins de $\frac{out}{\max(r, \omega(\log n))}$ appels.
Comparaison avec GGM : La construction GGM (avec l'astuce de Levin) utilise $\omega(\log n)$ appels à un PRG d'étirement $n$ pour produire une sortie de $n$ bits. En composant cela avec un PRG d'étirement de 1 bit (nécessitant $O(n/\log n)$ appels), le nombre total d'appels à un PRG de 1 bit est $\omega(n)$ . Le Theorem 2 implique une borne inférieure de $\Omega(n / \omega(\log n))$ , montrant que GGM est optimal à un facteur $\omega(\log n)$ près.

Signification et Revendications

Le papier affirme faire progresser de manière significative la question de l'optimalité des constructions de PRF à partir de PRG.

Optimalité de GGM : Alors que les résultats précédents étaient limités aux « constructions en arbre », ce travail fournit des bornes inférieures pour les constructions en boîte noire générales sous des hypothèses spécifiques mais naturelles (réductions à requêtes bornées).
Résolution du Cas de l'Appel Unique : Les auteurs déclarent explicitement que leur résultat résout la question de savoir si une PRF peut être construite avec un seul appel au PRG pour la classe des réductions à requêtes bornées. Ils démontrent qu'une telle construction est impossible pour les PRFs avec des longueurs d'entrée $in = \omega(\log n)$ .
Robustesse : Les résultats d'impossibilité tiennent même pour les PRFs faibles et, dans le cas des sorties longues, pour les constructions adaptatives.
Limites : Les auteurs reconnaissent modestement que leur résultat principal (Theorem 1) repose sur l'hypothèse de « requêtes bornées ». Ils notent qu'il reste une question ouverte de savoir si ces bornes inférieures peuvent être étendues à toutes les réductions en boîte noire, car leur preuve repose sur le fait que le nombre d'interactions de la réduction est indépendant de la complexité de requêtes de l'adversaire.

En résumé, le papier démontre que la construction GGM est presque optimale en termes de nombre d'invocations de PRG requises, particulièrement pour les constructions non-adaptatives et celles avec des sorties longues, en s'appuyant sur des techniques de méta-réduction et une analyse minutieuse de l'entropie.