Improved Search-to-Decision Reduction for Random Local Functions

1. Problème et Contexte

L'article s'intéresse aux fonctions locales aléatoires (Random Local Functions), une famille de primitives cryptographiques introduite par Goldreich en 2011. Une telle fonction $f_{G,P}$ est définie par :

• Un prédicat $P$ de constante $d$ (une fonction booléenne à $d$ entrées).
• Un hypergraphe aléatoire $G$ reliant les bits d'entrée aux bits de sortie.
• Chaque bit de sortie est le résultat de l'application de $P$ à $d$ bits d'entrée choisis aléatoirement.

Ces fonctions sont des candidats prometteurs pour les fonctions à sens unique (OWF) et les générateurs de nombres pseudo-aléatoires (PRG) locaux (calculables en temps constant, circuits de profondeur constante $NC^0$).

Le problème central abordé est la réduction "Recherche vers Décision" (Search-to-Decision) :

• Problème de Décision : Distinguer la sortie d'une fonction locale (sur une entrée secrète $s$) d'une chaîne de bits aléatoire (avec le même biais que $P$).
• Problème de Recherche : Inverser la fonction, c'est-à-dire retrouver l'entrée secrète $s$ (ou une pré-image) à partir de la sortie.

Le défi : Jusqu'à présent, les réductions connues de la décision vers la recherche nécessitaient que le prédicat $P$ possède une propriété de sensibilité (il existe une variable d'entrée dont le retournement change toujours la sortie). De nombreux prédicats cryptographiquement intéressants ne sont pas sensibles, limitant ainsi la portée des constructions de PRG basées sur l'hypothèse de la difficulté d'inversion.

2. Contributions Principales

Les auteurs proposent une nouvelle réduction qui élimine la nécessité de la propriété de sensibilité du prédicat.

Théorème Principal (Informel) :
Pour n'importe quel prédicat $P$ de constante $d$, s'il existe un algorithme efficace capable de distinguer la sortie d'une fonction locale (avec $m$ sorties et $n$ entrées) d'une chaîne aléatoire avec un avantage $\varepsilon$, alors il existe un algorithme efficace capable d'inverser la fonction avec une probabilité de succès $\Omega(\varepsilon)$, en utilisant $O(m(n/\varepsilon)^2 \log^3(n/\varepsilon))$ sorties.

Points clés de l'amélioration :

1. Généralité du prédicat : La réduction fonctionne pour tout prédicat, qu'il soit sensible ou non. Cela ouvre la voie à l'utilisation d'une gamme plus large de fonctions locales pour construire des PRG locaux forts.
2. Absence de prédicteur intermédiaire : Contrairement aux travaux antérieurs (comme Applebaum [App12]) qui construisaient d'abord un prédicteur de bits de sortie, cette méthode obtient directement l'algorithme de recherche à partir de l'algorithme de décision.
3. Robustesse : La méthode se généralise à des arités $d$ non constantes (jusqu'à $d = \text{polylog}(n)$), aux prédicats bruyants (modèle LPN) et aux modèles où les hyperarêtes doivent contenir des sommets distincts.

3. Méthodologie et Techniques Clés

La preuve repose sur une construction ingénieuse utilisant des hybrides et des transformations aléatoires sur l'hypergraphe.

A. Idée de la Réduction

L'objectif est de transformer l'instance de décision (distinguer $f(s)$ du bruit) en un problème de prédiction de la relation entre deux bits de l'entrée secrète ($s_1$ et $s_i$).

1. On part d'un distinguisher $D$ avec avantage $\varepsilon$.
2. On construit une série d'algorithmes prédicteurs $S_2, \dots, S_n$. Chaque $S_i$ tente de prédire si $s_1 = s_i$ ou $s_1 \neq s_i$.
3. Si $s_1 = s_i$, la transformation appliquée préserve la distribution "planted" (celle de la fonction).
4. Si $s_1 \neq s_i$, la transformation "brise" la corrélation, rendant la distribution proche du bruit aléatoire.
5. La différence de comportement de $D$ sur ces deux cas permet de déduire la relation entre les bits.

B. La Transformation Clé ($T_{a,b}$)

Le cœur de la technique est une transformation aléatoire $T_{a,b}$ appliquée à l'hypergraphe $G$ :

• Pour chaque hyperarête, si un sommet est $a$ ou $b$, il est remplacé aléatoirement par $a$ ou $b$ avec probabilité $1/2$. Sinon, il reste inchangé.
• Propriété de mélange (Mixing) : Si l'on applique cette transformation $t = O(n \log(nm/\varepsilon))$ fois de manière itérative avec des paires $(a,b)$ aléatoires, l'hypergraphe résultant devient statistiquement indistinguable d'un hypergraphe uniformément aléatoire, indépendamment de l'entrée initiale.

C. Argument Hybride

On définit une suite d'hybrides $H_0, \dots, H_t$ :

• $H_0$ correspond à la distribution initiale (fonction locale).
• $H_t$ correspond à une distribution proche du bruit aléatoire (grâce au temps de mélange).
• Si le distinguisher $D$ a un avantage $\varepsilon$ pour distinguer $H_0$ de $H_t$, alors par un argument hybride, il existe un indice $r$ où $D$ a un avantage $\approx \varepsilon/t$ pour distinguer $H_r$ de $H_{r+1}$.

D. Construction du Prédicteur

Pour prédire $s_1 \oplus s_i$ :

1. On applique $r$ transformations aléatoires à l'hypergraphe.
2. On applique ensuite une transformation spécifique $T_{\pi(1), \pi(i)}$ (où $\pi$ est une permutation aléatoire de l'entrée).
3. Cas $s_1 = s_i$ : La transformation $T_{\pi(1), \pi(i)}$ ne change pas la valeur de la fonction locale (car les bits d'entrée sont identiques). La distribution reste proche de $H_r$.
4. Cas $s_1 \neq s_i$ : La transformation modifie la distribution de manière effective, la rapprochant de $H_{r+1}$ (le bruit).
5. En exécutant $D$ sur ces instances transformées, on obtient un biais significatif pour déterminer si $s_1 = s_i$.

E. Amplification

Une fois un prédicteur avec un faible avantage $\Omega(\varepsilon/t)$ obtenu, les auteurs utilisent une amplification standard (répétition et seuillage) pour apprendre tous les bits $s_i$ par rapport à $s_1$, permettant de reconstruire $s$ avec une probabilité de succès $\Omega(\varepsilon)$.

4. Résultats et Complexité

• Complexité des échantillons : La réduction nécessite $O(m(n/\varepsilon)^2 \log^3(n/\varepsilon))$ sorties. Bien que cela implique une perte d'un facteur $n$ par rapport aux réductions pour les prédicats sensibles (qui sont optimaux), c'est le premier résultat général sans hypothèse de sensibilité.
• Généralisations :
  • Non-constante Sparsité : Fonctionne pour $d = \text{polylog}(n)$ sous certaines conditions sur $m$ et $\varepsilon$.
  • Valeurs Distinctes : S'adapte au modèle où les hyperarêtes ne contiennent pas de sommets répétés.
  • Prédicats Bruyants : S'applique au problème LPN (Learning Parity with Noise) où le prédicat est bruité.

5. Signification et Impact

1. Avancée Théorique : Cette travail résout un problème ouvert majeur en cryptographie locale en montrant que la sensibilité n'est pas une condition nécessaire pour la réduction Search-to-Decision. Cela renforce la crédibilité des fonctions locales comme candidats pour les OWF et PRG.
2. Construction de PRG : Combiné avec le "weak-to-strong compiler" d'Applebaum et Kachlon [AK19], ce résultat implique que si une famille de fonctions locales est à sens unique (même avec des prédicats non sensibles), alors une famille associée avec une longueur de sortie plus courte est un PRG local fort.
3. Nouvelles Techniques : La méthode de transformation aléatoire sur les hypergraphes pour créer un mélange statistique offre un outil puissant qui pourrait être réutilisé dans d'autres contextes de réduction ou d'analyse de complexité.
4. Limites : La complexité en échantillons est actuellement sous-optimale d'un facteur $\tilde{O}(n)$ par rapport aux cas sensibles. Les auteurs suggèrent que leurs techniques pourraient permettre de combler cet écart dans des travaux futurs.

En résumé, cet article fournit un cadre robuste et général pour relier la difficulté de distinguer les sorties de fonctions locales à la difficulté de les inverser, élargissant ainsi considérablement le paysage des primitives cryptographiques locales sécurisées.