Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
Identifieur interne : 000430 ( Istex/Corpus ); précédent : 000429; suivant : 000431Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
Auteurs : Guillaume Hanrot ; Damien Stehlé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 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><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></affiliation><affiliation><mods:affiliation>E-mail: hanrot@loria.fr</mods:affiliation></affiliation></author><author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name><affiliation><mods:affiliation>CNRS and ÉNS Lyon/ LIP, 46 allée d’Italie, 69364 Lyon Cedex 07, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: damien.stehle@ens-lyon.fr</mods:affiliation></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></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><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></affiliation><affiliation><mods:affiliation>E-mail: hanrot@loria.fr</mods:affiliation></affiliation></author><author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name><affiliation><mods:affiliation>CNRS and ÉNS Lyon/ LIP, 46 allée d’Italie, 69364 Lyon Cedex 07, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: damien.stehle@ens-lyon.fr</mods:affiliation></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><istex><corpusName>springer-ebooks</corpusName><author><json:item><name>Guillaume Hanrot</name><affiliations><json:string>LORIA/INRIA Lorraine, Technopôle de Nancy-Brabois, 615 rue du jardin botanique, F-54602 Villers-lès-Nancy Cedex, France</json:string><json:string>E-mail: hanrot@loria.fr</json:string></affiliations></json:item><json:item><name>Damien Stehlé</name><affiliations><json:string>CNRS and ÉNS Lyon/ LIP, 46 allée d’Italie, 69364 Lyon Cedex 07, France</json:string><json:string>E-mail: damien.stehle@ens-lyon.fr</json:string></affiliations></json:item></author><arkIstex>ark:/67375/HCB-NSCRDJW3-Z</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><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.</abstract><qualityIndicators><refBibsNative>false</refBibsNative><abstractWordCount>125</abstractWordCount><abstractCharCount>872</abstractCharCount><keywordCount>0</keywordCount><score>8.5</score><pdfWordCount>7023</pdfWordCount><pdfCharCount>34416</pdfCharCount><pdfVersion>1.6</pdfVersion><pdfPageCount>17</pdfPageCount><pdfPageSize>430 x 660 pts</pdfPageSize></qualityIndicators><title>Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm</title><chapterId><json:string>10</json:string><json:string>Chap10</json:string></chapterId><genre><json:string>conference</json:string></genre><serie><title>Lecture Notes in Computer Science</title><language><json:string>unknown</json:string></language><copyrightDate>2007</copyrightDate><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn><volume>V</volume><editor><json:item><name>David Hutchison</name></json:item><json:item><name>Takeo Kanade</name></json:item><json:item><name>Josef Kittler</name></json:item><json:item><name>Jon M. Kleinberg</name></json:item><json:item><name>Friedemann Mattern</name></json:item><json:item><name>John C. Mitchell</name></json:item><json:item><name>Moni Naor</name></json:item><json:item><name>Oscar Nierstrasz</name></json:item><json:item><name>C. Pandu Rangan</name></json:item><json:item><name>Bernhard Steffen</name></json:item><json:item><name>Madhu Sudan</name></json:item><json:item><name>Demetri Terzopoulos</name></json:item><json:item><name>Doug Tygar</name></json:item><json:item><name>Moshe Y. Vardi</name></json:item><json:item><name>Gerhard Weikum</name></json:item></editor></serie><host><title>Advances in Cryptology - CRYPTO 2007</title><language><json:string>unknown</json:string></language><copyrightDate>2007</copyrightDate><doi><json:string>10.1007/978-3-540-74143-5</json:string></doi><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn><eisbn><json:string>978-3-540-74143-5</json:string></eisbn><bookId><json:string>978-3-540-74143-5</json:string></bookId><isbn><json:string>978-3-540-74142-8</json:string></isbn><volume>4622</volume><pages><first>170</first><last>186</last></pages><genre><json:string>book-series</json:string></genre><editor><json:item><name>Alfred Menezes</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Data Encryption</value></json:item><json:item><value>Management of Computing and Information Systems</value></json:item><json:item><value>Computer Communication Networks</value></json:item><json:item><value>Systems and Data Security</value></json:item><json:item><value>Computers and Society</value></json:item><json:item><value>Discrete Mathematics in Computer Science</value></json:item></subject></host><ark><json:string>ark:/67375/HCB-NSCRDJW3-Z</json:string></ark><publicationDate>2007</publicationDate><copyrightDate>2007</copyrightDate><doi><json:string>10.1007/978-3-540-74143-5_10</json:string></doi><id>138ED4CA093BF8E8FAE8228623E874958705D7BF</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-NSCRDJW3-Z/fulltext.pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-NSCRDJW3-Z/bundle.zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/HCB-NSCRDJW3-Z/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm</title></titleStmt><publicationStmt><authority>ISTEX</authority><availability><licence>Springer-Verlag Berlin Heidelberg</licence></availability><date when="2007">2007</date></publicationStmt><notesStmt><note type="conference" source="proceedings" scheme="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</note><note type="publication-type" subtype="book-series" scheme="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</note></notesStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm</title><author><persName><forename type="first">Guillaume</forename><surname>Hanrot</surname></persName><email>hanrot@loria.fr</email><affiliation><orgName type="institution">LORIA/INRIA Lorraine, Technopôle de Nancy-Brabois, 615 rue du jardin botanique, F-54602 Villers-lès-Nancy Cedex</orgName><address><country key="FR">FRANCE</country></address></affiliation></author><author><persName><forename type="first">Damien</forename><surname>Stehlé</surname></persName><email>damien.stehle@ens-lyon.fr</email><affiliation><orgName type="institution">CNRS and ÉNS Lyon/ LIP, 46 allée d’Italie, 69364 Lyon Cedex 07</orgName><address><country key="FR">FRANCE</country></address></affiliation></author><idno type="istex">138ED4CA093BF8E8FAE8228623E874958705D7BF</idno><idno type="ark">ark:/67375/HCB-NSCRDJW3-Z</idno><idno type="DOI">10.1007/978-3-540-74143-5_10</idno></analytic><monogr><title level="m" type="main">Advances in Cryptology - CRYPTO 2007</title><title level="m" type="sub">27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007. Proceedings</title><title level="m" type="part">Lattices</title><idno type="DOI">10.1007/978-3-540-74143-5</idno><idno type="book-id">978-3-540-74143-5</idno><idno type="ISBN">978-3-540-74142-8</idno><idno type="eISBN">978-3-540-74143-5</idno><idno type="chapter-id">Chap10</idno><idno type="part-id">Part5</idno><editor><persName><forename type="first">Alfred</forename><surname>Menezes</surname></persName><email>ajmeneze@uwaterloo.ca</email></editor><imprint><biblScope unit="vol">4622</biblScope><biblScope unit="page" from="170">170</biblScope><biblScope unit="page" to="186">186</biblScope><biblScope unit="chapter-count">34</biblScope><biblScope unit="part-chapter-count">2</biblScope></imprint></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><editor><persName><forename type="first">David</forename><surname>Hutchison</surname></persName></editor><editor><persName><forename type="first">Takeo</forename><surname>Kanade</surname></persName></editor><editor><persName><forename type="first">Josef</forename><surname>Kittler</surname></persName></editor><editor><persName><forename type="first">Jon</forename><forename type="first">M.</forename><surname>Kleinberg</surname></persName></editor><editor><persName><forename type="first">Friedemann</forename><surname>Mattern</surname></persName></editor><editor><persName><forename type="first">John</forename><forename type="first">C.</forename><surname>Mitchell</surname></persName></editor><editor><persName><forename type="first">Moni</forename><surname>Naor</surname></persName></editor><editor><persName><forename type="first">Oscar</forename><surname>Nierstrasz</surname></persName></editor><editor><persName><forename type="first">C.</forename><surname>Pandu Rangan</surname></persName></editor><editor><persName><forename type="first">Bernhard</forename><surname>Steffen</surname></persName></editor><editor><persName><forename type="first">Madhu</forename><surname>Sudan</surname></persName></editor><editor><persName><forename type="first">Demetri</forename><surname>Terzopoulos</surname></persName></editor><editor><persName><forename type="first">Doug</forename><surname>Tygar</surname></persName></editor><editor><persName><forename type="first">Moshe</forename><forename type="first">Y.</forename><surname>Vardi</surname></persName></editor><editor><persName><forename type="first">Gerhard</forename><surname>Weikum</surname></persName></editor><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="seriesID">558</idno></series></biblStruct></sourceDesc></fileDesc><profileDesc><abstract xml:lang="en"><head>Abstract</head><p>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.</p></abstract><textClass ana="subject"><keywords scheme="book-subject-collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass ana="subject"><keywords scheme="book-subject"><list><label>I</label><item><term type="Primary">Computer Science</term></item><label>I15033</label><item><term type="Secondary" subtype="priority-1">Data Encryption</term></item><label>I24067</label><item><term type="Secondary" subtype="priority-2">Management of Computing and Information Systems</term></item><label>I13022</label><item><term type="Secondary" subtype="priority-3">Computer Communication Networks</term></item><label>I14050</label><item><term type="Secondary" subtype="priority-4">Systems and Data Security</term></item><label>I24040</label><item><term type="Secondary" subtype="priority-5">Computers and Society</term></item><label>I17028</label><item><term type="Secondary" subtype="priority-6">Discrete Mathematics in Computer Science</term></item></list></keywords></textClass><langUsage><language ident="EN"></language></langUsage></profileDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-NSCRDJW3-Z/fulltext.txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="corpus springer-ebooks not found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>David</GivenName><FamilyName>Hutchison</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Takeo</GivenName><FamilyName>Kanade</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Josef</GivenName><FamilyName>Kittler</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Jon</GivenName><GivenName>M.</GivenName><FamilyName>Kleinberg</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Friedemann</GivenName><FamilyName>Mattern</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>John</GivenName><GivenName>C.</GivenName><FamilyName>Mitchell</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Moni</GivenName><FamilyName>Naor</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Oscar</GivenName><FamilyName>Nierstrasz</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>C.</GivenName><FamilyName>Pandu Rangan</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Bernhard</GivenName><FamilyName>Steffen</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Madhu</GivenName><FamilyName>Sudan</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Demetri</GivenName><FamilyName>Terzopoulos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Doug</GivenName><FamilyName>Tygar</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Moshe</GivenName><GivenName>Y.</GivenName><FamilyName>Vardi</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Weikum</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingStyle="Unnumbered" OutputMedium="All" TocLevels="0"><BookID>978-3-540-74143-5</BookID><BookTitle>Advances in Cryptology - CRYPTO 2007</BookTitle><BookSubTitle>27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007. Proceedings</BookSubTitle><BookVolumeNumber>4622</BookVolumeNumber><BookSequenceNumber>4622</BookSequenceNumber><BookDOI>10.1007/978-3-540-74143-5</BookDOI><BookTitleID>151816</BookTitleID><BookPrintISBN>978-3-540-74142-8</BookPrintISBN><BookElectronicISBN>978-3-540-74143-5</BookElectronicISBN><BookChapterCount>34</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2007</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I15033" Priority="1" Type="Secondary">Data Encryption</BookSubject><BookSubject Code="I24067" Priority="2" Type="Secondary">Management of Computing and Information Systems</BookSubject><BookSubject Code="I13022" Priority="3" Type="Secondary">Computer Communication Networks</BookSubject><BookSubject Code="I14050" Priority="4" Type="Secondary">Systems and Data Security</BookSubject><BookSubject Code="I24040" Priority="5" Type="Secondary">Computers and Society</BookSubject><BookSubject Code="I17028" Priority="6" Type="Secondary">Discrete Mathematics in Computer Science</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Alfred</GivenName><FamilyName>Menezes</FamilyName></EditorName><Contact><Email>ajmeneze@uwaterloo.ca</Email></Contact></Editor></EditorGroup></BookHeader><Part ID="Part5"><PartInfo TocLevels="0"><PartID>5</PartID><PartNumber>V</PartNumber><PartSequenceNumber>5</PartSequenceNumber><PartTitle>Lattices</PartTitle><PartChapterCount>2</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookTitle>Advances in Cryptology - CRYPTO 2007</BookTitle></PartContext></PartInfo><Chapter ID="Chap10" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingStyle="Unnumbered" TocLevels="0"><ChapterID>10</ChapterID><ChapterDOI>10.1007/978-3-540-74143-5_10</ChapterDOI><ChapterSequenceNumber>10</ChapterSequenceNumber><ChapterTitle Language="En">Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm</ChapterTitle><ChapterSubTitle Language="En">(Extended Abstract)</ChapterSubTitle><ChapterFirstPage>170</ChapterFirstPage><ChapterLastPage>186</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2007</CopyrightYear></ChapterCopyright><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><PartID>5</PartID><BookID>978-3-540-74143-5</BookID><BookTitle>Advances in Cryptology - CRYPTO 2007</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Guillaume</GivenName><FamilyName>Hanrot</FamilyName></AuthorName><Contact><Email>hanrot@loria.fr</Email><URL>http://www.loria.fr/~hanrot</URL></Contact></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>Damien</GivenName><FamilyName>Stehlé</FamilyName></AuthorName><Contact><Email>damien.stehle@ens-lyon.fr</Email><URL>http://perso.ens-lyon.fr/damien.stehle</URL></Contact></Author><Affiliation ID="Aff1"><OrgName>LORIA/INRIA Lorraine, Technopôle de Nancy-Brabois, 615 rue du jardin botanique, F-54602 Villers-lès-Nancy Cedex</OrgName><OrgAddress><Country>France</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>CNRS and ÉNS Lyon/ LIP, 46 allée d’Italie, 69364 Lyon Cedex 07</OrgName><OrgAddress><Country>France</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>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.</Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></Part></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm</title><subTitle>(Extended Abstract)</subTitle></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm</title></titleInfo><name type="personal"><namePart type="given">Guillaume</namePart><namePart type="family">Hanrot</namePart><affiliation>LORIA/INRIA Lorraine, Technopôle de Nancy-Brabois, 615 rue du jardin botanique, F-54602 Villers-lès-Nancy Cedex, France</affiliation><affiliation>E-mail: hanrot@loria.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Damien</namePart><namePart type="family">Stehlé</namePart><affiliation>CNRS and ÉNS Lyon/ LIP, 46 allée d’Italie, 69364 Lyon Cedex 07, France</affiliation><affiliation>E-mail: damien.stehle@ens-lyon.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre displayLabel="OriginalPaper" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" type="conference" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2007</dateIssued><copyrightDate encoding="w3cdtf">2007</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><abstract 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.</abstract><relatedItem type="host"><titleInfo><title>Advances in Cryptology - CRYPTO 2007</title><subTitle>27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007. Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Alfred</namePart><namePart type="family">Menezes</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</genre><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">2007</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I15033">Data Encryption</topic><topic authority="SpringerSubjectCodes" authorityURI="I24067">Management of Computing and Information Systems</topic><topic authority="SpringerSubjectCodes" authorityURI="I13022">Computer Communication Networks</topic><topic authority="SpringerSubjectCodes" authorityURI="I14050">Systems and Data Security</topic><topic authority="SpringerSubjectCodes" authorityURI="I24040">Computers and Society</topic><topic authority="SpringerSubjectCodes" authorityURI="I17028">Discrete Mathematics in Computer Science</topic></subject><identifier type="DOI">10.1007/978-3-540-74143-5</identifier><identifier type="ISBN">978-3-540-74142-8</identifier><identifier type="eISBN">978-3-540-74143-5</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">151816</identifier><identifier type="BookID">978-3-540-74143-5</identifier><identifier type="BookChapterCount">34</identifier><identifier type="BookVolumeNumber">4622</identifier><identifier type="BookSequenceNumber">4622</identifier><identifier type="PartChapterCount">2</identifier><part><date>2007</date><detail type="part"><title>V: Lattices</title></detail><detail type="volume"><number>4622</number><caption>vol.</caption></detail><extent unit="pages"><start>170</start><end>186</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2007</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">David</namePart><namePart type="family">Hutchison</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Takeo</namePart><namePart type="family">Kanade</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Josef</namePart><namePart type="family">Kittler</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jon</namePart><namePart type="given">M.</namePart><namePart type="family">Kleinberg</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Friedemann</namePart><namePart type="family">Mattern</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">John</namePart><namePart type="given">C.</namePart><namePart type="family">Mitchell</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moni</namePart><namePart type="family">Naor</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Oscar</namePart><namePart type="family">Nierstrasz</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Pandu Rangan</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Bernhard</namePart><namePart type="family">Steffen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Madhu</namePart><namePart type="family">Sudan</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Demetri</namePart><namePart type="family">Terzopoulos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Doug</namePart><namePart type="family">Tygar</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moshe</namePart><namePart type="given">Y.</namePart><namePart type="family">Vardi</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Weikum</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">2007</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><part><detail type="volume"><number>V</number><caption>vol.</caption></detail></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2007</recordOrigin></recordInfo></relatedItem><identifier type="istex">138ED4CA093BF8E8FAE8228623E874958705D7BF</identifier><identifier type="ark">ark:/67375/HCB-NSCRDJW3-Z</identifier><identifier type="DOI">10.1007/978-3-540-74143-5_10</identifier><identifier type="ChapterID">10</identifier><identifier type="ChapterID">Chap10</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2007</accessCondition><recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-RLRX46XW-4">springer</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2007</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-NSCRDJW3-Z/record.json</uri></json:item></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000430 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000430 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Corpus
|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. |  |