# Problème de réseau

En informatique, les problèmes de réseau sont une classe de problèmes d'optimisation sur les réseaux. On conjecture que ces problèmes sont particulièrement difficiles à résoudre algorithmiquement : ces problèmes sont NP-difficiles, y compris en moyenne et non uniquement dans le pire des cas.
En conséquence, ces problèmes sont particulièrement intéressants pour la cryptographie, car ils peuvent servir à définir des primitives cryptographiques sûres. Pour des applications dans de tels systèmes cryptographiques, on utilise des réseaux définis sur des espaces vectoriels (souvent $\mathbb {Q} ^{n}$) ou des modules libres (souvent $\mathbb {Z} ^{n}$).
Dans les problèmes décrits ci-dessous, on suppose donnés une base d'un espace vectoriel V et une norme N (en général, il s'agira de la norme euclidienne L$^2$, mais on peut également utiliser d'autres normes L$^p$). On note Λ le réseau engendré par la base donnée

## Problème du plus court vecteur

Dans ce problème (abrégé en SVP pour shortest vector problem), on recherche un vecteur non-nul de la plus petite longueur possible (au sens de la norme N). Si l'on note λ cette longueur, c'est-à-dire:
$\lambda =\min _{v\in \Lambda \smallsetminus \{\mathbf {0} \}}\|v\|_{N}.$
alors la solution au problème est un vecteur v de longueur λ
Dans la version dite SVP$_γ$ on cherche une γ-approximation de la solution: un vecteur non nul de longueur au plus γ.λ où γ est un paramètre donné ≥ 1 dépendant de la dimension n du réseau.

### Complexité

On peut démontrer que la version exacte du problème est NP-difficile seulement pour des réductions aléatoires$^,$. En revanche, le problème considéré pour la norme uniforme est NP-difficile.

### Algorithmes pour le cas de la norme euclidienne

On peut diviser les algorithmes capables de résoudre le problème exact du plus court vecteur dans un réseau muni de la norme euclidienne en deux catégories : ceux dont la complexité en temps est super-exponentielle (2$^{ω(n)}$) et polynomiale en espace (par rapport à la dimension n du réseau), et ceux dont la complexité en temps et en espace sont toutes deux exponentielles (2$^{Θ(n)}$)
Dans la première catégorie on retrouve les méthodes d'énumération de réseaux$^,$$^,$, et de réduction par échantillonnage aléatoire$^,$; dans la deuxième, les méthodes de crible sur le réseau$^,$$^,$, le calcul des cellules de Voronoi sur le réseau$^,$, et l’échantillonnage Gaussien discret.
La recherche d'un algorithme qui résoudrait le problème exact en temps simplement exponentiel (2$^{O(n)}$) et polynomial en mémoire demeure un problème ouvert.
Pour résoudre le problème γ-approximé, les meilleures méthodes se basent sur la réduction de la base du réseau (en). Pour γ suffisamment grand (2$^{Ω(n)}$) l'algorithme de Lenstra-Lenstra-Lovász (LLL) peut trouver une solution en temps polynomial. Pour des valeurs plus petites de γ, il faut par exemple faire appel à l'algorithme des blocs de Korkine-Zolotarev (BKZ)$^,$$^,$, dans lequel la taille b des blocs détermine le compromis entre complexité en temps et la qualité du résultat (les petits blocs générant des approximations plus grossières mais plus rapidement). Cet algorithme utilisant la méthode de résolution exacte sur des réseaux de dimension au plus b, sa complexité est donc principalement due au coût en temps de ces résolutions en dimension b.

## Problème du plus proche vecteur

Ce problème (abrégé en CVP pour closest vector problem), on suppose donné, outre la base de vecteurs de l'espace vectoriel V engendrant le réseau Λ et la norme N, un vecteur v quelconque de V, qui n'est donc pas nécessairement un vecteur du réseau. On recherche alors le vecteur du réseau minimisant la distance avec v, c'est à dire
$x^{*}=\arg \min _{x\in \Lambda }\|\mathbf {v} -x\|_{N}$
Dans la version γ-approximative CVP$_γ$, on recherche à la place un vecteur du réseau dont la distance à v est au plus γ.

### Réduction du le problème du plus court vecteur

Le problème du plus proche vecteur peut être vu comme une généralisation du problème du plus court vecteur. En effet, si l'on suppose que l'on dispose d'un oracle capable de résoudre CVP$_γ$, alors on peut résoudre SVP$_γ$ en interrogeant l'oracle.
On ne peut pas simplement résoudre SVP$_γ$ en posant v = 0 dans un solveur de CVP$_γ$ (car le vecteur nul, membre du réseau, serait alors solution). En revanche, soit B = (b$_1$, b$_2$,... b$_n$) la base donnée pour le problème SVP. Alors On considère la base B$^i$ = (b$_1$, b$_2$,... 2b$_i$,...bn), et x$_i$ la solution produite par l'oracle de CVP$_γ$ pour B$^i$, alors il suffit de prendre comme solution de CVP$_γ$ le plus court vecteur de l'ensemble des {x$_i$ - b$_i$}.