💻 computer science

Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build PRFs in $\mathsf{NC}^1$ , Generically)

Cet article introduit une transformation générique qui convertit les PRF faibles en PRF fortes avec un surcoût de profondeur minimal, permettant la construction de PRF calculables en $\mathsf{NC}^1$ à partir d'hypothèses standards incluant LWE, LPN et CDH, résolvant ainsi des problèmes ouverts de longue date en cryptographie à faible profondeur.

Auteurs originaux : Youlong Ding, Aayush Jain, Ilan Komargodski

Publié 2026-08-27

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Youlong Ding, Aayush Jain, Ilan Komargodski

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

Dans le monde numérique, la sécurité repose souvent sur un type particulier d'outil mathématique appelé fonction pseudorandom (pseudo-aléatoire). Imaginez une machine qui prend un code secret et une donnée, puis recrache une suite de nombres qui semble complètement aléatoire pour quiconque regarde. Si la machine fonctionne correctement, personne ne peut faire la différence entre sa sortie et une séquence véritablement aléatoire, même après avoir vu la machine fonctionner de nombreuses fois. Ces outils sont les verrous et les clés invisibles qui protègent tout, des services bancaires en ligne aux messages privés. Pendant des décennies, des chercheurs ont cherché à construire ces machines pour qu'elles fonctionnent le plus rapidement possible, spécifiquement en les faisant fonctionner en très peu d'étapes. Dans le langage de l'informatique, cela signifie les construire avec un circuit très peu profond, permettant au calcul de se produire presque instantanément sur les processeurs modernes. Plus ces outils sont rapides et simples, plus ils peuvent être utilisés efficacement dans des systèmes complexes comme le vote sécurisé ou le partage de données privées.

Pendant longtemps, il y a eu un écart persistant dans notre capacité à construire ces machines rapides et peu profondes. Nous savions comment les créer en utilisant des hypothèses mathématiques très fortes et complexes, mais celles-ci nécessitaient des circuits profonds et lents. Inversement, nous pouvions construire des circuits peu profonds, mais seulement si nous nous appuyions sur des hypothèses plus faibles, moins prouvées, ou sur des structures mathématiques très spécifiques et rigides. C'était comme avoir une clé qui ouvre une porte mais qui est trop lourde à transporter, ou une clé qui est légère mais qui ne convient qu'à un seul verrou étrange. L'objectif était de trouver un moyen de fabriquer une clé légère capable d'ouvrir n'importe quelle porte, en utilisant uniquement les verrous les plus standards et les plus fiables disponibles. Ce défi est resté entier pendant près de trente ans, limitant la manière dont nous pouvions sécuriser le monde numérique.

Une équipe de chercheurs a désormais comblé cet écart avec une nouvelle méthode générale qui transforme un outil plus faible et plus facile à construire en un outil fort et sécurisé sans ralentir sa cadence. Leurs travaux, publiés dans un article intitulé « Pseudorandom Functions in NC1 from LWE/LPN/CDH », démontrent qu'il est possible de construire ces machines rapides et peu profondes en utilisant trois des hypothèses les plus fondamentales et les plus largement reconnues de la cryptographie. Les chercheurs ont réussi en affinant une vieille idée appelée construction GGM, qui construit une fonction complexe en parcourant un arbre de calculs plus petits. La méthode traditionnelle consistait à descendre un long couloir où chaque pas demandait la même quantité d'effort, rendant le voyage total long et lent. La nouvelle méthode change la forme du couloir. À mesure que le processus s'enfonce dans l'arbre, la quantité de travail requise à chaque étape diminue géométriquement. Les premières étapes sont lourdes, mais les étapes suivantes deviennent de plus en plus légères, si rapidement que l'effort total reste faible. Cette technique de « décroissance » (tapering) permet aux chercheurs de maintenir l'ensemble du processus dans les limites d'un circuit peu profond et rapide.

Pour prouver l'efficacité de cette nouvelle méthode, l'équipe l'a appliquée à trois problèmes mathématiques spécifiques connus pour être difficiles à résoudre. Le premier est le problème de l'apprentissage avec erreurs (Learning With Errors), qui consiste à trouver un motif caché dans un ensemble de données bruitées. Les tentatives précédentes pour construire des machines rapides à partir de ce problème nécessitaient une version plus complexe et spécifique des mathématiques utilisant de très grands nombres. Le nouveau travail montre que la version standard, avec des nombres beaucoup plus petits, est suffisante. Le deuxième problème est l'apprentissage de la parité avec du bruit (Learning Parity with Noise), qui traite de la recherche d'un motif caché dans un flux de bits dont les bits ont été inversés de manière aléatoire. Les chercheurs ont montré que leur méthode fonctionne avec la version standard de ce problème, supprimant le besoin des versions spécialisées et structurées qui étaient auparavant requises. Le troisième est l'hypothèse de Diffie-Hellman computationnel, une pierre angulaire de la sécurité Internet moderne utilisée pour échanger des clés secrètes. Pendant des décennies, la seule façon connue de construire des machines rapides à partir de cette hypothèse reposait sur une version plus forte et plus restrictive du problème. La nouvelle construction prouve que la version standard est suffisante.

La portée de ce travail réside dans sa généralité et son recours à des hypothèses standards. En montrant qu'un outil faible et peu profond peut être amélioré en un outil fort et sécurisé sans ajouter de profondeur, les chercheurs ont débloqué la capacité de construire des fonctions rapides et sûres à partir des problèmes mathématiques les plus basiques et les mieux étudiés. Cela résout plusieurs questions de longue date dans le domaine et fournit un nouveau schéma directeur flexible pour les futurs systèmes cryptographiques. Les chercheurs n'ont pas seulement suggéré que cela pourrait être possible ; ils ont fourni une construction concrète, étape par étape, et une preuve rigoureuse de son fonctionnement. Ils ont démontré que la profondeur de la machine résultante est essentiellement la même que la profondeur de l'outil de départ, préservant ainsi l'avantage de vitesse tout en gagnant la sécurité nécessaire.

Cette réussite signifie que, pour la première fois, nous pouvons construire ces outils de sécurité essentiels en utilisant les fondations mathématiques les plus communes et les plus fiables, sans sacrifier la vitesse. Cela élimine le besoin de variantes spécialisées et complexes de ces problèmes qui étaient auparavant jugées nécessaires pour l'efficacité. Le résultat est une base plus robuste et plus polyvalente pour la sécurité numérique de demain, permettant des méthodes de chiffrement plus rapides et plus efficaces qui peuvent être déployées à travers une large gamme de technologies. Ce travail constitue la preuve définitive que la barrière entre les outils faibles et rapides et les outils forts et rapides a été brisée, ouvrant la voie à une nouvelle ère de conception cryptographique efficace.

Résumé Technique : Fonctions Pseudorandom dans NC1 à partir de LWE/LPN/CDH

1. Énoncé du Problème

La construction de fonctions pseudorandomes (PRF) avec une faible complexité parallèle (spécifiquement dans la classe NC1, calculables par des circuits de taille polynomiale et de profondeur logarithmique) est un problème ouvert de longue date en cryptographie. Bien que les PRF puissent être construites de manière générique à partir de générateurs de nombres pseudoaléatoires (PRG) via la transformation de Goldreich-Goldwasser-Micali (GGM), cette méthode est intrinsèquement séquentielle. Même si le PRG sous-jacent est calculable en profondeur logarithmique, la PRF résultante nécessite une profondeur $\omega(\log n)$ , ce qui la place en dehors de NC1.

Avant ce travail, les PRF calculables dans NC1 étaient rares et reposaient sur des structures algébriques hautement spécifiques ou des hypothèses fortes :

Naor-Reingold (1997, 2004) : Ont construit des PRF dans $TC_0 \subseteq NC1$ à partir du problème de la décision Diffie-Hellman (DDH) et de la factorisation.
Banerjee-Peikert-Rosen (2012) : Ont construit des PRF dans $TC_0$ à partir de Ring-LWE, mais nécessitaient un rapport module-bruit super-polynomial.
Ding-Jain-Komargodski (2025) : Ont construit des PRF à partir de variantes structurées de Learning Parity with Noise (LPN), telles que SeededLPN ou Ring-LPN.

Le défi central est de parvenir à des PRF calculables dans NC1 à partir d'hypothèses standards (LWE avec un rapport module-bruit polynomial, LPN standard, et Computational Diffie-Hellman) sans dépendre de variantes structurées ou de paramètres super-polynomiaux.

2. Méthodologie

Le papier introduit une approche à deux volets : une transformation générique préservant la profondeur des WPRF (Weak PRFs) vers les PRF fortes, et de nouvelles constructions de WPRF efficaces en profondeur (ou synthétiseurs) à partir d'hypothèses standards.

2.1 Tapering-GGM : Une Transformation Générique

Les auteurs proposent une nouvelle adaptation de la construction d'arbre GGM, nommée Tapering-GGM, qui améliore une WPRF en une PRF forte tout en préservant la profondeur du circuit d'évaluation.

Le mécanisme de réduction (Tapering) : Dans un arbre GGM standard, la taille de l'état reste constante et la profondeur s'accumule linéairement avec le nombre de niveaux de l'arbre ( $\ell \cdot d_{WPRF}$ ). Dans le Tapering-GGM, la taille de l'état diminue géométriquement à chaque niveau. Si le paramètre de sécurité au niveau $i$ est $\lambda^{(i)}$ , les auteurs définissent $\lambda^{(i)} = \lambda^{2^{-i+1}}$ . Par conséquent, la profondeur de l'appel à la WPRF au niveau $i$ , notée $d(\lambda^{(i)})$ , diminue géométriquement.
Analyse de la profondeur : Si la WPRF de base a une profondeur $d(\lambda) = \Theta(\log \lambda)$ , la profondeur totale de la construction Tapering-GGM devient :
$d_{total} = O(\log \lambda) + \sum_{i=1}^{\ell} d(\lambda^{(i)}) \approx O(\log \lambda) + \sum_{i=1}^{\ell} \log(\lambda^{2^{-i+1}}) = O(\log \lambda)$
Cette décroissance géométrique garantit que la profondeur totale reste $O(d(\lambda))$ , maintenant la construction dans NC1 si la WPRF d'entrée est dans NC1.
Défis de sécurité et solutions :
- Défi : À mesure que l'arbre s'approfondit, le paramètre de sécurité $\lambda^{(i)}$ devient petit (sub-polynomial), ce qui pourrait briser la sécurité computationnelle de la WPRF sous-jacente.
- Solution 1 (Hachage) : L'entrée est d'abord hachée via une fonction de hachage à indépendance par paires. Cela garantit qu'avec une probabilité élevée, les requêtes de l'adversaire sont « éclatées » (projetées sur des chemins distincts) dans les premiers $O(\log_\Delta q)$ niveaux, où le paramètre de sécurité est encore polynomial.
- Solution 2 (Uniformité de la clé) : Pour les niveaux inférieurs au point d'éclatement, la construction repose sur la sécurité informationnelle. Les auteurs exigent que la WPRF soit clé-uniforme (1-indépendante). Si l'état au niveau de l'éclatement est pseudorandom, la composition subséquente de transformations clé-uniformes projette cet état vers une sortie parfaitement uniforme, indépendamment de la dureté computationnelle des WPRF de niveau inférieur.

2.2 Constructions de WPRF Efficaces en Profondeur

Les auteurs instancient le cadre Tapering-GGM avec de nouvelles constructions de WPRF à partir d'hypothèses standards :

À partir de LWE (Learning With Errors) :
- Les auteurs construisent la première WPRF en NC1 à partir de LWE standard avec un rapport module-bruit polynomial ( $\alpha = n^{-\epsilon}$ ).
- Outil technique clé : Un Échantillonneur Gaussien Arrondi (Rounded Gaussian Sampler) calculable en $O(\text{poly}(\log \log \lambda))$ de profondeur. Ils approchent la transformée de Box-Muller en utilisant des approximations polynomiales de faible profondeur pour $\ln$ , $\cos$ , et l'itération de Newton pour les racines carrées.
- Construction : Ils emploient un paradigme de chaînage (inspiré par Kim [Kim20]). La construction calcule des produits scalaires LWE masqués couche par couche. Les bits de poids fort de la sortie d'une couche échantillonnent de manière déterministe la distribution d'erreur de la couche suivante. Le bornage de l'échantillonneur d'erreur assure la stabilité, permettant de procéder via des hybrides pour la preuve de sécurité.
À partir de LPN (Learning Parity with Noise) :
- Les auteurs exploitent un résultat récent de Ding, Jain et Komargodski [DJK25] qui fournit des WPRF en NC1 à partir de LPN standard (bruit inverse polynomial arbitraire).
- En combinant cela avec le Tapering-GGM, ils obtiennent les premières PRF en NC1 à partir de LPN standard, éliminant le besoin de variantes structurées (ex: Ring-LPN).
À partir de CDH (Computational Diffie-Hellman) :
- Les auteurs observent que le Tapering-GGM nécessite en réalité une primitive plus faible qu'une WPRF : un Synthétiseur (où le pool d'entrée est caché à l'adversaire).
- Ils instancient la transformation en utilisant la construction de synthétiseur Naor-Reingold [NR95, NR99], qui est calculable en NC1 sous l'hypothèse CDH. Cela produit les premières PRF en NC1 à partir de CDH, améliorant les constructions précédentes basées sur DDH.

3. Contributions Clés

Transformation Générique Préservant la Profondeur : Une transformation boîte noire qui convertit toute WPRF (ou synthétiseur) calculable en profondeur $d(\lambda) = \Omega(\log \lambda)$ en une PRF forte calculable en profondeur $O(d(\lambda))$ . Cela résout la barrière générique empêchant les PRF en NC1 à partir d'hypothèses standards.
PRF en NC1 à partir de LWE Standard : La première construction de PRF en NC1 à partir de LWE avec un rapport module-bruit polynomial, résolvant un problème ouvert explicitement mentionné dans les notes de cours de Vaikuntanathan. Cela repose sur la dureté de GapSVP avec des facteurs d'approximation polynomiaux.
PRF en NC1 à partir de LPN Standard : La première construction de PRF en NC1 à partir de l'hypothèse LPN standard, éliminant le besoin de variantes structurées comme Ring-LPN ou Sparse LPN.
PRF en NC1 à partir de CDH : La première construction de PRF en NC1 à partir de l'hypothèse Computational Diffie-Hellman, améliorant le résultat de Naor-Reingold vieux de 30 ans qui reposait sur la DDH plus forte.
Échantillonneur Gaussien à Faible Profondeur : Un nouveau circuit déterministe pour échantillonner des erreurs gaussiennes arrondies en $O(\text{poly}(\log \log \lambda))$ de profondeur, qui est un composant critique pour la WPRF basée sur LWE.

4. Résultats

Le papier établit les résultats concrets suivants :

Théorème : S'il existe des WPRF en NC1, alors il existe des PRF en NC1.
Corollaire (LWE) : En supposant que l'hypothèse LWE soit vraie pour un rapport bruit-module $\alpha = n^{-\epsilon}$ , il existe des PRF en NC1.
Corollaire (LPN) : En supposant que l'hypothèse LPN soit vraie pour une probabilité de bruit $\mu = n^{-\epsilon}$ , il existe des PRF en NC1.
Corollaire (CDH) : En supposant que l'hypothèse CDH soit vraie, il existe des PRF en NC1.
Corollaire (GapSVP) : En supposant que GapSVP soit difficile à approximer à un facteur $\tilde{O}(n^{1+\epsilon})$ , il existe des PRF en NC1.

5. Signification

Le papier prétend résoudre plusieurs problèmes ouverts de longue date dans la complexité des primitives cryptographiques. En découplant la profondeur d'évaluation de la PRF de la nature séquentielle de la transformation GGM, les auteurs démontrent que des PRF fortes peuvent être construites à partir d'un large éventail d'hypothèses standards sans sacrifier l'efficacité parallèle.

Plus précisément, ce travail :

Supprime la dépendance à Ring-LWE et aux paramètres super-polynomiaux pour les PRF en NC1, passant à un LWE standard avec des paramètres polynomiaux.
Supprime la dépendance aux variantes structurées de LPN, passant à un LPN standard.
Affaiblit l'hypothèse de dureté pour les PRF basées sur CDH, passant de DDH à CDH.
Fournit un cadre générique (Tapering-GGM) qui peut mettre à niveau n'importe quel candidat de WPRF à profondeur logarithmique existant (ex: [ABG+14], [AR16]) en une PRF à profondeur logarithmique, à condition que l'hypothèse sous-jacente soit respectée.

Les auteurs positionnent ce travail comme une étape fondamentale pour comprendre la complexité parallèle de la cryptographie, avec des implications pour les protocoles de calcul sécurisé, la théorie de l'apprentissage (via les connexions PRF-versus-learning) et la méta-complexité.