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

DOI10.1145/301250.301441zbMATH Open1345.11090OpenAlexW1982051149MaRDI QIDQ2819600FDOQ2819600

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)

Cited In (15)

• New transference theorems on lattices possessing \(n^\varepsilon\)-unique shortest vectors
• Title not available (Why is that?)
• Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle
• On basing search SIVP on \(\mathbf{NP}\)-hardness
• The Geometry of Lattice Cryptography
• 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
• 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)