On the complexity of computing short linearly independent vectors and short bases in a lattice

DOI10.1145/301250.301441MaRDI QIDQ2819600zbMATHOpenAlexFDO

Authors Johannes Blömer, Jean-Pierre Seifert

Publication date 29 September 2016

Published in Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/301250.301441

zbMATH Keywords

latticesaverage-case complexityworst-case complexityshortest vectoralgorithmic geometry of numbersclosest vectorhardness of approximationsshortest lattice basis

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Lattices and convex bodies (number-theoretic aspects) (11H06) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• A relation of primal--dual lattices and the complexity of shortest lattice vector problem
• Hardness of approximating the shortest vector problem in lattices
• The shortest vector in a lattice is hard to approximate to within some constant
• Complexity of lattice problems. Non-approximability and limits of non-approximability
• scientific article; zbMATH DE number 1775383

Cited in

(16)

• A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.
• Fast LLL-type lattice reduction
• New transference theorems on lattices possessing \(n^\varepsilon\)-unique shortest vectors
• On basing search SIVP on \(\mathbf{NP}\)-hardness
• Complexity of lattice problems. Non-approximability and limits of non-approximability
• The geometry of lattice cryptography
• Approximating the closest vector problem using an approximate shortest vector oracle
• Sampling methods for shortest vectors, closest vectors and successive minima
• Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time
• scientific article; zbMATH DE number 1643917 (Why is no real title available?)
• A note on the concrete hardness of the shortest independent vector in lattices
• \(\mathrm{mR}_{\mathrm{LWE}}\)-CP-ABE: a revocable CP-ABE for post-quantum cryptography
• The reductions for the approximating covering radius problem
• Lattice-Based Identification Schemes Secure Under Active Attacks
• Sieve algorithms for some orthogonal integer lattices
• Worst-case to average-case reductions for module lattices

This page was built for publication: On the complexity of computing short linearly independent vectors and short bases in a lattice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2819600)