Lattice basis reduction: Improved practical algorithms and solving subset sum problems

DOI10.1007/BF01581144zbMath0829.90099WikidataQ57567988 ScholiaQ57567988MaRDI QIDQ1340057

M. Euchner, Claus Peter Schnorr

Publication date: 11 December 1994

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

subset sumlattice basis reductionblock Korkin- Zolotarev reductionfloating point \(L^ 3\)-algorithm

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Number-theoretic algorithms; complexity (11Y16)

Related Items (only showing first 100 items - show all)

On random nonsingular Hermite normal form ⋮ Computing theta functions with Julia ⋮ SoK: how (not) to design and implement post-quantum cryptography ⋮ Dual lattice attacks for closest vector problems (with preprocessing) ⋮ Bounding basis reduction properties ⋮ 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 ⋮ Homomorphic AES evaluation using the modified LTV scheme ⋮ Partially Known Nonces and Fault Injection Attacks on SM2 Signature Algorithm ⋮ Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing ⋮ A survey of VLSI implementations of tree search algorithms for MIMO detection ⋮ Probability method for cryptanalysis of general multivariate modular linear equation ⋮ Solving the search-LWE problem over projected lattices ⋮ Low-density attack revisited ⋮ An extension of Kannan's embedding for solving ring-based LWE problems ⋮ Lattice-based fault attacks on deterministic signature schemes of ECDSA and EdDSA ⋮ Shortest vector from lattice sieving: a few dimensions for free ⋮ On the ring-LWE and polynomial-LWE problems ⋮ A relative van Hoeij algorithm over number fields ⋮ A semantically secure public key cryptoscheme using bit-pair shadows ⋮ 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 ⋮ A non-commutative cryptosystem based on quaternion algebras ⋮ Lattice-based algorithms for number partitioning in the hard phase ⋮ Predicting truncated multiple recursive generators with unknown parameters ⋮ 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 ⋮ Finding shortest lattice vectors faster using quantum search ⋮ 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 ⋮ PotLLL: a polynomial time version of LLL with deep insertions ⋮ Self-dual DeepBKZ for finding short lattice vectors ⋮ A subexponential-time, polynomial quantum space algorithm for inverting the CM group action ⋮ Efficient computation of multidimensional theta functions ⋮ On the asymptotic complexity of solving LWE ⋮ A public key cryptosystem based on three new provable problems ⋮ Improving convergence and practicality of slide-type reductions ⋮ Cryptanalysis of a quadratic compact knapsack public-key cryptosystem ⋮ Sieving for closest lattice vectors (with preprocessing) ⋮ MLAMBDA: a modified LAMBDA method for integer least-squares estimation ⋮ On post-processing in the quantum algorithm for computing short discrete logarithms ⋮ 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 ⋮ Another 80-dimensional extremal lattice ⋮ Approximate polynomial GCD over integers ⋮ Comment on: ``Sum of squares of uniform random variables by I. Weissman ⋮ An Experimental Study of Kannan’s Embedding Technique for the Search LWE Problem ⋮ 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 ⋮ Algorithms for the Shortest and Closest Lattice Vector Problems ⋮ On the optimality of lattices for the Coppersmith technique ⋮ A public-key encryption scheme based on non-linear indeterminate equations ⋮ A semidefinite programming method for integer convex quadratic minimization ⋮ Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors ⋮ Lattice preconditioning for the real relaxation branch-and-bound approach for integer least squares problems ⋮ Solving market split problems with heuristical lattice reduction ⋮ Analysis of DeepBKZ reduction for finding short lattice vectors ⋮ Non-standard approaches to integer programming ⋮ Factoring polynomials and the knapsack problem ⋮ Reduction of Smith normal form transformation matrices ⋮ Topics in computational algebraic number theory ⋮ Finding Shortest Lattice Vectors in the Presence of Gaps ⋮ Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme ⋮ Dynamic trading under integer constraints ⋮ Parallel Cholesky-based reduction for the weighted integer least squares problem ⋮ The Diagonal Reduction Algorithm Using Fast Givens ⋮ Better Key Sizes (and Attacks) for LWE-Based Encryption ⋮ Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices ⋮ Quantum algorithms for computing general discrete logarithms and orders with tradeoffs ⋮ Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures ⋮ Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus ⋮ (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 ⋮ Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes ⋮ The convergence of slide-type reductions ⋮ On the success probability of solving unique SVP via BKZ ⋮ A Parallel Implementation of GaussSieve for the Shortest Vector Problem in Lattices ⋮ Reduced complexity \(K\) -best sphere decoder design for MIMO systems ⋮ A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths ⋮ Application of mixed integer quadratic program to shortest vector problems ⋮ A new parallel lattice reduction algorithm for BKZ reduced bases ⋮ 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 ⋮ 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 ⋮ Revisiting orthogonal lattice attacks on approximate common divisor problems ⋮ Quantum security analysis of CSIDH ⋮ Rational isogenies from irrational endomorphisms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• Improved low-density subset sum algorithms
• Simultaneous reduction of a lattice basis and its reciprocal basis
• Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
• Integer Programming with a Fixed Number of Variables
• On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
• Solving low-density subset sum problems
• Minkowski's Convex Body Theorem and Integer Programming
• A knapsack-type public key cryptosystem based on arithmetic in finite fields
• The Generalized Basis Reduction Algorithm
• Factoring Integers and Computing Discrete Logarithms via Diophantine Approximation
• A more efficient algorithm for lattice basis reduction

This page was built for publication: Lattice basis reduction: Improved practical algorithms and solving subset sum problems