Résumé technique : Vers la dureté dans le pire des cas pour le LPN à faible bruit

Énoncé du problème

Le problème de l'apprentissage de la parité avec du bruit (Learning Parity with Noise - LPN) est une hypothèse fondamentale en cryptographie, servant de base aux primitives à clé symétrique et au chiffrement à clé publique (P-K). Alors que la dureté en moyenne du problème analogue LWE (Learning With Errors) est soutenue par des hypothèses sur les réseaux (lattices) dans le pire des cas, l'établissement d'une réduction similaire du pire des cas vers le cas moyen pour LPN demeure une question ouverte centrale.

Les réductions existantes pour LPN, spécifiquement celles de Brakerski et al. [BLVW19] et de Yu et Zhang [YZ21], reposent sur le lissage statistique de codes linéaires. Ces méthodes exigent que des combinaisons creuses aléatoires des lignes d'une matrice génératrice soient statistiquement proches de l'uniformité. Cette exigence limite intrinsèquement la dureté en moyenne résultante à des taux de bruit aussi élevés que $1/2 - 1/\text{poly}(n)$. De tels taux de bruit élevés sont insuffisants pour les applications de clé publique, qui nécessitent généralement une dureté à des taux de bruit inversement polynomiaux (par exemple, $n^{-1/2}$) ou des taux de bruit constants contre des algorithmes de temps sous-exponentiel. De plus, les hypothèses sur le pire des cas requises par ces réductions existantes (par exemple, la dureté du problème du code le plus proche avec des taux de bruit très faibles) sont soit faibles, soit nécessitent des hypothèses de pré-traitement irréalistes.

Méthodologie

Les auteurs proposent une nouvelle approche qui relâche l'exigence de lissage statistique au profit de la distinguabilité computationnelle. Au lieu d'exiger que les combinaisons creuses aléatoires des lignes du code soient statistiquement proches de l'uniformité, les auteurs exigent seulement qu'elles soient computationnellement indiscernables de l'uniformité.

Ce changement conduit à une structure « win-win » basée sur les propriétés d'une matrice donnée $A \in \mathbb{F}_2^{m \times n}$ :

1. Décodage du code : Si les combinaisons aléatoires sont computationnellement indiscernables de l'uniformité, un solveur LPN efficace peut être utilisé pour décoder le code généré par $A$ à partir d'un bruit aléatoire.
2. Distinction du dual : Si les combinaisons aléatoires ne sont pas computationnellement indiscernables de l'uniformité, le discriminateur résout effectivement une version décisionnelle du problème de décodage du code dual de $A$ (spécifiquement, distinguer des syndromes de poids fixe de l'uniformité).

La réduction repose sur l'observation que si $A$ est considérée comme une matrice génératrice, alors $A^T$ agit comme la matrice de contrôle de parité du code dual. Récupérer un vecteur $r$ étant donné $r^T A$ est équivalent au décodage du code dual avec $r$ comme vecteur de bruit.

Contributions clés et résultats

1. Théorème de réduction principal

Le papier présente une réduction (Théorème 3.1) montrant que la dureté de LPN peut être dérivée de la dureté simultanée dans le pire des cas de deux problèmes :

• Le décodage d'un code généré par une matrice $A$ à partir d'un bruit aléatoire.
• La distinction de mots de code bruités (syndromes) du code dual de $A$ par rapport à l'uniformité.

Théorème 1.1 (Informel) : Supposons qu'il existe un algorithme efficace avec un avantage non négligeable pour résoudre le Search LPN avec $n$ variables, $t$ échantillons, et un taux de bruit $n^{-\alpha}$ (pour une constante $\alpha < 1$). Alors, pour toute constante $\beta > 0$ telle que $\alpha + \beta < 1$, il existe des algorithmes efficaces $S$ et $D$ tels que pour toute matrice $A$ :

• Soit $S$ peut décoder le code généré par $A$ à partir d'un bruit aléatoire de taux $n^{-(\alpha+\beta)}$.
• Soit $D$ peut distinguer les mots de code bruités du dual de $A$ de l'uniformité pour un taux de bruit $n^{\beta}/m$.

2. Instanciation pour la cryptographie à clé publique

En fixant des paramètres spécifiques, les auteurs démontrent que leur réduction produit la dureté de LPN dans le régime requis pour la construction de chiffrement à clé publique d'Alekhnovich [Ale03].

• Paramètres : En fixant $\alpha = 0.5$ (taux de bruit cible $n^{-0.5}$), $\beta = 0.45$, et $m = O(n^{2.9})$.
• Résultat : Cela implique la dureté de LPN avec $t=2n$ échantillons et un taux de bruit $n^{-0.5}$, en supposant la dureté simultanée dans le pire des cas du décodage d'un code et de son dual.
• Signification : Ce régime de paramètres était auparavant inaccessible via des réductions dans le pire des cas utilisant le lissage statistique.

3. Défis techniques et solutions

Les auteurs abordent la difficulté de passer du lissage statistique au lissage computationnel. Dans le cadre statistique, l'analyse de Fourier gère facilement la distribution jointe de la matrice lissée et du bruit. Dans le cadre computationnel, les auteurs montrent que même si $r^T A$ est pseudo-aléatoire, la fuite $r^T e$ pourrait potentiellement rendre la distribution jointe distinguable.

• Solution : La réduction construit un algorithme $S$ qui décode à partir d'un bruit de Bernoulli aléatoire plutôt que d'un bruit du pire des cas. Les auteurs prouvent que pour la plupart des choix de vecteurs de lissage $r$, les bits $r^T e$ se comportent comme des variables de Bernoulli indépendantes même après avoir fixé $r$. Cela permet à la réduction de procéder sans exiger que $r^T e$ soit non biaisé pour tous les vecteurs d'erreur du pire des cas, une condition qui constituait auparavant une barrière.

Signification et affirmations

Le papier affirme fournir une voie pour établir la dureté en moyenne de LPN avec des taux de bruit inversement polynomiaux (spécifiquement $n^{-1/2}$) basés sur des hypothèses dans le pire des cas. C'est une étape significative vers la construction de chiffrements à clé publique à partir d'hypothèses de dureté dans le pire des cas, un objectif qui a été difficile à atteindre pour LPN par rapport à LWE.

Les auteurs notent explicitement les limitations et les affirmations modestes suivantes :

• Hypothèse non standard : La réduction repose sur la dureté simultanée du décodage d'un code et de son dual. Cette hypothèse est non standard et n'a pas été étudiée de manière indépendante. Les auteurs ne prétendent pas que cette hypothèse est plus faible que les autres, mais plutôt qu'elle est une condition nécessaire pour que leur approche spécifique contourne la barrière du lissage statistique.
• Bruit aléatoire vs Bruit du pire des cas : Le décodeur $S$ résultant fonctionne contre un bruit de Bernoulli aléatoire, alors que les réductions précédentes (par exemple, [BLVW19]) produisaient des décodeurs pour un bruit de poids borné dans le pire des cas. Les auteurs reconnaissent que l'extension de leur approche au bruit du pire des cas renforcerait considérablement le résultat, mais nécessiterait de nouveaux outils pour raisonner sur l'entropie computationnelle.
• Temps sous-exponentiel : Les meilleurs algorithmes connus pour les problèmes du pire des cas spécifiés dans le théorème (décodage d'un code générique et de son dual) s'exécutent en temps sous-exponentiel. Ainsi, la réduction établit la dureté de LPN contre des algorithmes de temps polynomial basé sur des hypothèses de dureté sous-exponentielle dans le pire des cas.

En résumé, le papier propose une réduction « clean win-win » qui échange l'exigence statistique de lissage pour une exigence computationnelle, permettant la dureté de LPN à des taux de bruit suffisants pour le chiffrement à clé publique, à condition d'accepter la dureté simultanée du décodage d'un code et de son dual.