Fast LLL-type lattice reduction

DOI10.1016/j.ic.2005.04.004zbMath1108.11090OpenAlexW2031600610MaRDI QIDQ2490117

Claus Peter Schnorr

Publication date: 28 April 2006

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:hebis:30-12071

zbMATH Keywords

Householder reflectionQR-decompositionLLL-reductionSegmentsFloating point errorsLength defectLocal LLL-reductionSLLL-reduction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06)

Related Items (14)

Perturbation Analysis of the QR factor R in the context of LLL lattice basis reduction ⋮ Lattice Reduction for Modular Knapsack ⋮ Probability method for cryptanalysis of general multivariate modular linear equation ⋮ Segment LLL reduction of lattice bases using modular arithmetic ⋮ Modular Las Vegas algorithms for polynomial absolute factorization ⋮ Efficient Nyberg-Rueppel type of NTRU digital signature algorithm ⋮ A public key cryptosystem based on three new provable problems ⋮ Efficient Modular Arithmetic in Adapted Modular Number System Using Lagrange Representation ⋮ LLL for ideal lattices: re-evaluation of the security of Gentry-Halevi's FHE scheme ⋮ Efficient UC-Secure Authenticated Key-Exchange for Algebraic Languages ⋮ Cryptographic Functions from Worst-Case Complexity Assumptions ⋮ Cryptanalysis of General Lu-Lee Type Systems ⋮ A Digital Signature Scheme Based on CVP  ∞ ⋮ Parallel Cholesky-based reduction for the weighted integer least squares problem

Uses Software

• NTL

Cites Work

• Algorithms to construct Minkowski reduced and Hermite reduced lattice bases
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• An upper bound on the average number of iterations of the LLL algorithm
• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• Segment LLL reduction of lattice bases using modular arithmetic
• Random lattices, threshold phenomena and efficient reduction algorithms.
• The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
• On the complexity of computing short linearly independent vectors and short bases in a lattice
• Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
• Integer Programming with a Fixed Number of Variables
• The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice
• Minkowski's Convex Body Theorem and Integer Programming
• A more efficient algorithm for lattice basis reduction
• A sieve algorithm for the shortest lattice vector problem
• Floating-Point LLL Revisited
• Advances in Cryptology - CRYPTO 2003
• Finding smooth integers in short intervals using CRT decoding
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Fast LLL-type lattice reduction