Résumé technique : Fonctions à indépendance bornée rapides et leurs duales

Énoncé du problème

L'article traite du défi consistant à construire des primitives cryptographiques qui imitent les propriétés statistiques des fonctions aléatoires et des codes linéaires aléatoires tout en maintenant un surcoût de calcul constant. Plus précisément, les auteurs recherchent des implémentations « rapides » — définies comme étant calculables par des circuits arithmétiques de taille linéaire (taille $O(n)$) — qui satisfont :

1. Indépendance bornée : Des fonctions de hachage qui sont $t$-indépendantes pour tout $t$ constant.
2. Codes duaux rapides : Des familles de codes linéaires où le code et son dual admettent tous deux un encodage systématique rapide et atteignent des distances proches de la borne de Gilbert-Varshamov (GV).
3. Propriétés de type aléatoire plus fortes : Aller au-delà de la simple distance pour inclure des propriétés telles que la décodabilité en liste, garantissant que les codes se comportent comme des codes linéaires aléatoires même sous des contraintes locales (similarité locale).

Des travaux antérieurs, tels que [IKOS08] et [DI14], ont établi des fonctions de hachage à indépendance par paire rapides et des codes rapides approchant la borne GV, mais avec des limitations concernant le paramètre d'indépendance $t$, le corps de calcul, ou la capacité à optimiser simultanément le code et son dual. Une construction récente par [BR26] a amélioré les codes duaux rapides, mais était restreinte aux corps binaires, nécessitait un taux fixe de 1/2, présentait une probabilité d'échec non négligeable et manquait d'encodage systématique.

Méthodologie

Les auteurs s'appuient sur la « construction IKOS » (Ishai, Kushilevitz, Ostrovsky, Sahai) et la « construction DI » (Druk, Ishai), en les généralisant à des paramètres d'indépendance plus élevés.

1. Généralisation des fonctions de hachage

La construction centrale pour les fonctions de hachage suit un pipeline en trois étapes :

1. Encodage extérieur : Appliquer un code linéaire rapide avec une grande distance sur un alphabet large (mais constant) à l'entrée.
2. Hachage intérieur : Appliquer des fonctions de hachage à taille constante et $t$-indépendantes à chaque coordonnée du vecteur encodé.
3. Extraction : Appliquer la transposée d'une matrice génératrice d'un bon code (agissant comme un extracteur) au résultat.

Pour obtenir une $t$-indépendance, les auteurs remplacent les fonctions de hachage à indépendance par paire de taille constante de l'étape intérieure par des fonctions de hachage $t$-indépendantes de taille constante. Ils prouvent que si le code extérieur possède une distance suffisamment grande (spécifiquement $> 1 - 1/t^2$), la distinction de $t$ entrées est préservée à travers une fraction suffisante de coordonnées, permettant aux fonctions de hachage intérieures de produire des sorties uniformes et indépendantes que l'étape d'extraction finale préserve.

2. Familles de sorties uniformes linéaires (LUOF)

Pour construire les codes, les auteurs utilisent le concept de Famille de Sorties Uniformes Linéaires (LUOF). Une matrice aléatoire $A$ est une LUOF si, pour toute entrée non nulle $x$, la sortie $xA$ est uniformément distribuée.

• LUOF rapide : Les auteurs généralisent la construction de [DI14] pour créer une $t$-LUOF rapide. Une matrice $A$ est une $t$-LUOF si, pour tout ensemble de $t$ entrées linéairement indépendantes $x_1, \dots, x_t$, les sorties $x_1A, \dots, x_tA$ sont uniformément et stochastiquement indépendantes.
• Construction : Similaire à la construction de la fonction de hachage, cela implique un code extérieur, une couche de matrices constantes aléatoires (agissant comme la fonction « intérieure ») et une étape d'extraction. Les auteurs prouvent que si le code extérieur a une distance suffisante, les matrices aléatoires intérieures projettent les entrées linéairement indépendantes vers des sorties uniformes et indépendantes.

3. Construction de codes duaux rapides

En utilisant une matrice $t$-LUOF $A \in \mathbb{F}_q^{k \times r}$, les auteurs définissent un code $C$ avec l'application d'encodage systématique $x \mapsto (x, xA)$.

• Dualité : Le code dual $C^\perp$ est généré par l'application $y \mapsto (-yA^\top, y)$.
• Principe de transposition : En citant le principe de transposition (Lemme 3.4), ils soutiennent que si le calcul de $xA$ est rapide (taille linéaire), alors le calcul de $yA^\top$ est également rapide.
• Indépendance du dual : Une contribution technique cruciale est de prouver que si $A$ est une $t$-LUOF, alors $A^\top$ est également une $t$-LUOF (Lemme 3.9). Cela repose sur le lemme XOR de Vazirani et garantit que le code dual hérite des fortes propriétés de hasard du code primal.

Contributions clés et résultats

1. Fonctions de hachage $t$-indépendantes rapides

• Résultat : Pour tout $t$ constant, les auteurs construisent une famille de fonctions de hachage $t$-indépendantes calculables par des circuits de taille linéaire.
• Optimisation : Pour le corps binaire ($q=2$), le degré algébrique est optimisé à $\log_2 t$. C'est un résultat proche de l'optimalité, car des degrés inférieurs ne permettraient pas de supporter la $t$-indépendance.
• Efficacité : La taille du circuit est $O(k+r)$, où $k$ est la longueur d'entrée et $r$ la longueur de sortie. La constante cachée dépend de $t$ (environ $\Theta(t^7)$), mais reste constante pour un $t$ fixé.

2. Codes rapides avec duaux rapides (Borne GV)

• Résultat : Les auteurs construisent une famille de codes $C$ et de leurs duaux $C^\perp$ sur n'importe quel corps fini $\mathbb{F}_q$ avec un taux $R \in (0, 1)$ arbitraire.
• Propriétés :
  • Tant $C$ que $C^\perp$ admettent un encodage systématique rapide (taille linéaire).
  • Tous deux atteignent des distances $\varepsilon$-proches de la borne de Gilbert-Varshamov avec une probabilité de $1 - 2q^{-\varepsilon n}$.
  • La construction présente une probabilité d'échec négligeable (contrairement à [BR26]).
  • Elle supporte un circuit universel de taille linéaire pour l'encodage.

3. Codes à décodage en liste rapides avec duaux rapides

• Résultat : En utilisant la propriété $t$-LUOF, les auteurs étendent la construction à des codes qui sont $t$-localement similaires à des codes linéaires aléatoires.
• Décodage en liste : Ils prouvent que pour tout $t$ constant, les codes construits (et leurs duaux) sont $(\rho, L)$-décodables en liste jusqu'à la capacité de décodage en liste, avec une taille de liste $L = O(1/\varepsilon)$.
• Nouveauté : C'est la première construction (à la connaissance des auteurs) qui atteint simultanément l'encodage rapide, l'encodage du dual rapide et la décodabilité en liste optimale pour le code et son dual.

Signification et applications cryptographiques

L'article démontre que ces constructions servent de blocs de construction puissants pour la cryptographie, particulièrement dans des scénarios exigeant une haute efficacité et des garanties de sécurité fortes.

1. Calcul multipartite (MPC) parfaitement sécurisé

Les auteurs présentent les premiers protocoles non triviaux pour le calcul multipartite parfaitement sécurisé où la complexité du circuit passe linéairement avec le nombre de parties ($O(n)$).

• Contexte : Les protocoles précédents utilisant des codes algébriques (comme les codes de Reed-Solomon) imposaient souvent un surcoût quasi-linéaire.
• Application : En utilisant les codes duaux rapides, ils construisent un protocole d'Évaluation Linéaire Oblivieuse (OLE) et l'étendent à des fonctions générales de taille constante. Le protocole atteint un seuil de sécurité de $t = (1/2 - \varepsilon)n$ contre des adversaires passifs.

2. Produits Matrice-Vecteur Chiffrés (EMVP)

Dans le contexte de la cryptographie basée sur la complexité, les auteurs appliquent leurs codes duaux rapides aux produits matrice-vecteur chiffrés.

• Amélioration : Leur construction surmonte les limitations de l'approche [BR26] (qui était limitée à $\mathbb{F}_2$ et avait une probabilité d'échec non négligeable).
• Bénéfice : Cela permet des protocoles EMVP où l'encodage de la matrice et l'encodage de la requête ont tous deux une complexité de circuit asymptotiquement optimale.

3. Substituts conservateurs des codes linéaires aléatoires

La construction $t$-LUOF fournit un substitut « conservateur » pour les codes linéaires aléatoires dans les applications reposant sur la difficulté de l'algèbre linéaire bruitée (ex: Learning Parity with Noise - LPN).

• Avantage : Alors que les constructions précédentes ne reposaient que sur la distance minimale (similarité locale de degré 1), la $t$-LUOF assure une similarité locale de degré $t$, garantissant des propriétés combinatoires plus fortes comme la décodabilité en liste. Cela offre une hypothèse de sécurité plus robuste contre les attaques qui pourraient exploiter des structures locales.

4. Hachage compatible avec la MPC

Les fonctions de hachage $t$-indépendantes rapides avec un faible degré algébrique sont directement applicables aux protocoles MPC où la taille du circuit et le degré algébrique impactent simultanément la communication et la complexité des tours. La construction optimise les deux simultanément.

Conclusion

L'article généralise avec succès les constructions précédentes de taille linéaire pour supporter des paramètres d'indépendance plus élevés et des propriétés de type aléatoire plus fortes. En introduisant les $t$-LUOF rapides et en prouvant leurs propriétés de dualité, les auteurs fournissent un cadre unifié pour construire des codes et des fonctions de hachage qui sont simultanément rapides, systématiques et statistiquement robustes. Ces résultats permettent de nouveaux protocoles cryptographiques avec une complexité asymptotique optimale, particulièrement dans la MPC informationnelle et le calcul chiffré.