Problème de réseau

Dans ce problème (abrégé en SVP pour shortest vector problem^[2]), 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:

${\displaystyle \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.

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

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^[6],[7],[8], et de réduction par échantillonnage aléatoire^[9],[10]; dans la deuxième, les méthodes de crible sur le réseau^{[11],[12],[13]}, le calcul des cellules de Voronoi sur le réseau^[14],[15], et l’échantillonnage Gaussien discret^[16].

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)^{[17],[18],[19]}, 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.

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

${\displaystyle 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 γ.

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}.

• Portail de l’informatique
• Portail de la cryptologie