Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
Identifieur interne : 004C44 ( Main/Exploration ); précédent : 004C43; suivant : 004C45Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
Auteurs : Guillaume Hanrot [France] ; Damien Stehlé [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
English descriptors
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
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000430
- to stream Istex, to step Curation: 000427
- to stream Istex, to step Checkpoint: 001029
- to stream Hal, to step Corpus: 002987
- to stream Hal, to step Curation: 002987
- to stream Hal, to step Checkpoint: 003921
- to stream Main, to step Merge: 004D78
- to stream Main, to step Curation: 004C44
Le 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></author><author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name></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><idno type="wicri:Area/Istex/Checkpoint">001029</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001029</idno><idno type="wicri:doubleKey">0302-9743:2007:Hanrot G:improved:analysis:of</idno><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00145049</idno><idno type="url">https://hal.inria.fr/inria-00145049</idno><idno type="wicri:Area/Hal/Corpus">002987</idno><idno type="wicri:Area/Hal/Curation">002987</idno><idno type="wicri:Area/Hal/Checkpoint">003921</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">003921</idno><idno type="wicri:Area/Main/Merge">004D78</idno><idno type="wicri:Area/Main/Curation">004C44</idno><idno type="wicri:Area/Main/Exploration">004C44</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="3"><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><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Villers-lès-Nancy</settlement></placeName></affiliation><affiliation wicri:level="1"><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="3"><country xml:lang="fr">France</country><wicri:regionArea>CNRS and ÉNS Lyon/ LIP, 46 allée d’Italie, 69364 Lyon Cedex 07</wicri:regionArea><placeName><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region><settlement type="city">Lyon</settlement></placeName></affiliation><affiliation wicri:level="1"><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><keywords scheme="mix" xml:lang="en"><term>Lattice reduction</term><term>complexity analysis</term><term>lattice-based cryptosystems</term></keywords></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><affiliations><list><country><li>France</li></country><region><li>Auvergne-Rhône-Alpes</li><li>Grand Est</li><li>Lorraine (région)</li><li>Rhône-Alpes</li></region><settlement><li>Lyon</li><li>Villers-lès-Nancy</li></settlement></list><tree><country name="France"><region name="Grand Est"><name sortKey="Hanrot, Guillaume" sort="Hanrot, Guillaume" uniqKey="Hanrot G" first="Guillaume" last="Hanrot">Guillaume Hanrot</name></region><name sortKey="Hanrot, Guillaume" sort="Hanrot, Guillaume" uniqKey="Hanrot G" first="Guillaume" last="Hanrot">Guillaume Hanrot</name><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004C44 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 004C44 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|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. |  |