Practical, Predictable Lattice Basis Reduction

Daniele Micciancio; Michael Walter

Paper 2015/1123

Practical, Predictable Lattice Basis Reduction

Daniele Micciancio

, University of California, San Diego

Michael Walter

, University of California, San Diego

Abstract

Lattice reduction algorithms are notoriously hard to predict, both in terms of running time and output quality, which poses a major problem for cryptanalysis. While easy to analyze algorithms with good worst-case behavior exist, previous experimental evidence suggests that they are outperformed in practice by algorithms whose behavior is still not well understood, despite more than 30 years of intensive research. This has lead to a situation where a rather complex simulation procedure seems to be the most common way to predict the result of their application to an instance. In this work we present new algorithmic ideas towards bridging this gap between theory and practice. We report on an extensive experimental study of several lattice reduction algorithms, both novel and from the literature, that shows that theoretical algorithms are in fact surprisingly practical and competitive. In light of our results we come to the conclusion that in order to predict lattice reduction, simulation is superfluous and can be replaced by a closed formula using weaker assumptions. One key technique to achieving this goal is a novel algorithm to solve the Shortest Vector Problem (SVP) in the dual without computing the dual basis. Our algorithm enjoys the same practical efficiency as the corresponding primal algorithm and can be easily added to an existing implementation of it.

Note: Fixed typo in Corollary 2. Thanks to Eamonn Postlethwaite for pointing it out.

Metadata

Available format(s): PDF
Publication info: A minor revision of an IACR publication in EUROCRYPT 2016
Keywords: Lattice Reduction Enumeration Duality
Contact author(s): daniele @ cs ucsd edu
miwalter @ eng ucsd edu
History: 2022-08-22: last of 2 revisions; 2015-11-19: received; See all versions
Short URL: https://ia.cr/2015/1123
License: CC BY

BibTeX

@misc{cryptoeprint:2015/1123,
      author = {Daniele Micciancio and Michael Walter},
      title = {Practical, Predictable Lattice Basis Reduction},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/1123},
      year = {2015},
      url = {https://eprint.iacr.org/2015/1123}
}