Analysis of DeepBKZ reduction for finding short lattice vectors

DOI10.1007/s10623-020-00765-4zbMath1465.11236OpenAlexW3032909056MaRDI QIDQ2004968

Junpei Yamaguchi, Satoshi Nakamura, Masaya Yasuda

Publication date: 7 October 2020

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

Full work available at URL: https://doi.org/10.1007/s10623-020-00765-4

zbMATH Keywords

BKZSVPlattice basis reductiondeep insertions

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) General topics of discrete mathematics in relation to computer science (68R01) Number-theoretic algorithms; complexity (11Y16)

Related Items (3)

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

Uses Software

• NTL
• DeepLLL
• PotLLL
• BKZ
• fpLLL
• GitHub
• G6K

Cites Work

• Unnamed Item
• 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
• A modification of the LLL reduction algorithm
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• G6K
• Shortest vector from lattice sieving: a few dimensions for free
• Development of a dual version of DeepBKZ and its application to solving the LWE challenge
• Estimate all the {LWE, NTRU} schemes!
• Self-dual DeepBKZ for finding short lattice vectors
• The general sieve kernel and new records in lattice reduction
• 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
• Improved Progressive BKZ Algorithms and Their Precise Cost Estimation by Sharp Simulator
• Practical, Predictable Lattice Basis Reduction
• Mathematics of Public Key Cryptography
• BKZ 2.0: Better Lattice Security Estimates
• Lattice Enumeration Using Extreme Pruning
• Hermite’s Constant and Lattice Algorithms
• Analyzing Blockwise Lattice Algorithms Using Dynamical Systems
• Predicting Lattice Reduction

This page was built for publication: Analysis of DeepBKZ reduction for finding short lattice vectors