PotLLL: a polynomial time version of LLL with deep insertions
From MaRDI portal
Publication:398939
DOI10.1007/S10623-014-9918-8zbMATH Open1297.94067arXiv1212.5100OpenAlexW2040347389MaRDI QIDQ398939FDOQ398939
Authors: Felix Fontein, Michael Schneider, Urs Wagner 
Publication date: 18 August 2014
Published in: Designs, Codes and Cryptography (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1212.5100
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
- BKZ 2.0: Better lattice security estimates
- Factoring polynomials with rational coefficients
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lattice-based Cryptography
- Predicting Lattice Reduction
- Floating-Point LLL Revisited
- The LLL algorithm. Survey and applications
- PotLLL: a polynomial time version of LLL with deep insertions
- Block Reduced Lattice Bases and Successive Minima
- Analyzing blockwise lattice algorithms using dynamical systems
- An LLL-reduction algorithm with quasi-linear time complexity, extended abstract
- Algorithmic Number Theory
Cited In (4)
- PotLLL: a polynomial time version of LLL with deep insertions
- Analysis of DeepBKZ reduction for finding short lattice vectors
- A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths
- Explicit formula for Gram-Schmidt vectors in LLL with deep insertions and its applications
Uses Software
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)
