The hardness of the closest vector problem with preprocessing

DOI10.1109/18.915688zbMath1005.68078OpenAlexW2101362102MaRDI QIDQ4544560

Daniele Micciancio

Publication date: 4 August 2002

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/0efec059f78f4620933ea6f57ca63eec9c6c7ebd

zbMATH Keywords

NP-hardnessclosest vector problem

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (14)

The inapproximability of lattice and coding problems with preprocessing ⋮ A non-commutative cryptosystem based on quaternion algebras ⋮ Lattice-based algorithms for number partitioning in the hard phase ⋮ Solving low-density multiple subset sum problems with SVP oracle ⋮ A polynomial time algorithm for GapCVPP in \(l_1\) norm ⋮ Sieving for closest lattice vectors (with preprocessing) ⋮ Hardness of approximating the closest vector problem with pre-processing ⋮ Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH ⋮ An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm ⋮ Approximate Voronoi cells for lattices, revisited ⋮ Post-Quantum Cryptography: State of the Art ⋮ On compact representations of Voronoi cells of lattices ⋮ Unnamed Item ⋮ Hardness of bounded distance decoding on lattices in lp norms

This page was built for publication: The hardness of the closest vector problem with preprocessing