A hierarchy of polynomial time lattice basis reduction algorithms

DOI10.1016/0304-3975(87)90064-8zbMath0642.10030OpenAlexW1989510734WikidataQ57567987 ScholiaQ57567987MaRDI QIDQ1101500

Publication date: 1987

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90064-8

zbMATH Keywords

shortest lattice vector computational number theory Korkine-Zolotareff reduction Lenstra, Lenstra, Lovász reduction polynomial time lattice basis reduction algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies (number-theoretic aspects) (11H06) Quadratic forms (reduction theory, extreme forms, etc.) (11H55)

Related Items

On Lovász' lattice reduction and the nearest lattice point problem, Dual lattice attacks for closest vector problems (with preprocessing), Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance, Towards faster polynomial-time lattice reduction, Column basis reduction and decomposable knapsack problems, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Lattice-based fault attacks on deterministic signature schemes of ECDSA and EdDSA, Fiat-Shamir and correlation intractability from strong KDM-secure encryption, Approximate CVP in time $2^{0.802 n}$ -- now in any norm!, Segment LLL reduction of lattice bases using modular arithmetic, On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography, Simultaneously good bases of a lattice and its reciprocal lattice, A Fast Phase-based Enumeration Algorithm for SVP Challenge Through $$y$$-Sparse Representations of Short Lattice Vectors, Lattice-based algorithms for number partitioning in the hard phase, Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing, Sharper bounds on four lattice constants, Lattice Point Enumeration on Block Reduced Bases, Finding shortest lattice vectors faster using quantum search, Solving low-density multiple subset sum problems with SVP oracle, Correcting noisy exponentiation black-boxes modulo a prime, Self-dual DeepBKZ for finding short lattice vectors, Characterizing overstretched NTRU attacks, A polynomial algorithm for minimizing discrete convic functions in fixed dimension, Sparse recovery with integrality constraints, On the modular inversion hidden number problem, The optimal LLL algorithm is still polynomial in fixed dimension., Improving convergence and practicality of slide-type reductions, Sieving for closest lattice vectors (with preprocessing), Twisted-PHS: using the product formula to solve approx-SVP in ideal lattices, Hardness of approximating the closest vector problem with pre-processing, On post-processing in the quantum algorithm for computing short discrete logarithms, Another 80-dimensional extremal lattice, Lattice-based FHE as secure as PKE, Cryptogenography, Limits of random oracles in secure computation, Non-commutative arithmetic circuits with division, Decision trees, protocols and the entropy-influence conjecture, Locally testable codes and cayley graphs, Invitation games and the price of stability, Welfare maximization and truthfulness in mechanism design with ordinal preferences, Coordination mechanisms from (almost) all scheduling policies, Private interactive communication across an adversarial channel, Tree codes and a conjecture on exponential sums, Capacity of non-malleable codes, Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications, Adversarial hypothesis testing and a quantum stein's lemma for restricted measurements, Sequential decision making with vector outcomes, Learning mixtures of arbitrary distributions over large discrete domains, Why do simple algorithms for triangle enumeration work in the real world?, Black-box obfuscation for d-CNFs, Candidate weak pseudorandom functions in AC ⁰ ○ MOD ₂, Iterated group products and leakage resilience against NC1, Building one-time memories from isolated qubits, Attribute-efficient evolvability of linear functions, Energy-efficient circuit design, Rate-independent computation in continuous chemical reaction networks, Thinner is not always better: cascade knapsack problems, ETRU: NTRU over the Eisenstein integers, Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification, Non-planar universal anomalous dimension of twist-two operators with general Lorentz spin at four loops in $\mathcal{N} = 4$ SYM theory, Second order statistical behavior of LLL and BKZ, Approximate short vectors in ideal lattices of $\mathbb{Q}(\zeta_{p^e})$ with precomputation of ${\mathrm {Cl}}(\mathcal{O}_K)$, Pseudorandom functions in NC class from the standard LWE assumption, Security of the most significant bits of the Shamir message passing scheme, Improved low-density subset sum algorithms, Solving market split problems with heuristical lattice reduction, Analysis of DeepBKZ reduction for finding short lattice vectors, Non-standard approaches to integer programming, Fast LLL-type lattice reduction, Hardness of approximating the shortest vector problem in high $\ell_{p}$ norms, On the structure of Boolean functions with small spectral norm, (Leveled) Fully Homomorphic Encryption without Bootstrapping, Decompositions of Triangle-Dense Graphs, Parallel Cholesky-based reduction for the weighted integer least squares problem, Noisy polynomial interpolation modulo prime powers, Subexponential time relations in the class group of large degree number fields, Quantum algorithms for computing general discrete logarithms and orders with tradeoffs, Sampling methods for shortest vectors, closest vectors and successive minima, Approximate CVP$_p$ in time $2^{0.802n}$, 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, Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes, Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice, The convergence of slide-type reductions, Circuit-ABE from LWE: Unbounded Attributes and Semi-adaptive Security, A Subfield Lattice Attack on Overstretched NTRU Assumptions, Lattice-Based Fully Dynamic Multi-key FHE with Short Ciphertexts, Noisy Chinese remaindering in the Lee norm, On the limits of nonapproximability of lattice problems, A polynomial-time algorithm for solving the hidden subset sum problem, Slide reduction, revisited -- filling the gaps in SVP approximation, Random lattices, threshold phenomena and efficient reduction algorithms., A lattice-based public-key cryptosystem, Simultaneous reduction of a lattice basis and its reciprocal basis, SLIDE REDUCTION, SUCCESSIVE MINIMA AND SEVERAL APPLICATIONS, The remote set problem on lattices, Search for combinatorial objects using lattice algorithms -- revisited, Approximating the densest sublattice from Rankin’s inequality, Subexponential class group and unit group computation in large degree number fields, Generating cryptographically-strong random lattice bases and recognizing rotations of $\mathbb{Z}^n$, Meta-heuristic approaches to solve shortest lattice vector problem, Sieve, Enumerate, Slice, and Lift:, A Tale of Three Signatures: Practical Attack of ECDSA with wNAF, Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes, Attacking RSA with a Composed Decryption Exponent Using Unravelled Linearization, Partially Known Nonces and Fault Injection Attacks on SM2 Signature Algorithm, Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation, Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing, Targeted Homomorphic Attribute-Based Encryption, On the Security of OSIDH, Cloud-Assisted LLL: A Secure and Efficient Outsourcing Algorithm for Approximate Shortest Vector Problem, NTRU Fatigue: How Stretched is Overstretched?, Finding many collisions via reusable quantum walks. Application to lattice sieving, Fiat-Shamir signatures based on module-NTRU, Homomorphic encryption: a mathematical survey, Subfield attacks on HSVP in ideal lattices, Log-$\mathcal{S}$-unit lattices using explicit Stickelberger generators to solve approx ideal-SVP, On module unique-SVP and NTRU, Block Reduced Lattice Bases and Successive Minima, On the hardness of the NTRU problem, A sharper lower bound on Rankin's constant, Algebraic Cryptanalysis of CTRU Cryptosystem, The curious case of the half-half Bitcoin ECDSA nonces, 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), Explicit Hard Instances of the Shortest Vector Problem, Deterministic compression with uncertain priors, Sieve algorithms for the shortest vector problem are practical, Thrackles: An Improved Upper Bound, Testers and their applications, On the automorphism groups of strongly regular graphs I, Faster private release of marginals on small databases, Mechanism design in large games, Redrawing the boundaries on purchasing data from privacy-sensitive individuals, Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems, Complexity of approximating CSP with balance / hard constraints, Integer feasibility of random polytopes, Multireference alignment using semidefinite programming, Partial tests, universal tests and decomposability, High dimensional expanders and property testing, Parameterized testability, Direct sum fails for zero error average communication, Rational arguments, Lattice-Based Fault Attacks Against ECMQV, On a Waring’s problem for integral quadratic and Hermitian forms, On a quadratic Waring's problem with congruence conditions, Approximate CVP_p in Time 2^{0.802 n}, Algorithms for the Shortest and Closest Lattice Vector Problems, Lattice Reformulation Cuts, On the Bit Security of Elliptic Curve Diffie–Hellman, Revisiting Lattice Attacks on Overstretched NTRU Parameters, Short Stickelberger Class Relations and Application to Ideal-SVP, La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász, Bounding the sum of square roots via lattice reduction, Improved Rounding for Spline Coefficients and Knots, Symplectic Lattice Reduction and NTRU, Hermite’s Constant and Lattice Algorithms, LLL: A Tool for Effective Diophantine Approximation, The Geometry of Provable Security: Some Proofs of Security in Which Lattices Make a Surprise Appearance, Cryptographic Functions from Worst-Case Complexity Assumptions, The truth behind the myth of the folk theorem, Rigorous and Efficient Short Lattice Vectors Enumeration, Expanders with respect to Hadamard spaces and random graphs, Limits of local algorithms over sparse random graphs, A Digital Signature Scheme Based on CVP ∞, Improvements in the analysis of Kannan's CVP algorithm, Predicting Lattice Reduction, Quantum algorithms for algebraic problems, Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices, A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge, Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle, A time-distance trade-off for GDD with preprocessing: instantiating the DLW heuristic, Hermite reduction and a Waring’s problem for integral quadratic forms over number fields, Pseudorandom Functions: Three Decades Later

Cites Work