Efficient (Ideal) lattice sieving using cross-polytope LSH

Anja Becker, Thijs Laarhoven

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

17 Citations (Scopus)

Abstract

Combining the efficient cross-polytope locality-sensitive hash family of Terasawa and Tanaka with the heuristic lattice sieve algorithm of Micciancio and Voulgaris, we show how to obtain heuristic and practical speedups for solving the shortest vector problem (SVP) on both arbitrary and ideal lattices. In both cases, the asymptotic time complexity for solving SVP in dimension n is 20.298n+o(n). For any lattice, hashes can be computed in polynomial time, which makes our CPSieve algorithm much more practical than the SphereSieve of Laarhoven and de Weger, while the better asymptotic complexities imply that this algorithm will outperform the GaussSieve of Micciancio and Voulgaris and the HashSieve of Laarhoven in moderate dimensions as well. We performed tests to show this improvement in practice. For ideal lattices, by observing that the hash of a shifted vector is a shift of the hash value of the original vector and constructing rerandomization matrices which preserve this property, we obtain not only a linear decrease in the space complexity, but also a linear speedup of the overall algorithm. We demonstrate the practicability of our cross-polytope ideal lattice sieve ICPSieve by applying the algorithm to cyclotomic ideal lattices from the ideal SVP challenge and to lattices which appear in the cryptanalysis of NTRU.

Original languageEnglish
Title of host publicationProgress in Cryptology – AFRICACRYPT 2016
Subtitle of host publication8th International Conference on Cryptology in Africa, Fes, Morocco, April 13-15, 2016, Proceedings
EditorsD. Pointcheval, A. Nitaj, T. Rachidi
Place of PublicationDordrecht
PublisherSpringer
Pages3-23
Number of pages21
ISBN (Electronic)978-3-319-31517-1
ISBN (Print)978-3-319-31516-4
DOIs
Publication statusPublished - 2016
Event8th International Conference on the Theory and Application of Cryptographic Techniques in Africa (Africacrypt 2016) - Fes, Morocco
Duration: 13 Apr 201615 Apr 2016
Conference number: 8

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9646
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th International Conference on the Theory and Application of Cryptographic Techniques in Africa (Africacrypt 2016)
Abbreviated titleAfricacrypt 2016
Country/TerritoryMorocco
CityFes
Period13/04/1615/04/16

Keywords

  • (Ideal) lattices
  • Locality-sensitive hashing
  • Shortest vector problem
  • Sieving algorithms

Fingerprint

Dive into the research topics of 'Efficient (Ideal) lattice sieving using cross-polytope LSH'. Together they form a unique fingerprint.

Cite this