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

DOI10.1145/301250.301441zbMATH Open1345.11090OpenAlexW1982051149MaRDI QIDQ2819600FDOQ2819600

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

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

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)

Cited In (15)

• New transference theorems on lattices possessing \(n^\varepsilon\)-unique shortest vectors
• Title not available (Why is that?)
• The geometry of lattice cryptography
• On basing search SIVP on \(\mathbf{NP}\)-hardness
• Lattice-Based Identification Schemes Secure Under Active Attacks
• The Reductions for the Approximating Covering Radius Problem
• 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)