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

DOI10.1007/BF02579403zbMath0593.68030DBLPjournals/combinatorica/Babai86OpenAlexW2111416661WikidataQ59345776 ScholiaQ59345776MaRDI QIDQ1076512

László Babai

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 (only showing first 100 items - show all)

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 ⋮ Provable lattice reduction of $$\mathbb {Z}^n$$ with blocksize n/2 ⋮ Verification of NP-Hardness Reduction Functions for Exact Lattice Problems ⋮ 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 ⋮ 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

Cites Work

This page was built for publication: On Lovász' lattice reduction and the nearest lattice point problem