Hardness of bounded distance decoding on lattices in lp norms
type: Item
instance of: scholarly article
author: Huck Bennett
author: Chris Peikert
publication date: 2022-07-21T00:00:00Z
full work available at URL: https://arxiv.org/abs/2003.07903
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7561764
zbMATH Keywords: lattices
zbMATH Keywords: bounded distance decoding
zbMATH Keywords: NP-hardness
zbMATH Keywords: fine-grained complexity
MaRDI profile type: MaRDI publication profile
cites work: Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract)
cites work: (Gap/S)ETH hardness of SVP
cites work: Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP)
cites work: Q4542515
cites work: The hardness of approximate optima in lattices, codes, and systems of linear equations
cites work: Q4598216
cites work: On the packing densities of superballs and other bodies
cites work: Trapdoors for hard lattices and new cryptographic constructions
cites work: Tensor-based hardness of the shortest vector problem to within almost polynomial factors
cites work: On the complexity of \(k\)-SAT
cites work: Hardness of approximating the shortest vector problem in lattices
cites work: Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms
cites work: On the unique shortest lattice vector problem
cites work: On Bounded Distance Decoding for General Lattices
cites work: On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
cites work: Lattice points in high-dimensional spheres
cites work: The shortest vector in a lattice is hard to approximate to within some constant
cites work: The hardness of the closest vector problem with preprocessing
cites work: Q3579369
cites work: Inapproximability of the shortest vector problem: toward a deterministic reduction
cites work: Public-key cryptosystems from the worst-case shortest vector problem
cites work: On lattices, learning with errors, random linear codes, and cryptography
cites work: Lattice problems and norm embeddings
cites work: Discrete Gaussian sampling reduces to CVP and SVP
OpenAlex ID: W3013646474
title: Hardness of bounded distance decoding on lattices in lp norms
DOI: 10.4230/LIPICS.CCC.2020.36
description: scientific article; zbMATH DE number 7561764