Header

UZH-Logo

Maintenance Infos

PotLLL : a polynomial time version of LLL with deep insertions


Fontein, Felix; Schneider, Michael; Wagner, Urs (2014). PotLLL : a polynomial time version of LLL with deep insertions. Designs, Codes and Cryptography, 73(2):355-368.

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 PotLLL, 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.

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 PotLLL, 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.

Statistics

Citations

Dimensions.ai Metrics
6 citations in Web of Science®
7 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

16 downloads since deposited on 23 Jul 2019
16 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:National licences > 142-005
Dewey Decimal Classification:510 Mathematics
Uncontrolled Keywords:Applied Mathematics, Computer Science Applications
Language:English
Date:1 November 2014
Deposited On:23 Jul 2019 12:46
Last Modified:01 Nov 2019 01:01
Publisher:Springer
ISSN:0925-1022
OA Status:Green
Publisher DOI:https://doi.org/10.1007/s10623-014-9918-8
Related URLs:https://www.swissbib.ch/Search/Results?lookfor=nationallicencespringer101007s1062301499188 (Library Catalogue)

Download

Green Open Access

Download PDF  'PotLLL : a polynomial time version of LLL with deep insertions'.
Preview
Content: Published Version
Language: English
Filetype: PDF (Nationallizenz 142-005)
Size: 5MB
View at publisher