Paper 2014/948

Lattice Point Enumeration on Block Reduced Bases

Michael Walter

Abstract

When analyzing lattice based cryptosystems, we often need to solve the Shortest Vector Problem (SVP) in some lattice associated to the system under scrutiny. The go-to algorithms in practice to solve SVP are enumeration algorithms, which usually consist of a preprocessing step, followed by an exhaustive search. Obviously, the two steps offer a trade-off and should be balanced in their running time in order to minimize the overall complexity. In practice, the most common approach to control this trade-off is to use block reduction algorithms during the preprocessing. Despite the popularity of this approach, it lacks any well founded analysis and all practical approaches seem to use ad hoc parameters. This weakens our confidence in the cryptanalysis of the systems. In this work, we aim to shed light on at least one side of this trade-off and analyze the effect of block reduction on the exhaustive search. For this, we give asymptotic worst case bounds and presents results from both experiments and simulation that show its average case behavior in practice.

Note: Minor fix in formulation of Theorem 1.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. ICITS 2015
Keywords
Lattice AlgorithmsShortest Vector ProblemEnumeration AlgorithmsBlock Reduction
Contact author(s)
miwalter @ eng ucsd edu
History
2015-12-23: last of 2 revisions
2014-11-19: received
See all versions
Short URL
https://ia.cr/2014/948
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/948,
      author = {Michael Walter},
      title = {Lattice Point Enumeration on Block Reduced Bases},
      howpublished = {Cryptology ePrint Archive, Paper 2014/948},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/948}},
      url = {https://eprint.iacr.org/2014/948}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.