A relation of primal--dual lattices and the complexity of shortest lattice vector problem

DOI10.1016/S0304-3975(98)00058-9zbMath0926.11047OpenAlexW2030170158MaRDI QIDQ1274988

Jin-Yi Cai

Publication date: 12 January 1999

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00058-9

zbMATH Keywords

latticeNP-hardnessshortest vector probleminteractive proofs

Mathematics Subject Classification ID

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

Related Items (8)

Improved hardness results for unique shortest vector problem ⋮ Attribute-based access control for inner product functional encryption from LWE ⋮ Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions ⋮ On the unique shortest lattice vector problem ⋮ Cryptographic Functions from Worst-Case Complexity Assumptions ⋮ On the limits of nonapproximability of lattice problems ⋮ A note on the non-NP-hardness of approximate lattice problems under general Cook reductions. ⋮ A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor

Cites Work

• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• On Lovász' lattice reduction and the nearest lattice point problem
• Dual vectors and lower bounds for the nearest lattice point problem
• Factoring polynomials with rational coefficients
• Geometric algorithms and combinatorial optimization
• New bounds in some transference theorems in the geometry of numbers
• Integer Programming with a Fixed Number of Variables
• Collision-Free Hashing from Lattice Problems
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• The complexity of promise problems with applications to public-key cryptography
• 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: A relation of primal--dual lattices and the complexity of shortest lattice vector problem