A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths

DOI10.1007/s10623-019-00634-9zbMath1431.68084OpenAlexW2935879678MaRDI QIDQ2329392

Junpei Yamaguchi, Masaya Yasuda

Publication date: 17 October 2019

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

Full work available at URL: https://doi.org/10.1007/s10623-019-00634-9

zbMATH Keywords

lattice basis reductionLLL with deep insertionsshortest vector problem (SVP)shortest diagonal problem (SDP)

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Cryptography (94A60)

Related Items

Solving the search-LWE problem over projected lattices ⋮ Development and analysis of massive parallelization of a lattice basis reduction algorithm ⋮ Dynamic self-dual DeepBKZ lattice reduction with free dimensions and its implementation ⋮ Analysis of DeepBKZ reduction for finding short lattice vectors ⋮ A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge ⋮ A practical algorithm for completing half-Hadamard matrices using LLL

Uses Software

• NTL
• DeepLLL
• PotLLL
• BKZ

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• PotLLL: a polynomial time version of LLL with deep insertions
• Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors
• The LLL algorithm. Survey and applications
• On Lovász' lattice reduction and the nearest lattice point problem
• Factoring polynomials with rational coefficients
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Shortest vector from lattice sieving: a few dimensions for free
• Fast lattice basis reduction suitable for massive parallelization and its application to the shortest vector problem
• Explicit formula for Gram-Schmidt vectors in LLL with deep insertions and its applications
• Improved Progressive BKZ Algorithms and Their Precise Cost Estimation by Sharp Simulator
• Mathematics of Public Key Cryptography
• BKZ 2.0: Better Lattice Security Estimates
• On the equidistribution of Hecke points
• Analyzing Blockwise Lattice Algorithms Using Dynamical Systems
• Predicting Lattice Reduction
• Random Sampling Revisited: Lattice Enumeration with Discrete Pruning