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

DOI10.1145/301250.301441MaRDI QIDQ2819600zbMATH OpenOpenAlexFDO

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)

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

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)