SVP (Short Vector Problem) et de CVP (Closest Vector Problem) : ces deux problèmes sur les réseaux ayant n − 1 cycles non triviaux sont aussi difficiles que
| Previous PDF | Next PDF |
[PDF] RÉSOUDRE UN PROBLEME AVEC SVP
INITIATIVES SYNDICALES 62 RÉSOUDRE UN PROBLEME AVEC SVP Sans avoir la prétention de résoudre ce type de problèmes dont les raisons sont
[PDF] rapport
SVP (Short Vector Problem) et de CVP (Closest Vector Problem) : ces deux problèmes sur les réseaux ayant n − 1 cycles non triviaux sont aussi difficiles que
[PDF] Lattices with many cycles are dense - Prosecco
SVP (Short Vector Problem) et de CVP (Closest Vector Problem) : ces deux problèmes sur les réseaux ayant n − 1 cycles non triviaux sont aussi difficiles que
[PDF] Introduction à la Sécurité Prouvée en Cryptographie à Clés
2 Problème di ciles, Fonctions à sens unique et Fonction de hachage 15 2 4 Problèmes SVP et CVP dans les Réseaux arithmétiques 24
[PDF] R[Pleaseinsert\ ぐrerenderUnicode{é}intopreamble]seaux
Montrer que le problème CVP (décision) est NP-dur, en considérant le vecteur Le calcul du plus court vecteur (SVP pour shortest vector problem) est une
[PDF] Tournez la page SVP Les calculatrices sont autorisées **** NB :Le
Trois exemples et une application concluent le problème, partie III Les parties II et III sont indépendantes et pourront être traitées dans un ordre arbitraire
[PDF] Tournez la page SVP 5 THERMODYNAMIQUE Lobjectif de ce
Tournez la page S V P 5 THERMODYNAMIQUE L'objectif de ce problème est l' étude du fonctionnement stationnaire d'une machine ditherme de réfrigération
[PDF] Tournez svp - LIMOS
Donner un algorithme de programmation dynamique pour résoudre le problème suivant : Entrée : une matrice A de taille n × m où les coefficients valent 0 ou 1
[PDF] Algorithms for the Shortest and Closest Lattice Vector Problems
optimization problems admit simple geometric interpretations: SVP con- sists in finding a shortest non-zero vector in the Euclidean lattice L[B] := ∑i≤n xibi
[PDF] Probleme Physique 2019
Tournez la page S V P MINISTÈRE dans des nano-pistes Le problème proposé est une exploration de mécanismes de retournement d'aimantation à travers
[PDF] le problème compliqué
[PDF] Le Problème d'Abraham Ben Erza
[PDF] Le problème d'eau : un enjeu majeur
[PDF] le problème d'infiltration cinema
[PDF] le problème d'infiltration critique
[PDF] le problème d'infiltration film critique
[PDF] le problème d'infiltration horaire
[PDF] Le probleme de Géraldine
[PDF] LE PROBLEME DE L EAU A ALGER A LA FIN DU 20éme siècle
[PDF] le probleme de l'eau
[PDF] Le probleme de la chèvre
[PDF] Le problème du canadair
[PDF] le problème du duc de toscane arbre
[PDF] le problème du fil de fer
Lattices with many cycles are dense
MårtenTrolin
2004Master d"Informatique Fondamentale Réseaux euclidiens
École Normale Supérieure de LyonChantalKELLERDans cet article, Mårten Trolin présente un résultat négatif concernant la complexité de
SVP (Short Vector Problem) et de CVP (Closest Vector Problem) : ces deux problèmes surles réseaux ayantn1cycles non triviaux sont aussi difficiles que sur des réseaux en général.
Pour cela, il montre en premier lieu la densité des réseaux àn1cycles dans les réseaux, puis
réduit SVP et CVP sur un réseau quelconque au même problème sur un réseau àn1cycles
en n"effectuant que des transformations polynomiales en temps, ce qui permet d"affirmer que ces deux problèmes sur des réseaux àn1cycles sontNP-difficiles.Nous allons présenter ici l"idée de l"algorithme de Trolin pour montrer la densité des réseaux
àn1cycles, en expliquant comment le mettre en pratique efficacement. Nous verrons ensuitecomment réduire CVP sur un réseau quelconque à CVP sur un réseau àn1cycles, le procédé
étant identique pour SVP. Enfin, nous reviendrons sur des cas particuliers d"utilisation des réseaux cycliques.1 Densité des réseaux àn1cycles
1.1 Problème
On montre que l"on peut approcher tout réseau quelconque par un réseau àn1cycles non triviaux (et de même longueur, dans l"algorithme de Trolin) arbitrairement proche. Pour cela, on se donne un réseau quelconqueZndonné par une matriceBdes vecteurs de base, et >0. On cherche à approcherpar un réseau àn1cycles d"un facteuren norme : on construit une fonction;tel que;()est un réseau àn1cycles et;étendu aux vecteurs vérifie :
8u2Zn;ku;(u)k6kuk
1.2 Algorithme de Trolin
La fonction;est définie par l"application de l"algorithme suivant, prenantBen entrée et renvoyantB0base d"un réseau àn1cycles arbitrairement proche deB:1. MettreBsous forme normale de Hermite (HNF).
2. Transformer la matrice obtenue pour avoir une HNF plus simple (voir annexe A).
3. Appliquer LLL avec=34
sur lesn1premiers vecteurs pour obtenir(B). 14. Factoriser(B)en le produit deD=0
BBBB@1 0:::0
0 ......1 00:::0det(B)1
CCCCAet une matrice unimo-
dulaireE.5. TransformerDen une matriceD0engendrant un réseau àn1cycles de même longueur
(det(B))n1.6. PoserB0=D0E.
Remarques :
1. L"étape 1 de l"algorithme peut être réalisée en temps et en espace bornés par des poly-
nômes en la longueur des données d"entrée d"après [1].2. En utilisant leTheorem 1de l"article, on en déduit qu"après l"étape 6 de l"algorithme,
le réseau engendré parB0a bienn1cycles, carEest unimodulaire.1.3 Application à un vecteur
On étend;aux vecteurs ainsi : aux étapes 2 et 5, on définit respectivement les trans- formations2et5surB. On note(bi)i2J1;nKles lignes deB.Siu=nX
i=1t ibi, pour2 f2;5g, on définit(u) =nX i=1t ib0ioùb0iest laièmeligne de(B). On note;(u) =52(u)pour tout vecteuru2Zn. On a alors :8u2Zn;ku;(u)k6kuk
2 Application à SVP et CVP
D"après leLemma 10, on peut effectuer une réduction d"une instance de CVP sur un réseau quelconque à une instance de CVP sur un réseau àn1cycles, réduction qui est polynomiale en la taille des données. Comme CVP estNP-difficile [2], on en déduit que CVP sur les matrices àn1cycles est égalementNP-difficile. On a le même résultat pour SVP, qui estNP-difficile pour une matrice àn1cycles, comme pour une matrice quelconque [3].3 Remarques et perspectives
D"après l"article, de nombreuses applications se ramènent à des problèmes sur des réseaux
possédant certaines propriétés, comme des réseaux cycliques (malheureusement, aucune n"est
citée). C"est une des raisons pour lesquelles l"étude de réseaux particuliers peut être inté-
ressante. Cependant, comme présenté dans l"article, même ces propriétés sur les réseaux ne
suffisent pas à rendre les problèmes classiques plus simples.D"après [4], et en particulier :
every matrix reduces to a unique matrix in reduced row echelon form by elementary row operations 2 et leTheorem 1, tout réseau de dimensionnsurZnest cyclique, ce qui apporte un intérêt nouvel à l"étude de ces réseaux. Avec les précédents résultats, on sait maintenant que pour les réseaux ayant 1,n1ou n=c2Ncycles, SVP et CVP sont aussi difficiles que pour les réseaux en général. De plus, pour les réseaux ayant au moinsncycles, on peut se ramener àkcycles, pourk2J1;n1K. Il manque donc encore un résultat similaire sur les réseaux àk2J2;n2K; k6=n=ccyclespour pouvoir conclure sur tous les réseaux cycliques. Cependant, d"après Trolin, ce résultat
n"est pas directement généralisable à partir des preuves déjà existantes pour les autres réseaux
cycliques, et reste donc un problème ouvert. ConclusionLes réseaux àn1cycles sont denses dans l"ensemble des réseaux. Trolin entire un résultat qui peut être négatif : laNP-difficulté de SVP et de CVP pour ces réseaux.
Cependant, on peut remarquer que ce résultat a également un côté positif : la difficulté du
problème le rend intéressant pour des applications en cryptographie, par exemple pour définir
des systèmes de cryptage qui seronta prioriplus difficiles à casser que ceux décrits dans [5].
De plus, on se restreint ici à SVP et CVP, mais la densité de certaines matrices cycliqueset le fait que l"algorithme de Trolin présenté ici soit constructif pourraient servir à résoudre
d"autres problèmes.Références
[1] R.Kannanet A.Bachem: Polynomial algorithms for computing of the Smith and Hermite normal forms of an integer matrix.SIAM Journal of computing, pages 499-507, 1979.[2] I.Dinur, G.Kindler, S.Safraet R.Raz: Approximating CVP to within almost- polynomial factors is NP-hard.Combinatorica, pages 205-243, 2003. [3] D.Micciancio: The shortest vector in a lattice is hard to approximate within some constant.SIAM Journal of computing, pages 2008-2035, 2001. [4] Reduced row echelon form.http://en.wikipedia.org/wiki/Hermite_normal_form. [5] J.Hoffstein, J.Pipheret J.H.Silverman: NTRU : a ring based public key crypto- system.Proc. of ANTS III, pages 267-288, 1998. [6] M.Trolin: Lattices with many cycles are dense.Electronic Colloquium on Computational
Complexity, 2004.
Note :Pour les références [1, 5], n"ayant pu trouver l"article, seul l"abstract a été lu.
3