Lattice basis reduction: Improved practical algorithms and solving subset sum problems
From MaRDI portal
A practical floating point \(L^3\)-algorithm, \(L^3FP\), is presented that shows good stability according to empirical tests up to dimension 125 with integer entries of bit length up to 300. Moreover, a practical algorithm for block Korkin-Zolotarev reduction is proposed, and a variant of the Lenstra-Lenstra-Lovasz \(L^3\)-algorithm is introduced that uses ``deep insertions. For all the algorithms presented computational performance in solving subset sum problems is reported.
Recommendations
- Lattice Reduction Algorithms: Theory and Practice
- A hierarchy of polynomial time lattice basis reduction algorithms
- A more efficient algorithm for lattice basis reduction
- scientific article; zbMATH DE number 3958726
- scientific article; zbMATH DE number 3972987
- Practical, Predictable Lattice Basis Reduction
- Towards faster polynomial-time lattice reduction
- scientific article; zbMATH DE number 1643923
- Heuristics on lattice basis reduction in practice
Cites work
- A hierarchy of polynomial time lattice basis reduction algorithms
- A knapsack-type public key cryptosystem based on arithmetic in finite fields
- A more efficient algorithm for lattice basis reduction
- Factoring Integers and Computing Discrete Logarithms via Diophantine Approximation
- Factoring polynomials with rational coefficients
- scientific article; zbMATH DE number 4213909 (Why is no real title available?)
- scientific article; zbMATH DE number 4045845 (Why is no real title available?)
- scientific article; zbMATH DE number 4074814 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1346512 (Why is no real title available?)
- scientific article; zbMATH DE number 1346524 (Why is no real title available?)
- Improved low-density subset sum algorithms
- Integer Programming with a Fixed Number of Variables
- Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
- Minkowski's Convex Body Theorem and Integer Programming
- On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
- Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
- Simultaneous reduction of a lattice basis and its reciprocal basis
- Solving low-density subset sum problems
- The Generalized Basis Reduction Algorithm
Cited in
(only showing first 100 items - show all)- Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures
- Reduced complexity \(K\) -best sphere decoder design for MIMO systems
- Shortest vector from lattice sieving: a few dimensions for free
- On the ring-LWE and polynomial-LWE problems
- A non-commutative cryptosystem based on quaternion algebras
- On the asymptotic complexity of solving LWE
- Sieving for closest lattice vectors (with preprocessing)
- Comment on: ``Sum of squares of uniform random variables by I. Weissman
- On the optimality of lattices for the Coppersmith technique
- A public-key encryption scheme based on non-linear indeterminate equations
- Fast lattice basis reduction suitable for massive parallelization and its application to the shortest vector problem
- A semidefinite programming method for integer convex quadratic minimization
- Solving market split problems with heuristical lattice reduction
- Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme
- Dynamic trading under integer constraints
- Lattice-based algorithms for number partitioning in the hard phase
- Analysis of DeepBKZ reduction for finding short lattice vectors
- Quantum algorithms for computing general discrete logarithms and orders with tradeoffs
- (One) failure is not an option: bootstrapping the search for failures in lattice-based encryption schemes
- A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP
- On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem
- On the ideal shortest vector problem over random rational primes
- Advanced lattice sieving on GPUs, with tensor cores
- The convergence of slide-type reductions
- On the success probability of solving unique SVP via BKZ
- A polynomial-time algorithm for solving the hidden subset sum problem
- Fast reduction of algebraic lattices over cyclotomic fields
- 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
- Slide reduction, revisited -- filling the gaps in SVP approximation
- Improved lattice enumeration algorithms by primal and dual reordering methods
- A physical study of the LLL algorithm
- A practical algorithm for completing half-Hadamard matrices using LLL
- Revisiting orthogonal lattice attacks on approximate common divisor problems
- Quantum security analysis of CSIDH
- Rational isogenies from irrational endomorphisms
- Computing theta functions with Julia
- Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance
- A trace map attack against special ring-LWE samples
- Shortest vectors in lattices of Bai-Galbraith's embedding attack on the LWR problem
- Solving the search-LWE problem over projected lattices
- An extension of Kannan's embedding for solving ring-based LWE problems
- Lattice-based fault attacks on deterministic signature schemes of ECDSA and EdDSA
- Mean value formulas on sublattices and flags of the random lattice
- \(\mathsf{Rubato}\): noisy ciphers for approximate homomorphic encryption
- Quantum algorithms for variants of average-case lattice problems via filtering
- Predicting truncated multiple recursive generators with unknown parameters
- Self-dual DeepBKZ for finding short lattice vectors
- A subexponential-time, polynomial quantum space algorithm for inverting the CM group action
- On post-processing in the quantum algorithm for computing short discrete logarithms
- Dynamic self-dual DeepBKZ lattice reduction with free dimensions and its implementation
- Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification
- Lattice preconditioning for the real relaxation branch-and-bound approach for integer least squares problems
- Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus
- Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes
- A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths
- A new parallel lattice reduction algorithm for BKZ reduced bases
- Bounding basis reduction properties
- Low-density attack revisited
- Estimation of the hardness of the learning with errors problem with a restricted number of samples
- Solving low-density multiple subset sum problems with SVP oracle
- Efficient computation of multidimensional theta functions
- Cryptanalysis of a quadratic compact knapsack public-key cryptosystem
- MLAMBDA: a modified LAMBDA method for integer least-squares estimation
- Reduction of Smith normal form transformation matrices
- A relative van Hoeij algorithm over number fields
- On random nonsingular Hermite normal form
- Improving convergence and practicality of slide-type reductions
- A lattice reduction algorithm based on sublattice BKZ
- Integer factorization as subset-sum problem
- An improved method for predicting truncated multiple recursive generators with unknown parameters
- scientific article; zbMATH DE number 1643923 (Why is no real title available?)
- scientific article; zbMATH DE number 1676629 (Why is no real title available?)
- Finding shortest lattice vectors in the presence of gaps
- The diagonal reduction algorithm using fast Givens
- Practical, Predictable Lattice Basis Reduction
- A sieve algorithm based on overlattices
- Approximating the densest sublattice from Rankin's inequality
- Subexponential class group and unit group computation in large degree number fields
- Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
- A low data complexity attack on the GMR-2 cipher used in the satellite phones
- Lattice Reduction Algorithms: Theory and Practice
- Algorithms for the shortest and closest lattice vector problems
- Better key sizes (and attacks) for LWE-based encryption
- Analysis of Gauss-sieve for solving the shortest vector problem in lattices
- A Parallel Implementation of GaussSieve for the Shortest Vector Problem in Lattices
- Homomorphic AES evaluation using the modified LTV scheme
- Application of mixed integer quadratic program to shortest vector problems
- A survey of VLSI implementations of tree search algorithms for MIMO detection
- An experimental study of Kannan's embedding technique for the search LWE problem
- A semantically secure public key cryptoscheme using bit-pair shadows
- Partially Known Nonces and Fault Injection Attacks on SM2 Signature Algorithm
- Lattice Reduction for Modular Knapsack
- Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
- Sieve algorithms for the shortest vector problem are practical
- Rigorous and Efficient Short Lattice Vectors Enumeration
- scientific article; zbMATH DE number 4074814 (Why is no real title available?)
- PotLLL: a polynomial time version of LLL with deep insertions
- A public key cryptosystem based on three new provable problems
- Analysis of PSLQ, an integer relation finding algorithm
This page was built for publication: Lattice basis reduction: Improved practical algorithms and solving subset sum problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1340057)
