PotLLL: a polynomial time version of LLL with deep insertions

DOI10.1007/S10623-014-9918-8MaRDI QIDQ398939zbMATH OpenOpenAlexFDO

Authors Felix Fontein, Michael Schneider, Urs Wagner

Publication date 18 August 2014

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.5100, https://www.zora.uzh.ch/id/eprint/171977/1/ZORA_NL_171977.pdf

zbMATH Keywords

LLL algorithmdeep insertionlattice reduction

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Cryptography (94A60)

Abstract: Lattice reduction algorithms have numerous applications in number theory, algebra, as well as in cryptanalysis. The most famous algorithm for lattice reduction is the LLL algorithm. In polynomial time it computes a reduced basis with provable output quality. One early improvement of the LLL algorithm was LLL with deep insertions (DeepLLL). The output of this version of LLL has higher quality in practice but the running time seems to explode. Weaker variants of DeepLLL, where the insertions are restricted to blocks, behave nicely in practice concerning the running time. However no proof of polynomial running time is known. In this paper a new variant of DeepLLL with provably polynomial running time is presented. We compare the practical behavior of the new algorithm to classical LLL, BKZ as well as blockwise variants of DeepLLL regarding both the output quality and running time.

Recommendations

• A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths
• Towards faster polynomial-time lattice reduction
• Fast LLL-type lattice reduction
• Progress on LLL and lattice reduction
• Explicit formula for Gram-Schmidt vectors in LLL with deep insertions and its applications

Cites work

• scientific article; zbMATH DE number 1859030 (Why is no real title available?)
• scientific article; zbMATH DE number 2120513 (Why is no real title available?)
• Algorithmic Number Theory
• An LLL-reduction algorithm with quasi-linear time complexity, extended abstract
• Analyzing blockwise lattice algorithms using dynamical systems
• BKZ 2.0: Better lattice security estimates
• Block Reduced Lattice Bases and Successive Minima
• Factoring polynomials with rational coefficients
• Floating-Point LLL Revisited
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Lattice-based Cryptography
• PotLLL: a polynomial time version of LLL with deep insertions
• Predicting Lattice Reduction
• The LLL algorithm. Survey and applications

Cited in

(4)

• Analysis of DeepBKZ reduction for finding short lattice vectors
• Explicit formula for Gram-Schmidt vectors in LLL with deep insertions and its applications
• PotLLL: a polynomial time version of LLL with deep insertions
• A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths

Describes a project that uses

Uses Software

• DeepLLL
• PotLLL
• BKZ

This page was built for publication: PotLLL: a polynomial time version of LLL with deep insertions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q398939)