Slide reduction, revisited -- filling the gaps in SVP approximation
From MaRDI portal
Publication:2096526
DOI10.1007/978-3-030-56880-1_10zbMath1504.94089arXiv1908.03724OpenAlexW3080869780MaRDI QIDQ2096526
Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen, Noah Stephens-Davidowitz
Publication date: 9 November 2022
Full work available at URL: https://arxiv.org/abs/1908.03724
Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Approximation algorithms (68W25)
Related Items
Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance ⋮ Towards faster polynomial-time lattice reduction ⋮ Property-preserving hash functions for Hamming distance from standard assumptions ⋮ Subfield attacks on HSVP in ideal lattices ⋮ On module unique-SVP and NTRU ⋮ Improving convergence and practicality of slide-type reductions ⋮ A lattice reduction algorithm based on sublattice BKZ ⋮ Dynamic self-dual DeepBKZ lattice reduction with free dimensions and its implementation ⋮ A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP ⋮ Advanced lattice sieving on GPUs, with tensor cores ⋮ The convergence of slide-type reductions ⋮ On the success probability of solving unique SVP via BKZ ⋮ Faster enumeration-based lattice reduction: root Hermite factor \(k^{1/(2k)}\) time \(k^{k/8+o(k)}\) ⋮ Lattice reduction for modules, or how to reduce ModuleSVP to ModuleSVP
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The LLL algorithm. Survey and applications
- A hierarchy of polynomial time lattice basis reduction algorithms
- Factoring polynomials with rational coefficients
- Lattice reduction: a toolbox for the cryptoanalyst
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- Bounding basis reduction properties
- Finding Shortest Lattice Vectors in the Presence of Gaps
- A Decade of Lattice Cryptography
- Practical, Predictable Lattice Basis Reduction
- A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
- SLIDE REDUCTION, SUCCESSIVE MINIMA AND SEVERAL APPLICATIONS
- Approximating the densest sublattice from Rankin’s inequality
- Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers
- Solving the Shortest Vector Problem in 2 n Time Using Discrete Gaussian Sampling
- Integer Programming with a Fixed Number of Variables
- A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem
- Sieve algorithms for the shortest vector problem are practical
- Trapdoors for hard lattices and new cryptographic constructions
- Symplectic Lattice Reduction and NTRU
- New directions in nearest neighbor searching with applications to lattice sieving
- Computing a Lattice Basis Revisited
- Public-key cryptosystems from the worst-case shortest vector problem
- A sieve algorithm for the shortest lattice vector problem
- Analyzing Blockwise Lattice Algorithms Using Dynamical Systems
- Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)
- Predicting Lattice Reduction
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
- Rankin’s Constant and Blockwise Lattice Reduction
- On lattices, learning with errors, random linear codes, and cryptography
This page was built for publication: Slide reduction, revisited -- filling the gaps in SVP approximation
