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

DOI10.1145/301250.301441zbMath1345.11090OpenAlexW1982051149MaRDI QIDQ2819600

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

latticesworst-case complexityshortest vectoraverage-case complexityalgorithmic geometry of numbersclosest vectorhardness of approximationsshortest lattice basis

Mathematics Subject Classification ID

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

Related Items (13)

On basing search SIVP on \(\mathbf{NP}\)-hardness ⋮ A note on the concrete hardness of the shortest independent vector in lattices ⋮ New transference theorems on lattices possessing \(n^\varepsilon\)-unique shortest vectors ⋮ Sieve algorithms for some orthogonal integer lattices ⋮ \(\mathrm{mR}_{\mathrm{LWE}}\)-CP-ABE: a revocable CP-ABE for post-quantum cryptography ⋮ The Reductions for the Approximating Covering Radius Problem ⋮ Fast LLL-type lattice reduction ⋮ Lattice-Based Identification Schemes Secure Under Active Attacks ⋮ Sampling methods for shortest vectors, closest vectors and successive minima ⋮ Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle ⋮ The Geometry of Lattice Cryptography ⋮ A note on the non-NP-hardness of approximate lattice problems under general Cook reductions. ⋮ 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