A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms
Explore this paper's citation graph
Summary
An algorithm which for k?N finds a nonzero lattice vector b so that |b|2?(6k2)nk?(L)2, and successively applies Korkine?Zolotareff reduction to blocks of length k of the lattice basis.
- Type
- article
- Published
- 1987-08-02
- Cited by
- 794
- References
- 16
- Access
- Open access
- OpenAlex
- https://openalex.org/W1989510734
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:205092716
Keywords
Lattice reduction, Mathematics, Lattice problem, Lattice (music), Time complexity
References
- An Introduction to the Geometry of Numbers
- Algorithmic theory of numbers, graphs and convexity
- Extraits de lettres de M. Ch. Hermite à M. Jacobi sur différents objects de la théorie des nombres. (Continuation).
- Sur les formes quadratiques
- Worst-Case Complexity Bounds for Algorithms in the Theory of Integral Quadratic Forms
- An application of simultaneous approximation in combinatorial optimization
- Algorithms to Construct Minkowski Reduced an Hermite Reduced Lattice Bases
- U eher die positiven quadratischen Formen und über kettenbruchähnliche Algorithmen
- Integer Programming with a Fixed Number of Variables
- Factoring polynomials with rational coefficients
- Improved algorithms for integer programming and related lattice problems
- Disproof of the Mertens conjecture.
- Ueber die positiven quadratischen Formen und über kettenbruchähnliehe Algorithmen.
- Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers
- Another NP-complete problem and the complexity of computing short vectors in a lattice
- Disquisitiones Arithmeticae
- A More Efficient Algorithm for Lattice Basis Reduction (Extended Abstract)
Cited by
- Arithmétique modulaire pour la cryptographie
- The Rise and Fall of Knapsack Cryptosystems
- A Novel NTRU-Class Digital Signature Scheme: A Novel NTRU-Class Digital Signature Scheme
- New RSA vulnerabilities using lattice reduction methods
- Accelerated Slide- and LLL-Reduction
- A method to solve cyclotomic norm equations f * f
- Enumerative Algorithms for the Shortest and Closest Lattice Vector Problems in Any Norm via M-Ellipsoid Coverings
- BibTEX-List: Combinatorial Designs
- Limits on the Hardness of Lattice Problems in ell _p Norms
- Lattice-based cryptography: a practical implementation
- Nouvelles Constructions algébriques de codes spatio-temporels atteignant le compromis "Multiplexga-Diversité"
- Provable Security of Merkle-Micciancio-Lyubashevsky's Signature
- Lattices that admit logarithmic worst-case to average-case connection factors
- On the Limits of Nonapproximability of Lattice Problems
- Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem
- Security Analysis of the NTRUEncrypt Public Key Encryption Scheme
- Géométrie des nombres et cryptanalyse de NTRU
- GGH Cryptosystem and Lattice Reduction Algorithms
- Analyse probabiliste de la réduction des réseaux euclidiens cryptographiques. (Probabilistic analysis of reduced cryptographic Euclidean networks)
- Approche arithmétique RNS de la cryptographie asymétrique. (RNS arithmetic approach of asymmetric cryptography)