Mind the Gap? Not for SVP Hardness under ETH!

1. Problématique et Contexte

L'article s'intéresse à la complexité fine-grainée des problèmes fondamentaux sur les réseaux (lattices) sous l'hypothèse du temps exponentiel (ETH - Exponential Time Hypothesis).

• Les problèmes clés :
  • SVP (Shortest Vector Problem) : Trouver le vecteur non nul le plus court dans un réseau.
  • CVP (Closest Vector Problem) : Trouver le vecteur du réseau le plus proche d'un vecteur cible donné.
  • BDD (Bounded Distance Decoding) : Une variante de CVP où la cible est garantie d'être très proche du réseau.
• Le contexte théorique :
  • La dureté d'approximation de ces problèmes est bien établie sous l'hypothèse Gap-ETH (une version renforcée de l'ETH qui postule que distinguer les instances satisfiables des instances très non-satisfiables de 3-SAT nécessite un temps $2^{\Omega(n)}$).
  • Cependant, la dureté sous l'hypothèse ETH standard (qui ne postule que l'impossibilité de résoudre 3-SAT en temps $2^{o(n)}$, sans hypothèse de "gap" explicite) était un problème ouvert majeur pour ces problèmes de réseaux, en particulier pour le SVP.
  • L'objectif est de combler ce fossé : démontrer que la dureté connue sous Gap-ETH peut être obtenue sous l'hypothèse ETH seule.

2. Méthodologie et Techniques Clés

Les auteurs construisent une chaîne de réductions polynomiales (déterministes et randomisées) reliant le problème 3-SAT aux problèmes de réseaux.

A. De 3-SAT à MAXLIN (Réduction existante)

L'article s'appuie sur une percée récente de Bitansky et al. [BHIRW24], qui fournit une réduction polynomiale de 3-SAT vers le problème gap-MAXLIN (un problème de satisfaction de contraintes linéaires sur un corps fini, ici $\mathbb{F}_2$). Cela établit que MAXLIN est dur sous ETH.

B. De MAXLIN à CVP (Réduction Déterministe)

Les auteurs proposent une réduction déterministe directe de MAXLIN vers CVP$_{p,\gamma}$ (le problème du vecteur le plus proche en norme $\ell_p$ avec un facteur d'approximation $\gamma$).

• Technique : Ils construisent une matrice $B = [M \mid 2I_m]$ et un vecteur cible $t = v$.
• Astuce : L'ajout de $2I_m$ force les calculs de distance à être effectués modulo 2, simulant ainsi l'arithmétique sur $\mathbb{F}_2$.
• Résultat : Si l'instance MAXLIN est une instance "OUI", il existe un vecteur du réseau proche de $t$ (distance $\le r$). Si c'est une instance "NON", tous les vecteurs sont loin (distance $> \gamma r$). Cela prouve la dureté de CVP sous ETH pour tout $p \in [1, \infty)$.

C. De CVP à SVP (Réduction Randomisée et Nouvelle Propriété Géométrique)

C'est la contribution principale de l'article. Réduire CVP à SVP est difficile car le SVP ne possède pas de vecteur cible externe. Les auteurs utilisent une technique de sparsification de réseau (échantillonnage d'un sous-réseau aléatoire) couplée à un gadget géométrique.

• Le Gadget Localement Dense : Ils exploitent une propriété nouvelle de la grille entière $\mathbb{Z}^n$ en norme $\ell_p$ pour $p > 2$.
  • Propriété : Pour $p > 2$, le nombre de vecteurs du réseau proches du vecteur $\frac{1}{2}\mathbf{1}_n$ (où $\mathbf{1}_n$ est le vecteur de tous les 1) est exponentiellement plus grand que le nombre de vecteurs courts (proches de l'origine).
  • Preuve technique : Ils établissent cette propriété via une nouvelle inégalité sur la fonction thêta $\Theta_p(\tau, t)$. En utilisant l'analyse de Fourier et la formule de sommation de Poisson, ils montrent que pour tout $p > 2$, il existe un $\tau > 0$ tel que $\Theta_p(\tau, 1/2) > \Theta_p(\tau, 0)$. Cela contraste avec le cas $p=2$ où l'inégalité inverse est vraie.
• La Réduction :
  1. On part d'une instance CVP construite précédemment.
  2. On l'augmente avec le gadget $\mathbb{Z}^d$ centré en $\frac{1}{2}\mathbf{1}_d$.
  3. Si l'instance CVP est "OUI", le nombre de vecteurs courts dans le nouveau réseau explose (dû au gadget).
  4. Si l'instance CVP est "NON", le nombre de vecteurs courts reste faible.
  5. Une étape de sparsification (réduction de Khot) échantillonne un sous-réseau aléatoire qui conserve les vecteurs courts avec une probabilité élevée si l'instance est "OUI", mais les élimine tous si l'instance est "NON".

D. De CVP à BDD

Les auteurs améliorent également les réductions existantes de CVP vers BDD (décodage à distance bornée). En utilisant des gadgets similaires et une analyse fine des constantes, ils montrent que la dureté de BDD peut être établie sous ETH pour des paramètres $\alpha > \alpha^\ddagger_p$, où $\alpha^\ddagger_p$ est un seuil explicite dépendant de $p$.

3. Résultats Principaux

Les auteurs établissent les résultats suivants (sauf mention contraire, les réductions sont polynomiales) :

1. Dureté de CVP sous ETH :
   Pour tout $p \in [1, \infty)$, il existe une constante $\gamma > 1$ telle que CVP$_{p,\gamma}$ n'admet pas d'algorithme en temps $2^{o(n)}$ sous l'hypothèse ETH.

   • Note : C'est la première preuve de dureté sous ETH pour CVP dans les normes $\ell_p$ générales.

2. Dureté de SVP sous ETH (Résultat Majeur) :
   Pour tout $p \in (2, \infty)$, il existe une constante $\gamma > 1$ telle que SVP$_{p,\gamma}$ n'admet pas d'algorithme en temps $2^{o(n)}$ sous l'hypothèse ETH randomisée.

   • Note : Ce résultat comble le fossé entre les résultats connus sous Gap-ETH et ETH. Le cas $p=2$ reste une question ouverte (Open Problem 1).

3. Dureté de BDD sous ETH :
   Pour tout $p \in [1, \infty)$ et tout $\alpha > \alpha^\ddagger_p$, BDD$_{p,\alpha}$ n'admet pas d'algorithme en temps $2^{o(n)}$ sous l'hypothèse ETH randomisée.

   • Cela améliore les résultats antérieurs qui nécessitaient Gap-ETH.

4. Conséquence pour les Codes Linéaires :
   En tant que corollaire, ils obtiennent la dureté ETH du problème de la distance minimale (MDP) pour les codes linéaires, car MAXLIN est essentiellement équivalent au problème du vecteur le plus proche dans les codes (NCP).

4. Signification et Impact

• Réduction de l'hypothèse de complexité : L'article démontre que la dureté fine-grainée des problèmes de réseaux ne dépend pas nécessairement de l'hypothèse forte Gap-ETH, mais peut être dérivée de l'hypothèse ETH standard (ou randomisée). Cela renforce la crédibilité des hypothèses de sécurité utilisées en cryptographie post-quantique.
• Nouvelles propriétés géométriques : La découverte de la propriété de densité locale de la grille entière $\mathbb{Z}^n$ pour $p > 2$ (via l'analyse de la fonction thêta) est un résultat mathématique indépendant potentiellement utile pour d'autres problèmes d'optimisation sur les réseaux.
• Cryptographie Post-Quantique : La sécurité de nombreux schémas standardisés par le NIST (comme Kyber, Dilithium) repose sur la difficulté supposée de résoudre SVP/CVP en temps sous-exponentiel. Ces résultats renforcent la base théorique de ces schémas en éliminant la possibilité d'algorithmes sous-exponentiels "faciles" sous des hypothèses de complexité plus faibles.
• Ouverture : Le cas $p=2$ (norme Euclidienne) pour le SVP sous ETH reste un problème ouvert, bien que les auteurs notent que la dureté pour $p < 2$ découle de celle pour $p=2$ par des techniques d'embedding de normes.

En résumé, cet article établit une nouvelle frontière de dureté pour les problèmes fondamentaux de la théorie des réseaux, en prouvant que même sans l'hypothèse Gap-ETH, aucun algorithme sous-exponentiel ne peut résoudre ces problèmes, consolidant ainsi les fondements de la cryptographie post-quantique.