Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
Identifieur interne : 000427 ( Istex/Curation ); précédent : 000426; suivant : 000428Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
Auteurs : Guillaume Hanrot [France] ; Damien Stehlé [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: The security of lattice-based cryptosystems such as NTRU, GGH and Ajtai-Dwork essentially relies upon the intractability of computing a shortest non-zero lattice vector and a closest lattice vector to a given target vector in high dimensions. The best algorithms for these tasks are due to Kannan, and, though remarkably simple, their complexity estimates have not been improved since over twenty years. Kannan’s algorithm for solving the shortest vector problem (SVP) is in particular crucial in Schnorr’s celebrated block reduction algorithm, on which rely the best known generic attacks against the lattice-based encryption schemes mentioned above. In this paper we improve the complexity upper-bounds of Kannan’s algorithms. The analysis provides new insight on the practical cost of solving SVP, and helps progressing towards providing meaningful key-sizes.
Url:
DOI: 10.1007/978-3-540-74143-5_10
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000430
Links to Exploration step
ISTEX:138ED4CA093BF8E8FAE8228623E874958705D7BFLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm</title><author><name sortKey="Hanrot, Guillaume" sort="Hanrot, Guillaume" uniqKey="Hanrot G" first="Guillaume" last="Hanrot">Guillaume Hanrot</name><affiliation wicri:level="1"><mods:affiliation>LORIA/INRIA Lorraine, Technopôle de Nancy-Brabois, 615 rue du jardin botanique, F-54602 Villers-lès-Nancy Cedex, France</mods:affiliation><country xml:lang="fr">France</country><wicri:regionArea>LORIA/INRIA Lorraine, Technopôle de Nancy-Brabois, 615 rue du jardin botanique, F-54602 Villers-lès-Nancy Cedex</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: hanrot@loria.fr</mods:affiliation><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name><affiliation wicri:level="1"><mods:affiliation>CNRS and ÉNS Lyon/ LIP, 46 allée d’Italie, 69364 Lyon Cedex 07, France</mods:affiliation><country xml:lang="fr">France</country><wicri:regionArea>CNRS and ÉNS Lyon/ LIP, 46 allée d’Italie, 69364 Lyon Cedex 07</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: damien.stehle@ens-lyon.fr</mods:affiliation><country wicri:rule="url">France</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:138ED4CA093BF8E8FAE8228623E874958705D7BF</idno><date when="2007" year="2007">2007</date><idno type="doi">10.1007/978-3-540-74143-5_10</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-NSCRDJW3-Z/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000430</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000430</idno><idno type="wicri:Area/Istex/Curation">000427</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm</title><author><name sortKey="Hanrot, Guillaume" sort="Hanrot, Guillaume" uniqKey="Hanrot G" first="Guillaume" last="Hanrot">Guillaume Hanrot</name><affiliation wicri:level="1"><mods:affiliation>LORIA/INRIA Lorraine, Technopôle de Nancy-Brabois, 615 rue du jardin botanique, F-54602 Villers-lès-Nancy Cedex, France</mods:affiliation><country xml:lang="fr">France</country><wicri:regionArea>LORIA/INRIA Lorraine, Technopôle de Nancy-Brabois, 615 rue du jardin botanique, F-54602 Villers-lès-Nancy Cedex</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: hanrot@loria.fr</mods:affiliation><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name><affiliation wicri:level="1"><mods:affiliation>CNRS and ÉNS Lyon/ LIP, 46 allée d’Italie, 69364 Lyon Cedex 07, France</mods:affiliation><country xml:lang="fr">France</country><wicri:regionArea>CNRS and ÉNS Lyon/ LIP, 46 allée d’Italie, 69364 Lyon Cedex 07</wicri:regionArea></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: damien.stehle@ens-lyon.fr</mods:affiliation><country wicri:rule="url">France</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: The security of lattice-based cryptosystems such as NTRU, GGH and Ajtai-Dwork essentially relies upon the intractability of computing a shortest non-zero lattice vector and a closest lattice vector to a given target vector in high dimensions. The best algorithms for these tasks are due to Kannan, and, though remarkably simple, their complexity estimates have not been improved since over twenty years. Kannan’s algorithm for solving the shortest vector problem (SVP) is in particular crucial in Schnorr’s celebrated block reduction algorithm, on which rely the best known generic attacks against the lattice-based encryption schemes mentioned above. In this paper we improve the complexity upper-bounds of Kannan’s algorithms. The analysis provides new insight on the practical cost of solving SVP, and helps progressing towards providing meaningful key-sizes.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000427 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 000427 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Curation
|type= RBID
|clé= ISTEX:138ED4CA093BF8E8FAE8228623E874958705D7BF
|texte= Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
}}
| This area was generated with Dilib version V0.6.33. |  |