Problème de réseau

Modèle:Ébauche Modèle:Orphelin 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², 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

Problème du plus court vecteur : étant donnés les vecteurs de base (en bleu), et le réseau engendré, on recherche le plus court vecteur possible (en rouge).

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 =\underset{v\in \mathrm{\Lambda }\setminus \{\mathrm{𝟎}\}}{\min }\Vert v{\Vert }_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éatoiresModèle:,. 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éseauxModèle:,Modèle:,, et de réduction par échantillonnage aléatoireModèle:,; dans la deuxième, les méthodes de crible sur le réseauModèle:,Modèle:,, le calcul des cellules de Voronoi sur le réseauModèle:,, 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 Modèle:Lien. 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)Modèle:,Modèle:,, 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

Problème du plus proche vecteur : étant donnés une base (en bleu) et le réseau engendré, et un vecteur quelconque (en vert), on cherche le vecteur le plus proche appartenant au réseau (en rouge)

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 \underset{x\in \mathrm{\Lambda }}{\min }\Vert 𝐯-x{\Vert }_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₁, b₂,... b_n) la base donnée pour le problème SVP. Alors On considère la base Bⁱ = (b₁, b₂,... 2b_i,...bn), et x_i la solution produite par l'oracle de CVP_γ pour Bⁱ, alors il suffit de prendre comme solution de CVP_γ le plus court vecteur de l'ensemble des {x_i - b_i}.