Solving the search-LWE problem over projected lattices

DOI10.1016/j.dam.2022.04.018zbMath1491.94060OpenAlexW4281964710MaRDI QIDQ2146741

Nariaki Tateiwa, Masaya Yasuda, Katsuki Fujisawa, Satoshi Nakamura

Publication date: 21 June 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2022.04.018

zbMATH Keywords

lattice problemsLWElattice basis reductionDeepBKZ

Mathematics Subject Classification ID

Cryptography (94A60)

Uses Software

• NTL
• Eigen
• BKZ
• fpLLL
• GitHub
• G6K

Cites Work

• Unnamed Item
• Unnamed Item
• GitHub
• On the concrete hardness of learning with errors
• 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
• 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
• Second order statistical behavior of LLL and BKZ
• Analysis of DeepBKZ reduction for finding short lattice vectors
• Solving the search-LWE problem by lattice reduction over projected bases
• Advanced lattice sieving on GPUs, with tensor cores
• On the success probability of solving unique SVP via BKZ
• LWE with side information: attacks and concrete security estimation
• A refined analysis of the cost for solving LWE via uSVP
• 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
• Revisiting the expected cost of solving uSVP and applications to LWE
• 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
• BKZ 2.0: Better Lattice Security Estimates
• On the Efficacy of Solving LWE by Reduction to Unique-SVP
• An Experimental Study of Kannan’s Embedding Technique for the Search LWE Problem
• Lattice Enumeration Using Extreme Pruning
• Lattice-based Cryptography
• Minkowski's Convex Body Theorem and Integer Programming
• A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge
• Hermite’s Constant and Lattice Algorithms
• Progress on LLL and Lattice Reduction
• Predicting Lattice Reduction

This page was built for publication: Solving the search-LWE problem over projected lattices