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

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, Cryptanalysis of NTRU where the private polynomial has one or more consecutive zero coefficients, Evaluating the Cache Side Channel Attacks Against ECDSA, Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography, A Tale of Three Signatures: Practical Attack of ECDSA with wNAF, Individual discrete logarithm with sublattice reduction, Lattice-based SNARKs: publicly verifiable, preprocessing, and recursively composable (extended abstract), Some easy instances of ideal-SVP and implications on the partial Vandermonde knapsack problem, Solving LWR via BDD Strategy: Modulus Switching Approach, Revisiting the Sparsification Technique in Kannan’s Embedding Attack on LWE, Fiat-Shamir signatures based on module-NTRU, Quantum-resistant password-based threshold single-sign-on authentication with updatable server private key, Deterministic factoring with oracles, On the measurement and simulation of the BKZ behavior for \(q\)-ary lattices, Full quantum equivalence of group action DLog and CDH, and more, Log-\(\mathcal{S}\)-unit lattices using explicit Stickelberger generators to solve approx ideal-SVP, Development and analysis of massive parallelization of a lattice basis reduction algorithm, Fast practical lattice reduction through iterated compression, Finding short integer solutions when the modulus is small, An Efficient Algorithm for Integer Lattice Reduction, Lattice enumeration for tower NFS: a 521-bit discrete logarithm computation, Differential fault attack on Montgomery ladder and in the presence of scalar randomization, A sharper lower bound on Rankin's constant, Lattice-based public key cryptosystems invoking linear mapping mask, Lattice enumeration and automorphisms for tower NFS: a 521-bit discrete logarithm computation, Lattice-based cryptography: a survey, The curious case of the half-half Bitcoin ECDSA nonces, Concrete security from worst-case to average-case lattice reductions, Finding and evaluating parameters for BGV, Revisiting security estimation for LWE with hints from a geometric perspective, Subfield algorithms for ideal- and module-SVP based on the decomposition group, Sieve algorithms for the shortest vector problem are practical, Random Sampling Revisited: Lattice Enumeration with Discrete Pruning, Hermite’s Constant and Lattice Algorithms, Cryptographic Functions from Worst-Case Complexity Assumptions, Rigorous and Efficient Short Lattice Vectors Enumeration, Learning strikes again: the case of the DRS signature scheme, Predicting Lattice Reduction, A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge, Unnamed Item, Analysis of PSLQ, an integer relation finding algorithm, A Vectorized, Cache Efficient LLL Implementation, Lattice-Based SNARGs and Their Application to More Efficient Obfuscation

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