On Lovász' lattice reduction and the nearest lattice point problem

DOI10.1007/BF02579403zbMath0593.68030OpenAlexW2111416661WikidataQ59345776 ScholiaQ59345776MaRDI QIDQ1076512

Publication date: 1986

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579403

zbMATH Keywords

polynomial time nonhomogeneous computational number theory simultaneous diophantine approximation Grötschel-Lowasz-Schrijver version Lenstra's integer linear Lovasz-reduced basis programming algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Lattices and convex bodies (number-theoretic aspects) (11H06) Quadratic forms (reduction theory, extreme forms, etc.) (11H55) Diophantine approximation, transcendental number theory (11J99)

Related Items

Algorithms to construct Minkowski reduced and Hermite reduced lattice bases, Dual lattice attacks for closest vector problems (with preprocessing), How to meet ternary LWE keys, Column basis reduction and decomposable knapsack problems, Cryptanalysis of a public key cryptosystem based on Diophantine equations via weighted LLL reduction, 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, The $\mathbb Q$-curve construction for endomorphism-accelerated elliptic curves, The hardness of approximate optima in lattices, codes, and systems of linear equations, Lattice-based fault attacks on deterministic signature schemes of ECDSA and EdDSA, Diophantine approximation of matrices, Fiat-Shamir and correlation intractability from strong KDM-secure encryption, Shortest vector from lattice sieving: a few dimensions for free, Recovering zeros of polynomials modulo a prime, Dual vectors and lower bounds for the nearest lattice point problem, Post-quantum cryptography: lattice signatures, Approximate CVP in time $2^{0.802 n}$ -- now in any norm!, Ciphertext-only attacks against compact-LWE submitted to NIST PQC project, Unnamed Item, Simultaneously good bases of a lattice and its reciprocal lattice, Cubic $(m,n)$-metacirculant graphs which are not Cayley graphs, Symmetry groups of Boolean functions and constructions of permutation groups, Automorphism groups and isomorphisms of Cayley digraphs, Geometry of the Kronecker sequence, LLL-reduction for integer knapsacks, Improvements in closest point search based on dual HKZ-bases, A detailed analysis of the hybrid lattice-reduction and meet-in-the-middle attack, Estimation of the hardness of the learning with errors problem with a restricted number of samples, Attacking the linear congruential generator on elliptic curves via lattice techniques, Lattice-basis reduction precoding based on successive interference cancellation design for multiuser MIMO downlink system, On the number of lattice points in a small sphere and a recursive lattice decoding algorithm, Improved analysis of the reduction from BDD to uSVP, Gaussian sampling of lattices for cryptographic applications, Efficient computation of multidimensional theta functions, Distances to lattice points in knapsack polyhedra, The closest vector problem in tensored root lattices of type A and in their duals, The optimal LLL algorithm is still polynomial in fixed dimension., Cryptanalysis of the GGH cryptosystem, Lattice attacks against elliptic-curve signatures with blinded scalar multiplication, Lattice polly cracker cryptosystems, MLAMBDA: a modified LAMBDA method for integer least-squares estimation, On post-processing in the quantum algorithm for computing short discrete logarithms, Simplicial volume and fillings of hyperbolic manifolds, Jug measuring: algorithms and complexity, Lattice-based completely non-malleable public-key encryption in the standard model, Privately outsourcing exponentiation to a single server: cryptanalysis and optimal constructions, The Reductions for the Approximating Covering Radius Problem, A randomized sieving algorithm for approximate integer programming, Algorithms for the Shortest and Closest Lattice Vector Problems, Cryptanalysis of the Knapsack Generator, A public-key encryption scheme based on non-linear indeterminate equations, General Theory for Integer-Type Algorithm for Higher Order Differential Equations, Lattice preconditioning for the real relaxation branch-and-bound approach for integer least squares problems, Security analysis of cryptosystems using short generators over ideal lattices, Solving market split problems with heuristical lattice reduction, Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices, La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász, Enhancing Goldreich, Goldwasser and Halevi's scheme with intersecting lattices, Short principal ideal problem in multicubic fields, On the complexity of cutting-plane proofs, Algorithms for CRT-variant of approximate greatest common divisor problem, On finite-precision representations of geometric objects, Parallel Cholesky-based reduction for the weighted integer least squares problem, Improvement of Lattice-Based Cryptography Using CRT, Lattice sieving in three dimensions for discrete log in medium characteristic, Lattice-based treshold-changeability for standard CRT secret-sharing schemes, The Diagonal Reduction Algorithm Using Fast Givens, The shortest vector problem and tame kernels of cyclotomic fields, Better Key Sizes (and Attacks) for LWE-Based Encryption, Quantum algorithms for computing general discrete logarithms and orders with tradeoffs, Sampling methods for shortest vectors, closest vectors and successive minima, Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures, Key recovery from Gram-Schmidt norm leakage in hash-and-sign signatures over NTRU lattices, Threshold schemes from isogeny assumptions, Cutting-plane proofs in polynomial space, Automorphism groups of graphs with 1-factorizations, Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice, Exact lattice sampling from non-Gaussian distributions, A relation of primal--dual lattices and the complexity of shortest lattice vector problem, On the limits of nonapproximability of lattice problems, Implementation report of the Kohel-Lauter-Petit-Tignol algorithm for the constructive Deuring correspondence, Practical Implementation and Error Bound of Integer-Type Algorithm for Higher-Order Differential Equations, Generalized symmetry of graphs - a survey, A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths, Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey, On polynomial-time solvable linear Diophantine problems, On the minimum order of graphs with given semigroup, A polynomial-time algorithm for solving the hidden subset sum problem, 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, A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor, SLIDE REDUCTION, SUCCESSIVE MINIMA AND SEVERAL APPLICATIONS, A note on BDD problems with $\lambda_2$-gap, New bounds in some transference theorems in the geometry of numbers, The remote set problem on lattices, Approximating $SVP_{\infty}$ to within almost-polynomial factors is NP-hard, Commutative images of rational languages and the Abelian kernel of a monoid, He gives C-sieves on the CSIDH, Quantum security analysis of CSIDH, Homomorphic Encryption Standard, Sieve, Enumerate, Slice, and Lift:, Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes, Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation, Sampling from Arbitrary Centered Discrete Gaussians for Lattice-Based Cryptography, Towards a Simpler Lattice Gadget Toolkit, SCALLOP: scaling the CSI-FiSh, Reconstructing points of superelliptic curves over a prime finite field, Some easy instances of ideal-SVP and implications on the partial Vandermonde knapsack problem, Solving LWR via BDD Strategy: Modulus Switching Approach, Hybrid dual and meet-LWE attack, \textsc{Hawk}: module LIP makes lattice signatures fast, compact and simple, Enumeration and unimodular equivalence of empty delta-modular simplices, Log-$\mathcal{S}$-unit lattices using explicit Stickelberger generators to solve approx ideal-SVP, Block Reduced Lattice Bases and Successive Minima, Finding short integer solutions when the modulus is small, The special case of cyclotomic fields in quantum algorithms for unit groups, Compact lattice gadget and its applications to hash-and-sign signatures, Error correction and ciphertext quantization in lattice cryptography, Mathematics of computation through the lens of linear equations and lattices, Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP), Sieve algorithms for the shortest vector problem are practical, A Parametric Version of LLL and Some Consequences: Parametric Shortest and Closest Vector Problems, An Experimental Study of Kannan’s Embedding Technique for the Search LWE Problem, Lattice-Based Fault Attacks Against ECMQV, On the Bit Security of Elliptic Curve Diffie–Hellman, Short Generators Without Quantum Computers: The Case of Multiquadratics, A natural lattice basis problem with applications, Improved Rounding for Spline Coefficients and Knots, A multidimensional continued fraction based on a high-order recurrence relation, Symplectic Lattice Reduction and NTRU, Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures, LLL: A Tool for Effective Diophantine Approximation, Selected Applications of LLL in Number Theory, Cryptographic Functions from Worst-Case Complexity Assumptions, Cryptanalysis of General Lu-Lee Type Systems, Exponentiation in Pairing-Friendly Groups Using Homomorphisms, Unnamed Item, A Digital Signature Scheme Based on CVP ∞, Improvements in the analysis of Kannan's CVP algorithm, A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge, On Modular Decomposition of Integers, A time-distance trade-off for GDD with preprocessing: instantiating the DLW heuristic, Algorithms for the Generalized NTRU Equations and their Storage Analysis, The Restricted Isometry Property of Subsampled Fourier Matrices

Cites Work