Development and analysis of massive parallelization of a lattice basis reduction algorithm

DOI10.1007/S13160-023-00580-ZOpenAlexW4362581889MaRDI QIDQ6139332

Yuji Shinano, Katsuki Fujisawa, Shizuo Kaji, Masaya Yasuda, Nariaki Tateiwa, Keiichiro Yamamura

Publication date: 18 January 2024

Published in: Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s13160-023-00580-z

zbMATH Keywords

parallel computationlattice problemslattice basis reductionshortest vector problem (SVP)CMAP-LAP framework

Mathematics Subject Classification ID

General topics of discrete mathematics in relation to computer science (68R01) Lattices (06B99)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factoring polynomials with rational coefficients
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Progressive lattice sieving
• Shortest vector from lattice sieving: a few dimensions for free
• Second order statistical behavior of LLL and BKZ
• Fast lattice basis reduction suitable for massive parallelization and its application to the shortest vector problem
• Estimate all the {LWE, NTRU} schemes!
• Statistics on special manifolds
• Analysis of DeepBKZ reduction for finding short lattice vectors
• Advanced lattice sieving on GPUs, with tensor cores
• Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance
• 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
• A Tutorial on High Performance Computing Applied to Cryptanalysis
• BKZ 2.0: Better Lattice Security Estimates
• Parallel Shortest Lattice Vector Enumeration on Graphics Cards
• Lattice Enumeration Using Extreme Pruning
• Minkowski's Convex Body Theorem and Integer Programming
• The Geometry of Algorithms with Orthogonality Constraints
• New directions in nearest neighbor searching with applications to lattice sieving
• Bounds on packings of spheres in the Grassmann manifold
• The Ubiquity Generator Framework: 7 Years of Progress in Parallelizing Branch-and-Bound
• Numerical Methods for Computing Angles Between Linear Subspaces
• A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge
• Lattice Attacks on NTRU and LWE: A History of Refinements
• Hermite’s Constant and Lattice Algorithms
• Predicting Lattice Reduction
• Improved Algorithms for the Approximate k-List Problem in Euclidean Norm

This page was built for publication: Development and analysis of massive parallelization of a lattice basis reduction algorithm