Cryptology ePrint Archive: Report 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.

Category / Keywords: Lattice Algorithms, Shortest Vector Problem, Enumeration Algorithms, Block Reduction

Original Publication (in the same form): ICITS 2015

Date: received 18 Nov 2014, last revised 23 Dec 2015

Contact author: miwalter at eng ucsd edu

Available format(s): PDF | BibTeX Citation

Note: Minor fix in formulation of Theorem 1.

Version: 20151223:105705 (All versions of this report)

Short URL: ia.cr/2014/948

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]