# Hardness of the (Approximate) Shortest Vector Problem:
A Simple Proof via Reed-Solomon Codes

Huck Bennett Oregon State University<EMAIL_ADDRESS>Part of
this work was completed while the author was at the University of Michigan and
supported by NSF Grant No. CCF-2006857. The views expressed are those of the
authors and do not necessarily reflect the official policy or position of the
National Science Foundation. Chris Peikert University of Michigan and
Algorand, Inc<EMAIL_ADDRESS>This author’s work was supported by NSF
Grant No. CCF-2006857.

###### Abstract

We give a _simple_ proof that the (approximate, decisional) Shortest Vector
Problem is $\mathsf{NP}$-hard under a randomized reduction. Specifically, we
show that for any $p\geq 1$ and any constant $\gamma<2^{1/p}$, the
$\gamma$-approximate problem in the $\ell_{p}$ norm
($\gamma$-$\mathrm{GapSVP}_{p}$) is not in $\mathsf{RP}$ unless
$\mathsf{NP}\subseteq\mathsf{RP}$. Our proof follows an approach pioneered by
Ajtai (STOC 1998), and strengthened by Micciancio (FOCS 1998 and SICOMP 2000),
for showing hardness of $\gamma$-$\mathrm{GapSVP}_{p}$ using _locally dense
lattices_. We construct such lattices simply by applying “Construction A” to
Reed-Solomon codes with suitable parameters, and prove their local density via
an elementary argument originally used in the context of Craig lattices.

As in all known $\mathsf{NP}$-hardness results for $\mathrm{GapSVP}_{p}$ with
$p<\infty$, our reduction uses randomness. Indeed, it is a notorious open
problem to prove $\mathsf{NP}$-hardness via a deterministic reduction. To this
end, we additionally discuss potential directions and associated challenges
for derandomizing our reduction. In particular, we show that a close
deterministic analogue of our local density construction would improve on the
state-of-the-art explicit Reed-Solomon list-decoding lower bounds of Guruswami
and Rudra (STOC 2005 and IEEE Transactions on Information Theory 2006).

As a related contribution of independent interest, we also give a polynomial-
time algorithm for decoding $n$-dimensional “Construction A Reed-Solomon
lattices” (with different parameters than those used in our hardness proof) to
a distance within an $O(\sqrt{\log n})$ factor of Minkowski’s bound. This
asymptotically matches the best known distance for decoding near Minkowski’s
bound, due to Mook and Peikert (IEEE Transactions on Information Theory 2022),
whose work we build on with a somewhat simpler construction and analysis.

lox

##  1 Introduction

> [I]t may easily happen that other, perhaps in some sense simpler, lattices
> also have the properties that are required from $L$ to complete the proof…
> There are different reasons which may motivate the search for such a
> lattice: to make the proof deterministic; to improve the factor in the
> approximation result; to make the proof simpler.
>
> Miklós Ajtai, [Ajt98, Remark 2]

A _lattice_ $\mathcal{L}$ is the set of all integer linear combinations of
some $n$ linearly independent vectors
$\boldsymbol{b}_{1},\ldots,\boldsymbol{b}_{n}\in\mathbb{R}^{m}$. The matrix
$B=(\boldsymbol{b}_{1},\ldots,\boldsymbol{b}_{n})$ whose columns are these
vectors is called a _basis_ of $\mathcal{L}$, and $n$ is called its _rank_.
Formally, the lattice $\mathcal{L}$ generated by $B$ is defined as

$\mathcal{L}=\mathcal{L}(B):=\Big{\\{}\sum_{i=1}^{n}a_{i}\boldsymbol{b}_{i}:a_{1},\ldots,a_{n}\in\mathbb{Z}\Big{\\}}\
\text{.}$

Lattices are classically studied mathematical objects, and have proved
invaluable in many computer science applications, especially the design and
analysis of cryptosystems. Indeed, the area of lattice-based cryptography,
which designs cryptosystems whose security is based on the apparent
intractability of certain computational problems on lattices, has flourished
over the past quarter century. (See [Pei16] and its bibliography for a
comprehensive summary and list of references.)

The central computational problem on lattices is the Shortest Vector Problem
($\mathrm{SVP}$): given a lattice basis $B$ as input, the goal is to find a
shortest non-zero vector in $\mathcal{L}(B)$. This paper is concerned with its
$\gamma$-approximate decision version in the $\ell_{p}$ norm
($\gamma$-$\mathrm{GapSVP}_{p}$), where $p\geq 1$ is fixed and the
approximation factor $\gamma=\gamma(n)\geq 1$ is some function of the lattice
rank $n$ (often a constant). Here the input additionally includes a distance
threshold $s>0$, and the goal is to determine whether the length (in the
$\ell_{p}$ norm)
$\lambda_{1}^{(p)}(\mathcal{L}):=\min_{\boldsymbol{v}\in\mathcal{L}\setminus\\{\boldsymbol{0}\\}}\lVert\boldsymbol{v}\rVert_{p}$
of the shortest non-zero vector in $\mathcal{L}$ is at most $s$, or is
strictly greater than $\gamma s$, when one of the two cases is promised to
hold. For the exact problem, where $\gamma=1$, we often simply write
$\mathrm{GapSVP}_{p}$.

Motivated especially by its central role in the security of lattice-based
cryptography, understanding the complexity of $\gamma$-$\mathrm{GapSVP}$ has
been the subject of a long line of work. In an early technical report, van
Emde Boas [vEB81] initiated the study of the hardness of lattice problems more
generally, and in particular showed that $\mathrm{GapSVP}_{\infty}$ is
$\mathsf{NP}$-hard. Seventeen years later, Ajtai [Ajt98] finally showed
similar hardness for the important Euclidean case of $p=2$, i.e., he showed
that exact $\mathrm{GapSVP}_{2}$ is $\mathsf{NP}$-hard, though under a
_randomized_ reduction. Subsequent work [CN98, Mic98, Kho03, Kho04, HR07,
Mic12] improved this by showing that $\gamma$-$\mathrm{GapSVP}_{p}$ in any
$\ell_{p}$ norm is $\mathsf{NP}$-hard to approximate for any constant
$\gamma\geq 1$, and hard for nearly polynomial factors
$\gamma=n^{\Omega(1/\log\log n)}$ assuming stronger complexity assumptions,
also using randomized reductions. Recent work [AS18, BPT22] has also shown the
_fine-grained_ hardness of $\gamma$-$\mathrm{GapSVP}_{p}$ for small constants
$\gamma$ (again under randomized reductions). On the other hand,
$\gamma$-$\mathrm{GapSVP}_{p}$ for finite $p\geq 2$ is unlikely to be
$\mathsf{NP}$-hard for approximation factors $\gamma\geq C_{p}\sqrt{n}$ (where
$C_{p}$ is a constant depending only on $p$) [GG98, AR04, Pei07], and the
security of lattice-based cryptography relies on the conjectured hardness of
$\mathrm{GapSVP}$ or other problems for even larger (but typically polynomial)
factors.

While this line of work has been very successful in showing progressively
stronger hardness of approximation and fine-grained hardness for
$\gamma$-$\mathrm{GapSVP}_{p}$, it leaves some other important issues
unresolved. First, for $p\neq\infty$ the hardness reductions and their
analysis are rather complicated, and second, they are randomized. Indeed, it
is a notorious, long-standing open problem to prove that $\mathrm{GapSVP}_{p}$
is $\mathsf{NP}$-hard, even in its exact form, under a deterministic reduction
for some finite $p$. While there have been some potential steps in this
direction [Mic98, Mic12], e.g., using plausible number-theoretic conjectures
that appear very hard to prove, there has been no new progress on this front
for a decade.

###  1.1 Our Contributions

The primary contribution of this work is to give a substantially simpler proof
that $\gamma$-$\mathrm{GapSVP}_{p}$ is $\mathsf{NP}$-hard under a randomized
reduction, for any $p\geq 1$ and constant $\gamma<2^{1/p}$. The heart of our
reduction is a family of “gadget” lattices $\mathcal{L}$ derived from Reed-
Solomon codes $\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$ (for prime $q$) via the
very natural “Construction A” [CS99], which simply sets
$\mathcal{L}=\mathcal{C}+q\mathbb{Z}^{n}$. These lattices also are closely
related to a family studied by Craig [Cra], and we take advantage of this
similarity in our analysis (see Section 1.3 for details).

######  Theorem 1.1 (Hardness of $\gamma$-$\mathrm{GapSVP}_{p}$).

For any $p\geq 1$ and constant $\gamma$ satisfying $1\leq\gamma<2^{1/p}$,
$\gamma$-$\mathrm{GapSVP}_{p}$ is not in $\mathsf{RP}$ unless
$\mathsf{NP}\subseteq\mathsf{RP}$.

We note that Theorem 1.1 is actually identical to the main result in [Mic98].
As such, it matches the best known $\mathsf{NP}$-hardness of approximation for
$\gamma$-$\mathrm{GapSVP}_{p}$ (i.e., largest $\gamma$) achieved by a “one-
shot” reduction for all sufficiently small $p$, including $p=2$. By “one-
shot,” we mean that the reduction does not amplify the approximation factor
from an initial fixed constant to an arbitrary constant (or more) via
tensoring, as is done in [Kho04, HR07, Mic12]. (It is an interesting question
whether our hard $\gamma$-$\mathrm{GapSVP}_{p}$ instances are amenable to
tensoring; see Section 1.4.)

Although our reduction still uses randomness, we believe that it may be easier
to derandomize than previous reductions, both due to its simplicity, and
because of its close connection to prior work showing hardness of minimum
distance problem on codes via a deterministic reduction [CW09]. To that end,
in Section 5 we also describe two approaches to potentially derandomizing our
reduction, both of which aim to deterministically construct a particular
lattice coset and lower bound the number of short vectors in it (see Section
1.2 for the motivation for this). The first approach is based on Fourier
analysis, using similar techniques to those in [CW09], and the second is based
on “smooth” proxies for point-counting functions.

We also show that a close deterministic analog of our randomized local-density
construction would imply improved explicit Reed-Solomon list-decoding lower
bounds, going beyond the current state of the art from [GR05]. One may
interpret this implication either pessimistically, as a barrier to a very
strong derandomization of our reduction, or optimistically, as a potential
route to improve Reed-Solomon list-decoding lower bounds. Here there is a
further connection between the two problems, in that [GR05] obtains its list-
decoding lower bounds by using the same Fourier-analytic tool underlying one
of our derandomization attempts—specifically, the Weil bound for character
sums (Equation 25). Unfortunately, the Weil bound falls just short of what we
need in our context. (The Weil bound and related techniques were first used
for counting Reed-Solomon code words in [CW04], and were also used in the
deterministic hardness reduction for the minimum distance problem on codes in
[CW09].)

#### Efficient decoding near Minkowski’s bound.

As a separate contribution of independent interest, in Section 4 we give a
polynomial-time algorithm for decoding “Construction A Reed-Solomon lattices”
of rank $n$—the same family of lattices as in our hardness reduction, but
instantiated with different parameters—to a distance within a $O(\sqrt{\log
n})$ factor of Minkowski’s bound.111Minkowski’s bound gives an upper bound on
the “normalized density” of a lattice $\mathcal{L}$. Specifically, it asserts
that $\lambda_{1}^{(2)}(\mathcal{L})\leq\sqrt{n}\cdot\det(\mathcal{L})^{1/n}$
for all rank-$n$ lattices $\mathcal{L}$, where
$\det(\mathcal{L})=\sqrt{\det(B^{T}B)}$ for any basis $B$ of $\mathcal{L}$.
The $O(\sqrt{\log n})$ factor in our result asymptotically matches the best
factor known from prior work [MP22], which is for a different family of
lattices. In fact, we rely on one of the main underlying theorems from that
work, but give a simpler construction and analysis based on individual Reed-
Solomon codes instead of towers of BCH codes.

Let $\mathrm{RS}_{q}[k,S]$ denote the dimension-$k$ Reed-Solomon code over
$\mathbb{F}_{q}$ with evaluation set $S$ (defined below in Equation 3). Note
that $n=q$ is the rank of the lattice $\mathcal{L}$ in the following theorem.

######  Theorem 1.2 (Decoding near Minkowski’s bound, informal).

Let $q$ be prime and let $k:=\lfloor q/(2\log_{2}q)\rfloor\leq q/2$. Then for
the “Construction A Reed-Solomon” lattice
$\mathcal{L}:=\mathrm{RS}_{q}[q-k,\mathbb{F}_{q}]+q\mathbb{Z}^{q}\subseteq\mathbb{Z}^{q}$:

  1. 1.

We have $\Omega(\sqrt{q/\log
q})\leq\lambda_{1}(\mathcal{L})\leq\sqrt{q}\cdot\det(\mathcal{L})^{1/q}\leq
O(\sqrt{q})$, i.e., the minimum distance is within a $O(\sqrt{\log q})$ factor
of Minkowski’s bound.

  2. 2.

There is an algorithm that, on input $q$ and a vector
$\boldsymbol{y}\in\mathbb{R}^{q}$, outputs all lattice vectors
$\boldsymbol{v}\in\mathcal{L}$ satisfying
$\lVert\boldsymbol{y}-\boldsymbol{v}\rVert\leq C\sqrt{k}\approx
C\sqrt{q/(2\log_{2}q)}$ in time polynomial in $q$, for some universal constant
$C>0$.

This result adds to a separate line of work on efficient (list) decoding for
various families of lattices [MN08, GP12, DP19, MP22]. Recently, Ducas and van
Woerden [DvW21] further motivated this study by showing cryptographic
applications of lattices that can be efficiently decoded near Minkowski’s
bound. (However, their application is most compelling when the minimum
distances of both the lattice and its dual are close to Minkowski’s bound,
which is not the case in the present setting.)

###  1.2 Technical Overview

Here we give an overview of the key new elements in the proof of our main
hardness theorem (Theorem 1.1), which are the focus of Section 3. For
concision, we defer the technical aspects of our efficient decoding algorithm
and derandomization attempts to Sections 4 and 5, respectively.

Besides using randomness, another common feature in nearly all prior hardness
results for $\mathrm{GapSVP}_{p}$ is the use of _locally dense lattices_ as
advice (the only exception being [Kho03]). Roughly speaking, a locally dense
lattice for relative distance $\alpha\in(0,1)$ in the $\ell_{p}$ norm is a
lattice $\mathcal{L}$ and a coset $\boldsymbol{x}+\mathcal{L}$ (i.e., the
lattice “shifted by” some vector $\boldsymbol{x}$) such that there are at
least subexponentially many (in the lattice rank) vectors
$\boldsymbol{v}\in\boldsymbol{x}+\mathcal{L}$ satisfying
$\lVert\boldsymbol{v}\rVert_{p}\leq\alpha\cdot\lambda_{1}^{(p)}(\mathcal{L})$.
One may view such a coset $\boldsymbol{x}+\mathcal{L}$ as a “bad”
configuration for list-decoding $\mathcal{L}$ to within relative distance
$\alpha$ in the $\ell_{p}$ norm, because there are many lattice vectors
relatively close to $-\boldsymbol{x}$.222For technical reasons, the formal
definition of local density, given in Definition 2.6, also requires a linear
transform that maps the short vectors in $\boldsymbol{x}+\mathcal{L}$ onto the
set of all binary vectors of a given dimension. Such a transform can be
obtained by random sampling using a probabilistic version of Sauer’s Lemma
(see Theorem 2.7) that is now standard in this context [Ajt98, Mic98].
Therefore, we defer further discussion of this issue to the main body.

Prior works have obtained locally density from a variety of lattice families:
the Schnorr-Adelman prime number lattices [Ajt98, CN98, Mic98]; a variant of
Construction A [Kho04] and Construction D [Mic12] applied to (towers of) BCH
codes; and random sublattices of $\mathbb{Z}^{n}$ and lattices with
exponential kissing number [AS18, BPT22]. In this work, we give a simple
construction of locally dense lattices from Reed-Solomon codes, as described
below.

Our main reduction (Theorem 2.10) shows how to use a locally dense lattice for
relative distance $\alpha$ in the $\ell_{p}$ norm to prove
$\mathsf{NP}$-hardness (via a randomized reduction) of
$\gamma$-$\mathrm{GapSVP}_{p}$ for any constant $\gamma>1/\alpha$. This
reduction is very similar to those from prior works, so for the remainder of
this section we focus on summarizing our new construction of locally dense
lattices.

#### Locally dense lattices from Reed-Solomon codes.

We start with some basic definitions and facts used in our construction.
Recall that the Construction A lattice obtained from a linear code
$\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$ for some prime $q$ is defined as
$\mathcal{L}:=\mathcal{C}+q\mathbb{Z}^{n}$, i.e., an integer vector
$\boldsymbol{z}\in\mathbb{Z}^{n}$ is in the lattice if and only if
$\boldsymbol{z}\bmod q$ is a code word. In fact, it will often be convenient
to work with an equivalent “dual view” of Construction A lattices. Namely, if
$H\in\mathbb{F}_{q}^{k\times n}$ is a parity-check matrix of a linear code
$\mathcal{C}:=\ker(H)\subseteq\mathbb{F}_{q}^{n}$ for prime $q$, then the
_parity-check lattice_ $\mathcal{L}^{\perp}(H)$ obtained from $H$ is defined
as

$\mathcal{L}^{\perp}(H):=\\{\boldsymbol{z}\in\mathbb{Z}^{n}:H\boldsymbol{z}=\boldsymbol{0}\in\mathbb{F}_{q}^{k}\\}=\ker(H)+q\mathbb{Z}^{n}=\mathcal{C}+q\mathbb{Z}^{n}\
\text{.}$ (1)

Such lattices have determinant
$\det(\mathcal{L}^{\perp}(H))=|\mathbb{Z}^{n}/\mathcal{L}^{\perp}(H)|\leq
q^{k}$, with equality exactly when $H$ has full row rank (see Lemma 2.2).

We next define the family of parity-check matrices $H=H_{q}(k,S)$ that we use
to construct our family of locally dense lattices. Such a matrix is
parameterized by a prime $q$, a positive integer $k$, and a set
$S\subseteq\mathbb{F}_{q}$. Letting $s_{0},\ldots,s_{n-1}$ be the elements of
$S$ in some arbitrary order, we define

$H=H_{q}(k,S):=\begin{pmatrix}[l]1&1&1&\cdots&1\\\
s_{0}&s_{1}&s_{2}&\cdots&s_{n-1}\\\
s_{0}^{2}&s_{1}^{2}&s_{2}^{2}&\cdots&s_{n-1}^{2}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
s_{0}^{k-1}&s_{1}^{k-1}&s_{2}^{k-1}&\cdots&s_{n-1}^{k-1}\end{pmatrix}\in\mathbb{F}_{q}^{k\times
n}\ \text{.}$ (2)

That is, $H_{q}(k,S)$ is the transposed Vandermonde matrix whose $(i,s)$th
entry is $s^{i}$, where for convenience we index the rows and columns of
$H_{q}(k,S)$ by $i\in\\{0,\ldots,k-1\\}$ and $s\in S$, respectively, and
define $0^{0}:=1$.

The matrix $H=H_{q}(k,S)$ defined in Equation 2 is a _generator matrix_ of the
dimension-$k$ Reed-Solomon code

$\mathrm{RS}_{q}[k,S]:=\\{(p(s))_{s\in S}:p\in\mathbb{F}_{q}[x],\deg(p)<k\\}$
(3)

over $\mathbb{F}_{q}$ with evaluation set $S$, and hence is a parity-check
matrix of its dual code, which is a so-called _generalized_ Reed-Solomon (GRS)
code (see [Hal, Theorem 5.1.6]). Moreover, in the special case where
$S=\mathbb{F}_{q}$, it turns out that $H_{q}(k,S)$ is a parity-check matrix
for the (ordinary) Reed-Solomon code $\mathrm{RS}_{q}[q-k,\mathbb{F}_{q}]$ of
dimension $q-k$ with evaluation set $S=\mathbb{F}_{q}$. So,
$\mathcal{L}^{\perp}(H_{q}(k,\mathbb{F}_{q}))=\mathrm{RS}_{q}[q-k,\mathbb{F}_{q}]+q\mathbb{Z}^{q}$
is the Construction A lattice corresponding to the Reed-Solomon code
$\mathrm{RS}_{q}[q-k,\mathbb{F}_{q}]$. For simplicity, in this overview we
restrict to these “Construction A Reed-Solomon” lattices by taking
$S=\mathbb{F}_{q}$, but note that our results generalize to any sufficiently
large $S\subseteq\mathbb{F}_{q}$.

It is easy to see that for $k<q$, the GRS code having parity-check matrix $H$
has minimum distance (in the Hamming metric) $k+1$: any $k$ columns of $H$ are
linearly independent, because they form a transposed Vandermonde matrix, while
any $k+1$ obviously are not. Therefore, the corresponding Construction A
lattice $\mathcal{L}:=\ker(H)+q\mathbb{Z}^{q}$ has minimum distance
$\lambda_{1}^{(1)}(\mathcal{L})\geq k+1$ in the $\ell_{1}$ norm. The key to
our local density construction and its $\alpha\approx 1/2^{1/p}$ relative
distance is that the $\ell_{1}$ minimum distance is in fact almost _twice_
this large (at least): in Theorem 3.1 we show that
$\lambda_{1}^{(1)}(\mathcal{L})\geq 2k$ when $k\leq q/2$. The proof is short
and elementary, proceeding via Newton’s identities, and is closely related to
the analysis of Craig lattices [Cra] (see Section 1.3).

#### Obtaining a dense coset.

Because the determinant of $\mathcal{L}$ (i.e., the number of its integer
cosets) is $q^{k}$, the pigeonhole principle immediately implies that there
exists an integer coset of $\mathcal{L}$ containing at least
$\binom{q}{h}/q^{k}$ _binary_ vectors in $\\{0,1\\}^{q}$ with Hamming weight
$h$, which have $\ell_{1}$ norm $h$. By setting parameters appropriately, this
yields a coset with subexponentially many vectors of $\ell_{1}$ norm at most
$\alpha\cdot\lambda_{1}^{(1)}(\mathcal{L})$, for any constant $\alpha>1/2$.

More specifically, set
$h:=\alpha\cdot(2k)\leq\alpha\cdot\lambda_{1}^{(1)}(\mathcal{L})$ and
$q\approx k^{1/\varepsilon}$ for some positive constant
$\varepsilon<1-1/(2\alpha)$. (For simplicity, assume that $h$ is an integer.)
Then there must exist an integer coset of $\mathcal{L}$ containing at least

$\frac{\binom{q}{h}}{q^{k}}\geq\Big{(}\frac{q}{h}\Big{)}^{h}\cdot
q^{-k}=\frac{q^{(2\alpha-1)k}}{(2\alpha k)^{2\alpha
k}}\approx\frac{q^{(2\alpha-1)k}}{q^{2\varepsilon\alpha
k}}=q^{(2(1-\varepsilon)\alpha-1)k}=q^{\Omega(k)}=q^{\Omega(q^{\varepsilon})}$
(4)

weight-$h$ binary vectors, which is subexponentially large in $q$.

The above shows the _existence_ of a suitable coset, but following previous
works, it is straightforward to show that a _randomly sampled_ coset from a
suitable distribution is likely to have enough short vectors (see Lemma 3.3).
Indeed, the difference between showing that such a coset exists, versus
sampling one efficiently, versus deterministically computing one efficiently,
is the main technical difference between getting a non-uniform, versus
randomized, versus deterministic hardness reduction (respectively) for
$\mathrm{GapSVP}_{p}$ using these techniques.

The above argument generalizes to arbitrary $\ell_{p}$ norms for finite $p$,
albeit for larger relative distances $\alpha>1/2^{1/p}$. Because $\mathcal{L}$
is integral, $\lambda_{1}^{(1)}(\mathcal{L})\geq 2k$ implies that
$\lambda_{1}^{(p)}(\mathcal{L})\geq(2k)^{1/p}$ for any finite $p\geq 1$.
Moreover, reparameterizing the calculation in Equation 4 by choosing
$\alpha>1/2^{1/p}$ and setting $h:=\alpha^{p}\cdot(2k)$ shows that some coset
of $\mathcal{L}$ contains subexponentially many binary vectors of Hamming
weight $h$, and hence of $\ell_{p}$ norm
$h^{1/p}=\alpha\cdot(2k)^{1/p}\leq\alpha\cdot\lambda_{1}^{(p)}(\mathcal{L})$.
Therefore, this construction yields locally dense lattices in the $\ell_{p}$
norm for any constant relative distance $\alpha>1/2^{1/p}$, which by our main
reduction implies Theorem 1.1, i.e., randomized $\mathsf{NP}$-hardness of
$\gamma$-$\mathrm{GapSVP}_{p}$ for any constant $\gamma<2^{1/p}$.

###  1.3 Additional Related Work

The Construction A Reed-Solomon lattices we use are closely related to a
family of algebraic lattices studied by Craig [Cra] (see also [CS99, Chapter
8, Section 6]), and our proof of Theorem 3.1 is inspired by and very similar
to an argument lower bounding the minimum distance of Craig lattices from
[CS99, Chapter 8, Section 6, Theorem 7].333Specifically, [CS99] considers
Craig lattices obtained from the coefficient vectors of polynomials in
principal ideals of the form $(x-1)^{m}R$ in rings of the form
$R=\mathbb{Z}[x]/(x^{p}-1)$, for some prime $p$ and integer $m\geq 1$. The
original definition of [Cra] is slightly different, and uses the “canonical”
(Minkowski) embedding of such ideals in the ring of integers
$R=\mathbb{Z}[x]/(\Phi_{p}(x))$ of the $p$th cyclotomic number field. In fact,
the guarantees on the minimum distances and determinants of Craig lattices
given there are such that our hardness proof for $\mathrm{GapSVP}$ could be
made to work using Craig lattices instead of Construction A Reed-Solomon
lattices. We have chosen to work with the latter family because they are more
elementary and general, and because of their direct connections to efficient
lattice decoding, list-decoding lower bounds, and derandomization techniques,
as explored in Sections 4 and 5.

We also note that locally dense lattices appear in other work on the
complexity of lattice problems. In particular, all prior $\mathsf{NP}$\- and
fine-grained hardness reductions for the problem of Bounded Distance Decoding
to relative distance $\alpha^{\prime}$ in the $\ell_{p}$ norm
($\alpha^{\prime}$-$\mathrm{BDD}_{p}$) [LLM06, BP20, BPT22], another important
lattice problem, use locally dense lattices. In fact, the smallest
$\alpha^{\prime}$ for which we know how to show $\mathsf{NP}$-hardness of
$\alpha^{\prime}$-$\mathrm{BDD}_{p}$ is essentially the smallest $\alpha(p)$
for which we can construct locally dense lattices for relative distance
$\alpha(p)$ in the $\ell_{p}$ norm.

Additionally, _locally dense codes_ play an analogous role to locally dense
lattices in the complexity of coding problems, and particularly the Minimum
Distance Problem (MDP), which is the analog of $\mathrm{SVP}$ for codes.
Indeed, the work of Micciancio, Dumer, and Sudan [DMS99] adapted the local
density framework to codes and used it to show randomized hardness of
approximation for MDP. This reduction was subsequently made deterministic by
Cheng and Wan [CW09], who, as mentioned above, constructed locally dense codes
from Reed-Solomon codes. Micciancio [Mic14] formalized the locally dense code
framework, gave a simplified deterministic $\mathsf{NP}$-hardness proof for
MDP, and discussed the search for analogous deterministic constructions of
locally dense lattices. (Austrin and Khot [AK11] also gave a simplified
deterministic hardness reduction for MDP, but it does not obviously use the
same framework.)

Finally, with respect to our result in Theorem 1.2, we note that a number of
previous works have given algorithms for efficient decoding near Minkowski’s
bound on other families of lattices. These include [MN08, GP12], which showed
how to (list) decode to a distance within a $O(n^{1/4})$ factor of Minkowski’s
bound on Barnes-Wall lattices; [DP19], which showed how to decode to a
distance within a $O(\log n)$ factor of Minkowski’s bound on a family of
discrete-logarithm lattices; and [MP22], which showed how to (list) decode to
a distance within a $O(\sqrt{\log n})$ factor of Minkowski’s bound on lattices
obtained by applying Construction D to towers of BCH codes.

###  1.4 Open Questions

The obvious question left open by our work is whether our reduction can be
derandomized, using the same family of lattices. Addressing this is the main
focus of Section 5, and we defer further discussion of it to there.

Another interesting question is whether it is possible to amplify the
approximation factor $\gamma$ achieved by our reduction via _tensoring_ , as
is done in previous works [Kho04, HR07, Mic12]. Recall that the tensor product
of lattices $\mathcal{L}_{1},\mathcal{L}_{2}$ having respective bases
$B_{1},B_{2}$ is defined as
$\mathcal{L}_{1}\otimes\mathcal{L}_{2}:=\mathcal{L}(B_{1}\otimes B_{2})$, and
that
$\lambda_{1}(\mathcal{L}_{1}\otimes\mathcal{L}_{2})\leq\lambda_{1}(\mathcal{L}_{1})\cdot\lambda_{1}(\mathcal{L}_{2})$.
To see why tensoring might be useful for gap amplification, observe that if
this bound was an equality, then the $m$-fold tensor product
$\mathcal{L}^{\otimes m}$ of $\mathcal{L}$ with itself would satisfy
$\lambda_{1}(\mathcal{L}^{\otimes m})=\lambda_{1}(\mathcal{L})^{m}$, which
would amplify the approximation factor in an instance of
$\gamma$-$\mathrm{GapSVP}_{p}$ to $\gamma^{m}$. However, this inequality is
_not_ tight in general (see, e.g., [HR07, Lemma 2.3]). Nevertheless, prior
reductions have been able to prove similar inequalities for certain families
of lattices, but it is not immediately obvious how to adapt their techniques
to our setting.

Finally, as previously observed in [BP20], we do not have a good understanding
of the smallest possible relative distance $\alpha^{*}=\alpha^{*}(p)$ for
locally dense lattices in $\ell_{p}$ norms for finite $p>2$. Besides showing
better “one-shot” hardness for $\gamma$-$\mathrm{GapSVP}_{p}$, achieving
smaller factors $\alpha(p)$ for such $p$ (ideally,
$\alpha(p)\approx\alpha^{*}(p)$) would imply improved (randomized)
$\mathsf{NP}$-hardness results for Bounded Distance Decoding (specifically, it
would show hardness of $\alpha^{\prime}$-$\mathrm{BDD}_{p}$ for any
$\alpha^{\prime}>\alpha(p)$). The triangle inequality implies a lower bound of
$\alpha^{*}\geq 1/2$ in any norm, and, as observed in [Mic98], we have
$\alpha^{*}(2)\geq 1/\sqrt{2}$. So, the relative-distance factors
$\alpha(p)\approx 1/2^{1/p}$ for local density achieved by [Mic98] and this
work are essentially optimal for $p=1$ and $p=2$ (and conjecturally for all
$p\in[1,2]$). However, they deteriorate as $p$ increases. On the other hand,
the factors $\alpha(p)$ obtained in [BP20] satisfy
$\lim_{p\to\infty}\alpha(p)=1/2$, and hence are nearly optimal for large $p$,
but are poor even for some $p>2$. In particular, they satisfy
$\alpha(p)<1/\sqrt{2}$ only for $p>p_{1}\approx 4.2773$, even though we
believe that $\alpha(p)<1/\sqrt{2}$ should be achievable for all $p>2$. (We
note in passing that $\alpha(p)\approx 1/\sqrt{2}$ is achievable for _all_ $p$
via norm embeddings [RR06].) It seems plausible that a family similar to our
Construction A Reed-Solomon lattices $\mathcal{L}$—perhaps obtained by
parameterizing the underlying Reed-Solomon code differently, using a different
algebraic code, or by randomly sparsifying $\mathcal{L}$ as in [BP20]—might
achieve this.

#### Acknowledgements.

We thank Swastik Kopparty [Kop20] for very helpful answers to several of our
questions, and for pointing us to the contents of Sections 5.1 and 5.2.

##  2 Preliminaries

Throughout this work we adopt the convention that $0^{0}:=1$ in any ring. For
a positive integer $k$, define $[k]:=\\{0,1,\ldots,k-1\\}$.

In general, every vector or matrix is indexed by some specified set $S$. For
example, $\boldsymbol{x}\in\mathbb{Z}^{S}$ is an integer vector indexed by
$S$, having an entry $x_{s}\in\mathbb{Z}$ for each $s\in S$ (and no other
entries). When the index set is $[n]$ for some non-negative integer $n$, we
usually omit the brackets in the exponent and just write, e.g.,
$\mathbb{Z}^{n}$. We emphasize that in this case the indices start from zero.
An object indexed by a finite set $S$ of size $n=\left|{S}\right|$ can be
reindexed by $[n]$, simply by enumerating $S=\\{s_{0},\ldots,s_{n-1}\\}$ under
some arbitrary order, and identifying index $s_{i}$ with index $i$.

For a finite set $S$ and a positive integer $h\leq\left|{S}\right|$, let
$B_{S,h}:=\\{\boldsymbol{v}\in\\{0,1\\}^{S}:\lVert\boldsymbol{v}\rVert_{1}=h\\}$
be the set of binary vectors indexed by $S$ of Hamming weight $h$. As above,
when $S=[n]$ we often write $B_{n,h}$. Finally, let
$\mathcal{B}_{p}^{n}(r):=\\{\boldsymbol{x}:\lVert\boldsymbol{x}\rVert_{p}\leq
r\\}\subset\mathbb{R}^{n}$ denote the real $n$-dimensional $\ell_{p}$ ball of
radius $r$ centered at the origin.

###  2.1 Basic Lattice Definitions

Given a lattice $\mathcal{L}=\mathcal{L}(B)$ with basis
$B\in\mathbb{R}^{m\times n}$, we define the _rank_ of $\mathcal{L}$ to be $n$
and the (ambient) _dimension_ of $\mathcal{L}$ to be $m$. We denote the
_minimum distance_ of $\mathcal{L}$ in the $\ell_{p}$ norm, which is the
length of a shortest non-zero vector in $\mathcal{L}$, by

$\lambda_{1}^{(p)}(\mathcal{L}):=\min_{\boldsymbol{x}\in\mathcal{L}\setminus\\{0\\}}\lVert\boldsymbol{x}\rVert_{p}\
\text{.}$

The central problem that we study in this work asks about the value of
$\lambda_{1}^{(p)}(\mathcal{L})$ for a given input lattice $\mathcal{L}$.

######  Definition 2.1.

For $p\geq 1$ and $\gamma=\gamma(n)\geq 1$, the decisional,
$\gamma$-approximate Shortest Vector Problem in the $\ell_{p}$ norm
($\gamma$-$\mathrm{GapSVP}_{p}$) is the promise problem defined as follows.
The input consists of a basis $B\in\mathbb{Z}^{m\times n}$ of an integer
lattice $\mathcal{L}$ and a distance threshold $s>0$, and the goal is to
determine whether the input is a YES instance or a NO instance, where these
are defined as follows:

  * •

YES instance: $\lambda_{1}^{(p)}(\mathcal{L})\leq s$.

  * •

NO instance: $\lambda_{1}^{(p)}>\gamma s$.

We define the _determinant_ of $\mathcal{L}$ to be
$\det(\mathcal{L}):=\sqrt{\det(B^{T}B)}$, which is equal to $|\det(B)|$ when
$m=n$ (i.e., when $\mathcal{L}$ is full-rank). We note that determinant is
well defined because, although lattice bases are not unique, they are
equivalent up to multiplication on the right by unimodular matrices.

The density of a rank-$n$ lattice $\mathcal{L}$ is captured by its so-called
_root Hermite factor_
$\lambda_{1}(\mathcal{L})/\det(\mathcal{L})^{1/n}$.444This ratio is the square
root of the Hermite factor
$\gamma(\mathcal{L}):=(\lambda_{1}(\mathcal{L})/\det(\mathcal{L})^{1/n})^{2}$,
which is defined in this way for historical reasons. The density of a lattice
corresponds to its quality in various applications, including as the set of
centers of a sphere packing and as an error-correcting code. Minkowski’s bound
asserts that the root Hermite factor of such a rank-$n$ lattice is at most
$\sqrt{n}$, which is convenient to write in expanded form as

$\lambda_{1}(\mathcal{L})\leq\sqrt{n}\cdot\det(\mathcal{L})^{1/n}\ \text{.}$
(5)

###  2.2 Parity-Check Matrices and Lattices

For a prime $q$ and a matrix $H\in\mathbb{F}_{q}^{k\times n}$, we define the
_parity-check lattice_ $\mathcal{L}^{\perp}(H)$ obtained from $H$ as

$\mathcal{L}^{\perp}(H):=\\{\boldsymbol{z}\in\mathbb{Z}^{n}:H\boldsymbol{z}=\boldsymbol{0}\\}=\ker(H)+q\mathbb{Z}^{n}\
\text{.}$ (6)

Note that $\mathcal{L}^{\perp}(H)$ is simply the “Construction A” lattice
[CS99, Chapter 5, Section 2] of the linear error-correcting code $\mathcal{C}$
having $H$ as a parity-check matrix, i.e.,
$\mathcal{C}=\\{\boldsymbol{c}\in\mathbb{F}_{q}^{n}:H\boldsymbol{c}=\boldsymbol{0}\\}$.
More generally, for any “syndrome” $\boldsymbol{u}\in\mathbb{F}_{q}^{k}$ we
define

$\mathcal{L}^{\perp}_{\boldsymbol{u}}(H):=\\{\boldsymbol{x}\in\mathbb{Z}^{n}:H\boldsymbol{x}=\boldsymbol{u}\\}\
\text{.}$

If there exists some $\boldsymbol{x}\in\mathbb{Z}^{n}$ such that
$H\boldsymbol{x}=\boldsymbol{u}$, then it follows immediately that
$\mathcal{L}^{\perp}_{\boldsymbol{u}}(H)$ is simply the lattice coset
$\boldsymbol{x}+\mathcal{L}^{\perp}(H)$. So, we can identify cosets of
$\mathcal{L}^{\perp}(H)$ by their corresponding syndromes. We recall some
standard properties of parity-check lattices, and give a proof for self-
containment.

######  Lemma 2.2.

Let $q$ be a prime, let $k$ and $n$ be positive integers, and let
$H\in\mathbb{F}_{q}^{k\times n}$ be a parity-check matrix. Then the parity-
check lattice $\mathcal{L}=\mathcal{L}^{\perp}(H)$ has rank $n$ and
determinant $\det(\mathcal{L})\leq q^{k}$, with equality if and only if the
rows of $H$ are linearly independent.

###### Proof.

The first claim follows simply by noting that
$q\mathbb{Z}^{n}\subseteq\mathcal{L}^{\perp}(H)\subseteq\mathbb{Z}^{n}$. For
the determinant, observe that the map $\boldsymbol{x}\mapsto H\boldsymbol{x}$
is an additive-group homomorphism from $\mathbb{Z}^{n}$ to
$\mathbb{F}_{q}^{k}$, and that $\mathcal{L}^{\perp}(H)$ is its kernel by
definition. So, by the first isomorphism theorem, the map induces an
isomorphism from the quotient group $\mathbb{Z}^{n}/\mathcal{L}^{\perp}(H)$ to
the image
$\operatorname{Im}(H)=\\{H\boldsymbol{x}:\boldsymbol{x}\in\mathbb{Z}^{n}\\}\subseteq\mathbb{F}_{q}^{k}$,
where the subset relation is an equality if and only if the rows of $H$ are
linearly independent. The claim then follows from the fact that
$\det(\mathcal{L}^{\perp}(H))=\left|{\mathbb{Z}^{n}/\mathcal{L}^{\perp}(H)}\right|=\left|{\operatorname{Im}(H)}\right|$.
∎

We next formally define the family of parity-check lattices that are at the
heart of our construction of locally dense lattices.

######  Definition 2.3.

For a prime $q$, positive integer $k$, and set $S\subseteq\mathbb{F}_{q}$,
define $H_{q}(k,S)\in\mathbb{F}_{q}^{k\times S}$ to be the matrix $H$ whose
rows and columns are respectively indexed by $[k]=\\{0,1,\ldots,k-1\\}$ and
$S$, and whose $(i,s)$th entry is

$H_{i,s}:=s^{i}\in\mathbb{F}_{q}\ \text{.}$

(Recall that $0^{0}:=1$.) Equivalently, if we enumerate
$S=\\{s_{0},\ldots,s_{n-1}\\}$ in some arbitrary order, we have

$H=H_{q}(k,S):=\begin{pmatrix}[l]1&1&1&\cdots&1\\\
s_{0}&s_{1}&s_{2}&\cdots&s_{n-1}\\\
s_{0}^{2}&s_{1}^{2}&s_{2}^{2}&\cdots&s_{n-1}^{2}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
s_{0}^{k-1}&s_{1}^{k-1}&s_{2}^{k-1}&\cdots&s_{n-1}^{k-1}\end{pmatrix}\in\mathbb{F}_{q}^{k\times
n}\ \text{.}$ (7)

Notice that $H$ is a transposed Vandermonde matrix. In particular, if $k\leq
n$ then its rows are linearly independent, and so
$\det(\mathcal{L}^{\perp}(H))=q^{k}$ by Lemma 2.2.

We recall from the introduction that $H=H_{q}(k,S)$ is a generator matrix (of
row vectors) of the dimension-$k$ Reed-Solomon code over $\mathbb{F}_{q}$ with
evaluation set $S$, and hence $H$ is a parity-check matrix of its
dimension-$(n-k)$ dual code. So, $\mathcal{L}^{\perp}(H)$ is the Construction
A lattice of this dual code. These dual codes are in fact _generalized Reed-
Solomon codes_ , a family of codes that include Reed-Solomon codes as a
special case and that are closed under taking duals (see [Hal, Theorem
5.1.6]). Moreover, in the special case where $S=\mathbb{F}_{q}$, the matrix
$H=H_{q}(k,\mathbb{F}_{q})$ is in fact a parity-check matrix of an (ordinary)
Reed-Solomon code. For our hardness proof it suffices to use this special
case; i.e., we show $\mathsf{NP}$-hardness (under a randomized reduction) of
$\mathrm{GapSVP}$ by using Construction A lattices of (ordinary) Reed-Solomon
codes as gadgets. See Section 4 and Section 5.1 for other connections between
these lattices and Reed-Solomon codes.

###  2.3 Symmetric Polynomials

A _symmetric polynomial_ $P(x_{1},x_{2},\ldots,x_{m})$ is a polynomial that is
invariant under any permutation of its variables, i.e.,
$P(x_{1},\ldots,x_{m})=P(x_{\pi(1)},\ldots,x_{\pi(m)})$ as formal polynomials
for all permutations $\pi$ of $\\{1,2,\ldots,m\\}$. Because the order of the
variables is immaterial, we usually just write a symmetric polynomial as
$P(X)$, where $X=\\{x_{1},\ldots,x_{m}\\}$ is the set of variables, and we
write $P(T)$ for its evaluation on a multiset $T$ of values.

We next recall two important symmetric polynomials and the relationship
between them. For a non-negative integer $i$, the $i$th _power sum_ of a set
$X$ of variables is defined as

$p_{i}(X):=\sum_{x\in X}x^{i}\ \text{.}$ (8)

(Recall that $0^{0}:=1$.) For $1\leq i\leq\left|{X}\right|$, the $i$th
_elementary symmetric polynomial_ of $X$ is defined as

$e_{i}(X):=\sum_{\begin{subarray}{c}Z\subseteq X,\\\
\left|{Z}\right|=i\end{subarray}}\;\prod_{z\in Z}z\ \text{.}$ (9)

That is, $e_{i}(X)$ is the multilinear polynomial whose monomials consist of
all products of $i$ distinct variables from $X$. We extend this definition to
$i=0$ by setting $e_{0}(X):=1$ and to integers $i>\left|{X}\right|$ by setting
$e_{i}(X):=0$.

Power sums and elementary symmetric polynomials are related by _Newton’s
identities_ (see, e.g., [Mea92]), which assert that for $1\leq
i\leq\left|{X}\right|$,

$i\cdot e_{i}(X)=\sum_{j=1}^{i}(-1)^{j-1}\cdot e_{i-j}(X)\cdot p_{j}(X)\
\text{.}$ (10)

The following standard claim uses Newton’s identities to show that if the
first $k$ power sums of two _multisets_ of field elements coincide, then so do
the first $k$ elementary symmetric polynomials of those multisets.

######  Claim 2.4.

Let $T,U$ be multisets over a prime field $\mathbb{F}_{q}$, let $k\leq q$ be a
positive integer, and suppose that $p_{i}(T)=p_{i}(U)$ for all $i\in[k]$. Then
$e_{i}(T)=e_{i}(U)$ for all $i\in[k]$.

###### Proof.

The proof is by (strong) induction. For the base case where $i=0$, we have by
definition that $e_{0}(T)=e_{0}(U)=1$. For the inductive case where $1\leq
i<k$, because $i\neq 0\in\mathbb{F}_{q}$ we have that

$e_{i}(T)=i^{-1}\cdot\sum_{j=1}^{i}(-1)^{j-1}\cdot e_{i-j}(T)\cdot
p_{j}(T)=i^{-1}\cdot\sum_{j=1}^{i}(-1)^{j-1}\cdot e_{i-j}(U)\cdot
p_{j}(U)=e_{i}(U)\ \text{,}$

where the first and third equalities follow from Newton’s identities (Equation
10), and the second equality follows from the claim’s hypothesis and the
inductive hypothesis (note that the sums involve elementary symmetric
polynomials $e_{i-j}$ only for $i-j<i$). ∎

We define the _root polynomial_ $f_{T}(x)\in\mathbb{F}[x]$ of a multiset $T$
over a field $\mathbb{F}$ to be

$f_{T}(x):=\prod_{t\in T}(x-t)=\sum_{i=0}^{\left|{T}\right|}(-1)^{i}\cdot
e_{i}(T)\cdot x^{\left|{T}\right|-i}\ \text{.}$ (11)

We then get the following result, which uses 2.4 to show that if sufficiently
many of the initial power sums of two multisets are equal, then the multisets
themselves are equal.

######  Proposition 2.5.

Let $q$ be a prime, let $k\leq q/2$ be a positive integer, let $T,U$ be
multisets over $\mathbb{F}=\mathbb{F}_{q}$ of total cardinality
$\left|{T}\right|+\left|{U}\right|<2k$, and suppose that $p_{i}(T)=p_{i}(U)$
for all $i\in[k]$. Then $T=U$.

###### Proof.

Because

$\left|{T}\right|\equiv p_{0}(T)=p_{0}(U)\equiv\left|{U}\right|\pmod{q}$

and $0\leq\left|{T}\right|+\left|{U}\right|<2k\leq q$, it follows that
$\left|{T}\right|=\left|{U}\right|$ and hence both $f_{T}(x),f_{U}(x)$ have
degree $\left|{T}\right|<k$.

Next, by the hypotheses and 2.4, we have that $e_{i}(T)=e_{i}(U)$ for all
$i\leq\left|{T}\right|$. Therefore, by the equality in Equation 11, $f_{T}(x)$
and $f_{U}(x)$ are identical as formal polynomials in $\mathbb{F}[x]$.
Finally, because the polynomial ring $\mathbb{F}[x]$ is a unique factorization
domain, and because $f_{T}(x)$ and $f_{U}(x)$ split over $\mathbb{F}$ by
construction, it follows that $T=U$. ∎

###  2.4 Locally Dense Lattices

Roughly speaking, _locally dense lattices_ are lattices that have one or more
cosets with many relatively short vectors. Somewhat more precisely, a locally
dense lattice consists of an integer lattice
$\mathcal{L}\subset\mathbb{Z}^{n}$ and a shift
$\boldsymbol{x}\in\mathbb{Z}^{n}$ such that for some $\alpha\in(0,1)$, the
number of points in the coset $\boldsymbol{x}+\mathcal{L}$ of norm at most
$\alpha\cdot\lambda_{1}(\mathcal{L})$ is large (for our purposes, greater than
$2^{n^{\varepsilon}}$ for some constant $\varepsilon>0$). Therefore, locally
dense lattices are not efficiently list decodable, even combinatorially, to
within distance $\alpha\cdot\lambda_{1}(\mathcal{L})$ in the worst case (in
particular, around center $-\boldsymbol{x}$). For the purposes of proving
hardness, we also require a linear map $T$ that projects the short vectors in
$\boldsymbol{x}+\mathcal{L}$ onto a lower-dimensional hypercube
$\\{0,1\\}^{r}$.

######  Definition 2.6.

For $p\in[1,\infty)$, real $\alpha>0$, and positive integers $r$ and $R$, a
$(p,\alpha,r,R)$-_locally dense lattice_ consists of an integer lattice of
rank $R$ (and some dimension $n$) represented by a basis matrix
$A\in\mathbb{Z}^{n\times R}$, a positive integer $\ell$, a shift
$\boldsymbol{x}\in\mathbb{Z}^{n}$, and a matrix $T\in\mathbb{Z}^{r\times n}$,
where

  1. 1.

$\lambda_{1}^{(p)}(\mathcal{L}(A))\geq\ell^{1/p}$ and

  2. 2.

$\\{0,1\\}^{r}\subseteq T(V):=\\{T\boldsymbol{v}:\boldsymbol{v}\in V\\}$,
where
$V:=(\boldsymbol{x}+\mathcal{L}(A))\cap\mathcal{B}_{p}^{n}(\alpha\cdot\ell^{1/p})$
is the set of all vectors of $\ell_{p}$ norm at most $\alpha\cdot\ell^{1/p}$
in the lattice coset $\boldsymbol{x}+\mathcal{L}(A)$.

A useful tool for satisfying Item 2 in the above definition is the following
probabilistic version of Sauer’s Lemma due to Micciancio [Mic98]. It roughly
says that for $n\gg r$, for any large enough collection of vectors $W\subseteq
B_{n,h}$ (the weight-$h$ slice of $\\{0,1\\}^{n}$), and for a random matrix
$T\in\\{0,1\\}^{r\times n}$ whose coordinates are sampled independently with a
suitable bias, $\\{0,1\\}^{r}\subseteq T(W)$ with good probability. We
emphasize that all the arithmetic in this theorem is done over the integers
(not over $\mathbb{F}_{2}$).

######  Theorem 2.7 ([Mic98, Theorem 4]).

Let $r,n,h$ be positive integers, let $W\subseteq B_{n,h}$, and let
$\varepsilon>0$. If $\left|{W}\right|\geq h!\cdot n^{24r\sqrt{h}/\varepsilon}$
and $T\in\\{0,1\\}^{r\times n}$ is sampled by setting each entry to $1$
independently with probability $1/(4hr)$, then $\\{0,1\\}^{r}\subseteq T(W)$
with probability at least $1-\varepsilon$.

###  2.5 Hardness of $\mathrm{GapSVP}$ via Locally Dense Lattices

We next recall a variant of (the decision version of) the Closest Vector
Problem (CVP), which will be the hard problem that we reduce to
$\mathrm{GapSVP}_{p}$. In this variant, called $\mathrm{GapCVP}^{\prime}_{p}$,
the target vector is either within a specified distance of a lattice vector
given by a _binary_ combination of basis vectors, or _all non-zero integer
multiples_ of the target vector are more than a $\gamma$ multiple of this
distance from the lattice (where distance is measured in the $\ell_{p}$ norm).

######  Definition 2.8.

For $p\in[1,\infty]$, an instance of the
$\gamma$-$\mathrm{GapCVP}^{\prime}_{p}$ problem consists of a rank-$r$ lattice
basis $B\in\mathbb{Z}^{d\times r}$, a target vector
$\boldsymbol{t}\in\mathbb{Z}^{d}$, and a distance threshold $s>0$. The goal is
to determine whether an input is a YES instance or a NO instance, where these
are defined as follows:

  * •

YES instance: there exists a _binary_ $\boldsymbol{c}\in\\{0,1\\}^{r}$ such
that $\lVert B\boldsymbol{c}-\boldsymbol{t}\rVert_{p}\leq s$.

  * •

NO instance: $\mathrm{dist}_{p}(w\boldsymbol{t},\mathcal{L}(B))>\gamma s$ for
all $w\in\mathbb{Z}\setminus\\{0\\}$.

The following hardness theorem follows via a reduction from Exact Set Cover to
$\mathrm{GapCVP}^{\prime}_{p}$.

######  Theorem 2.9 ([ABSS93]).

For every $p\in[1,\infty)$ and every constant $\gamma\geq 1$,
$\gamma$-$\mathrm{GapCVP}^{\prime}_{p}$ is $\mathsf{NP}$-hard.

The following theorem gives a polynomial-time reduction from
$\gamma$-$\mathrm{GapCVP}^{\prime}_{p}$ to
$\gamma^{\prime}$-$\mathrm{GapSVP}_{p}$ for some approximation factors
$\gamma>\gamma^{\prime}\geq 1$, which uses a locally dense lattice as advice.
In general, this advice makes the reduction non-uniform, but when the advice
is efficiently computable by a (randomized) algorithm, as it is in this and
prior works, the procedure is an efficient (randomized) reduction. The
reduction below is very similar to the one in [Mic12, Theorem 5.1], but
written so as to allow for using an arbitrary locally dense lattice as advice.
Due to this similarity, and for concision, we defer its proof to Appendix A.

######  Theorem 2.10.

Let $p\geq 1$, $r$ and $n$ be positive integers, $\alpha>0$ be a constant, and
$\gamma,\gamma^{\prime}$ be constants satisfying

$1/\alpha>\gamma^{\prime}\geq 1\text{ and
}\gamma\geq\gamma^{\prime}\cdot\Big{(}\frac{1}{1-(\alpha\gamma^{\prime})^{p}}\Big{)}^{1/p}\
\text{.}$

There is a deterministic polynomial-time algorithm that, given a
$\gamma$-$\mathrm{GapCVP}^{\prime}_{p}$ instance $(B,\boldsymbol{t},s)$ of
rank $r$ and a $(p,\alpha,r,R)$-locally dense lattice
$(A,\ell,\boldsymbol{x},T)$ as input, outputs a
$\gamma^{\prime}$-$\mathrm{GapSVP}_{p}$ instance $(B^{\prime},s^{\prime})$ of
rank $R+1$ which is a YES (respectively, NO) instance if
$(B,\boldsymbol{t},s)$ is a YES (resp., NO) instance.

From these two theorems we get the following hardness results for
$\mathrm{GapSVP}$.

######  Corollary 2.11.

Let $p\geq 1$, let $r$ be a positive integer, let $\alpha>0$ be a constant,
and suppose that there is an algorithm $A$ that computes a
$(p,\alpha,r,\operatorname{poly}(r))$-locally dense lattice in
$\operatorname{poly}(r)$ time. Let $\gamma$ be a constant satisfying
$1\leq\gamma<1/\alpha$. Then:

  1. 1.

If $A$ is deterministic, then $\gamma$-$\mathrm{GapSVP}_{p}$ is
$\mathsf{NP}$-hard (and exact $\mathrm{GapSVP}_{p}$ is
$\mathsf{NP}$-complete).

  2. 2.

If $A$ is randomized and its output satisfies Item 1 of Definition 2.6 with
probability $1$ and Item 2 of Definition 2.6 with probability at least $2/3$,
then $\gamma$-$\mathrm{GapSVP}_{p}$ is not in $\mathsf{RP}$ unless
$\mathsf{NP}\subseteq\mathsf{RP}$.555The condition
“$\gamma$-$\mathrm{GapSVP}_{p}$ is not in $\mathsf{RP}$” is a slight abuse of
notation, since $\gamma$-$\mathrm{GapSVP}_{p}$ for $\gamma>1$ is a promise
problem rather than a language. However, the definition of $\mathsf{RP}$ can
naturally be extended to encompass promise problems, which is the intended
meaning here.

  3. 3.

If $A$ is randomized, and its output satisfies Items 1 and 2 of Definition 2.6
with probability at least $2/3$, then there is no _randomized_ polynomial-time
algorithm for $\gamma$-$\mathrm{GapSVP}_{p}$ unless
$\mathsf{NP}\subseteq\mathsf{BPP}$.

###### Proof.

Items 1 and 3 follow immediately by combining Theorems 2.9 and 2.10.
Inspection of the proof of Theorem 2.10 shows that for NO instances to be
mapped to NO instances, only Item 1 of Definition 2.6 is needed, from which
Item 2 of the claim follows. ∎

##  3 Local Density from Reed-Solomon Codes

In this section we show how to obtain locally dense lattices from Reed-Solomon
codes with appropriate parameters. More specifically, we show to satisfy
Definition 2.6 using a lattice $\mathcal{L}:=\mathcal{L}^{\perp}(H)$
corresponding to a parity-check matrix $H=H_{q}(k,S)$ from Definition 2.3.
(Recall that $H$ is the parity-check matrix of a Reed-Solomon code when
$S=\mathbb{F}_{q}$, and of a generalized Reed-Solomon code for any
$S\subseteq\mathbb{F}_{q}$.)

The overall structure of the argument is as follows. First, in Section 3.1 we
give a lower bound of $\lambda_{1}^{(p)}(\mathcal{L})\geq(2k)^{1/p}$, which
corresponds to Item 1 of Definition 2.6, by using the connection between power
sums and symmetric polynomials (see Section 2.3). Then, in Section 3.2 we use
the upper bound $\det(\mathcal{L})\leq q^{k}$ from Lemma 2.2 and the
pigeonhole principle to show that there exists a lattice coset with many short
(binary) vectors, and in fact a suitably sampled random coset has this
property with good probability. Finally, in Section 3.3 we set parameters and
use Theorem 2.7 to satisfy Item 2 of Definition 2.6 with good probability.

###  3.1 Minimum Distance

The following theorem says that for any $k\leq\left|{S}\right|/2$, the
$\ell_{1}$ minimum distance of $\mathcal{L}=\mathcal{L}^{\perp}(H)$ for
$H=H_{q}(k,S)$ is at least $2k$. The theorem and proof are very similar to one
that lower bounds the minimum distance of Craig lattices, as given in [Cra]
and [CS99, Chapter 8, Theorem 7].

Note that a weaker bound of $\lambda_{1}^{(1)}(\mathcal{L})\geq k+1$ (for any
$k<q$) follows trivially from the minimum Hamming distance $k+1$ of the
(generalized Reed-Solomon) code having parity-check matrix $H$. However, this
bound is not strong enough for the rest of the local-density argument below,
which requires $\lambda_{1}^{(1)}(\mathcal{L})\geq(1+\Omega(1))k$.

######  Theorem 3.1.

Let $q$ be a prime, let $S\subseteq\mathbb{F}_{q}$, let
$k\leq\left|{S}\right|/2$ be a positive integer, and let
$H:=H_{q}(k,S)\in\mathbb{F}_{q}^{k\times S}$ be the matrix from Definition
2.3. Then $\mathcal{L}=\mathcal{L}^{\perp}(H)$ has $\ell_{1}$ minimum distance
$\lambda^{(1)}_{1}(\mathcal{L})\geq 2k$.

As a consequence, for any $p\in[1,\infty)$ the $\ell_{p}$ minimum distance
satisfies $\lambda_{1}^{(p)}(\mathcal{L})\geq(2k)^{1/p}$.

We point out that the $2^{1/p}$ factor in Theorem 3.1 propagates to the
relative-distance bound for local density in Theorem 3.4 below, and then to
the $\mathrm{GapSVP}$ approximation factor in our main hardness theorem,
Theorem 1.1.

###### Proof.

The consequence follows immediately from the fact that
$\mathcal{L}\subseteq\mathbb{Z}^{S}$ and
$\lVert\boldsymbol{v}\rVert_{p}\geq\lVert\boldsymbol{v}\rVert_{1}^{1/p}$ for
all $\boldsymbol{v}\in\mathbb{Z}^{S}$.

Now consider some arbitrary
$\boldsymbol{x}\in\mathcal{L}\subseteq\mathbb{Z}^{S}$ for which
$\lVert\boldsymbol{x}\rVert_{1}<2k$; we will show that
$\boldsymbol{x}=\boldsymbol{0}$. Let
$\boldsymbol{x}^{+},\boldsymbol{x}^{-}\in\mathbb{Z}^{S}$ be the unique non-
negative integer vectors satisfying
$\boldsymbol{x}=\boldsymbol{x}^{+}-\boldsymbol{x}^{-}$. Define multisets
$T^{+}$ and $T^{-}$ over $S$ that respectively depend on $\boldsymbol{x}^{+}$
and $\boldsymbol{x}^{-}$ as follows. For each $s\in S$ with $x_{s}^{+}>0$
(respectively, $x_{s}^{-}>0$), let $T^{+}$ (respectively, $T^{-}$) contain $s$
with multiplicity $x_{s}^{+}$ (respectively, $x_{s}^{-}$).666For example, if
$S=\\{0,1,2,3,4\\}=\mathbb{F}_{q}$ and
$\boldsymbol{x}=(x_{0},x_{1},x_{2},x_{3},x_{4})^{t}=(1,-2,0,1,0)^{t}$, then
$x^{+}=(1,0,0,1,0)$, $x^{-}=(0,2,0,0,0)$, and accordingly $T^{+}=\\{0,3\\}$,
$T^{-}=\\{1,1\\}$.

Note that
$\left|{T^{+}}\right|+\left|{T^{-}}\right|=\lVert\boldsymbol{x}\rVert_{1}<2k$.
Because
$H\boldsymbol{x}=H(\boldsymbol{x}^{+}-\boldsymbol{x}^{-})=\boldsymbol{0}\in\mathbb{F}_{q}^{k}$,
by definition of $H$ we have that $p_{i}(T^{+})=p_{i}(T^{-})$ for all
$i\in[k]$ (where recall that $p_{i}$ denotes the $i$th power sum). Because
$k\leq\left|{S}\right|/2\leq q/2$, by Proposition 2.5 it follows that
$T^{+}=T^{-}$. Since $T^{+}\cap T^{-}=\emptyset$ by construction, we must have
$T^{+}=T^{-}=\emptyset$, and hence $\boldsymbol{x}=\boldsymbol{0}$, as
desired. ∎

The following lemma (which is well known in other forms) shows that the lower
bound $\lambda_{1}^{(p)}(\mathcal{L}^{\perp}(H))\geq(2k)^{1/p}$ from Theorem
3.1 is in fact an equality under mild conditions on the parameters, by giving
an explicit lattice coset that has multiple short vectors. However, because it
proves only that the number of such vectors is polynomial in the dimension, it
is insufficient to establish local density.

######  Lemma 3.2.

Let $q$ be a prime, let $k$ be a positive integer that divides $q-1$, and let
$H:=H_{q}(k,S)\in\mathbb{F}_{q}^{k\times S}$ where
$\mathbb{F}_{q}^{*}\subseteq S\subseteq\mathbb{F}_{q}$. Then for
$\boldsymbol{u}:=(k,0,\ldots,0)\in\mathbb{F}_{q}^{k}$, the lattice coset
$\mathcal{L}^{\perp}_{\boldsymbol{u}}(H)=\\{\boldsymbol{x}\in\mathbb{Z}^{S}:H\boldsymbol{x}=\boldsymbol{u}\\}$
contains $(q-1)/k$ binary vectors of Hamming weight $k$ and pairwise disjoint
support. As a consequence, when $k<q-1$, we have
$\lambda_{1}^{(p)}(\mathcal{L}^{\perp}(H))=(2k)^{1/p}$ for any
$p\in[1,\infty)$.

###### Proof.

Let $G$ be the order-$k$ subgroup of the (cyclic, multiplicative) group
$\mathbb{F}_{q}^{*}$, i.e., the subgroup of the $k$th roots of unity. Then the
binary indicator vectors $\boldsymbol{x}_{C}\in\\{0,1\\}^{S}$ of each of the
$(q-1)/k$ pairwise disjoint cosets $C=cG$ of $G$ all belong to the coset
$\mathcal{L}^{\perp}_{\boldsymbol{u}}(H)$. This is simply because for any such
coset, the $0$th power sum of its elements is $k$, and the $i$th power sum for
$0<i<k$ is zero; this can be seen by Newton’s identities and the fact that the
root polynomial of $C$ is $f_{C}(x)=\prod_{c\in C}(x-c)=x^{k}-r_{C}$, where
$r_{C}=c^{k}$ for every $c\in C$. Finally, when $k<q-1$, there is more than
one such vector $\boldsymbol{x}_{C}$, and the differences between distinct
pairs of them are lattice vectors in $\\{0,\pm 1\\}^{S}$ of Hamming weight
$2k$, and hence $\ell_{p}$ norm $(2k)^{1/p}$. ∎

###  3.2 Dense Cosets

Following an approach previously used in [Mic98, Kho04, Mic12] (and implicitly
in [Ajt98]), we first show via a pigeonhole argument that a dense lattice
coset must exist, and then show how to sample such a coset efficiently (with
good probability).

For a prime $q$, a positive integer $k$, and a set $S\subseteq\mathbb{F}_{q}$
of size $n$ (with some arbitrary ordering of its elements), let
$H=H_{q}(k,S)\in\mathbb{F}_{q}^{k\times n}$ be the parity-check matrix from
Definition 2.3. By Lemma 2.2, the lattice
$\mathcal{L}=\mathcal{L}^{\perp}(H)\subseteq\mathbb{Z}^{n}$ has
$\det(\mathcal{L})\leq q^{k}$ integer cosets. Recall that $B_{n,h}$ is the set
of $n$-dimensional binary vectors of Hamming weight $h$, which has cardinality
$\left|{B_{n,h}}\right|=\binom{n}{h}$. Therefore, by the pigeonhole principle,
there must exist some integer coset $\boldsymbol{x}+\mathcal{L}$ with
$\left|{(\boldsymbol{x}+\mathcal{L})\cap
B_{n,h}}\right|\geq\binom{n}{h}/q^{k}$ weight-$h$ binary vectors. In
particular, taking $n\approx q$, $h\approx\alpha^{p}\cdot(2k)$ for some
constant $\alpha>1/2^{1/p}$, and $k=q^{\varepsilon}$ for a suitable small
constant $\varepsilon>0$ implies the existence of a coset with roughly
$q^{(2\alpha^{p}-1)k}=q^{\Omega(q^{\varepsilon})}$ such vectors. These vectors
have $\ell_{p}$ norm $h^{1/p}\approx\alpha\cdot(2k)^{1/p}$, whereas by Theorem
3.1 the lattice minimum distance is at least $(2k)^{1/p}$, yielding a local-
density relative distance of roughly $\alpha$.

The following lemma extends the above existential result by showing that
something very similar holds for a _uniformly random_ shift $\boldsymbol{x}\in
B_{n,h}$: for any $\delta>0$, the coset $\boldsymbol{x}+\mathcal{L}$ contains
at least $\delta\cdot\binom{n}{h}/q^{k}$ weight-$h$ binary vectors with
probability greater than $1-\delta$. The proof given below closely follows the
structure of the very similar one of [Kho04, Lemma 4.3].

######  Lemma 3.3.

For a prime $q$, positive integer $k$, and set $S\subseteq\mathbb{F}_{q}$ of
size $n$, let $H=H_{q}(k,S)\in\mathbb{F}_{q}^{k\times n}$ be the parity-check
matrix from Definition 2.3. There is an efficient randomized algorithm that,
for any $\delta\geq 0$, and on input $H$ and any $h\in[n]$, outputs a shift
$\boldsymbol{x}\in B_{n,h}$ such that

$\Pr_{\boldsymbol{x}}\Big{[}\left|{(\boldsymbol{x}+\mathcal{L})\cap
B_{n,h}}\right|\geq\delta\cdot\binom{n}{h}/q^{k}\Big{]}>1-\delta\ \text{.}$

###### Proof.

The algorithm simply samples and outputs a uniformly random binary vector
$\boldsymbol{x}\in B_{n,h}$. This is clearly efficient. To show correctness,
we will use the syndromes of $H$. For each
$\boldsymbol{u}\in\mathbb{F}_{q}^{k}$, define
$K_{\boldsymbol{u}}:=\left|{\\{\boldsymbol{z}\in
B_{n,h}:H\boldsymbol{z}=\boldsymbol{u}\\}}\right|$, and define
$\boldsymbol{s}:=H\boldsymbol{x}\in\mathbb{F}_{q}^{k}$ to be the syndrome
corresponding to $\boldsymbol{x}$. So, we need to prove that
$K_{\boldsymbol{s}}\geq\delta\cdot\binom{n}{h}/q^{k}$ with probability greater
than $1-\delta$. Indeed, we have:

$\displaystyle\Pr_{\boldsymbol{x}}\Big{[}\left|{(\boldsymbol{x}+\mathcal{L})\cap
B_{n,h}}\right|<\delta\cdot\binom{n}{h}/q^{k}\Big{]}$
$\displaystyle=\Pr_{\boldsymbol{x}}\Big{[}K_{\boldsymbol{s}}<\delta\cdot\binom{n}{h}/q^{k}\Big{]}$
$\displaystyle=\sum_{\boldsymbol{u}\in\mathbb{F}_{q}^{k}:K_{\boldsymbol{u}}<\delta\cdot\binom{n}{h}/q^{k}}\Pr_{\boldsymbol{x}}[H\boldsymbol{x}=\boldsymbol{u}]$
$\displaystyle=\sum_{\boldsymbol{u}\in\mathbb{F}_{q}^{k}:K_{\boldsymbol{u}}<\delta\cdot\binom{n}{h}/q^{k}}\frac{K_{\boldsymbol{u}}}{\binom{n}{h}}$
$\displaystyle<\sum_{\boldsymbol{u}\in\mathbb{F}_{q}^{k}:K_{\boldsymbol{u}}<\delta\cdot\binom{n}{h}/q^{k}}\frac{\delta}{q^{k}}$
$\displaystyle\leq\delta\ ,$

where the first inequality uses the fact that the sum is over syndromes
$\boldsymbol{u}$ with $K_{\boldsymbol{u}}<\delta\cdot\binom{n}{h}/q^{k}$, and
the second inequality uses the fact that there are at most $q^{k}$ terms in
the sum. ∎

###  3.3 The Main Argument

######  Theorem 3.4 (Locally dense lattices from Reed-Solomon codes).

For any $p\in[1,\infty)$ and constant $\alpha>1/2^{1/p}$, there exists a
randomized polynomial-time algorithm that, given any sufficiently large
positive integer $r$ in unary as input, outputs a
$(p,\alpha,r,R=\operatorname{poly}(r))$-locally dense lattice (Definition 2.6)
with probability at least $2/3$. Moreover, the algorithm’s output satisfies
Item 1 of Definition 2.6 with probability $1$.

###### Proof.

The algorithm starts by setting its parameters as follows. It sets
$\varepsilon:=2\alpha^{p}-1>0$, and chooses:

  * •

a $\operatorname{poly}(r)$-bounded integer $k\geq r^{1/(1/2-\delta)}$ for some
arbitrary constant $\delta\in(0,1/2)$, and

  * •

a $\operatorname{poly}(r)$-bounded prime $q\geq
k^{3(1+\varepsilon)/\varepsilon}$. (Such a prime $q$ always exists by
Bertrand’s Postulate.)

The algorithm then computes the components of a $(p,\alpha,r,R=q)$-locally
dense lattice $(A,\ell,\boldsymbol{x},T)$ as follows. It lets:

  * •

$A\in\mathbb{Z}^{q\times q}$ be a basis of
$\mathcal{L}:=\mathcal{L}^{\perp}(H)$, where
$H=H(k,S)\in\mathbb{F}_{q}^{k\times q}$ for $S=\mathbb{F}_{q}$;777For
appropriate parameters, our argument works more generally for any sufficiently
large subset $S\subseteq\mathbb{F}_{q}$, with $R=\left|{S}\right|$; we use
$S=\mathbb{F}_{q}$ for simplicity.

  * •

$\ell:=2k$;

  * •

$\boldsymbol{x}\in B_{q,h}$ be a uniformly random $q$-dimensional binary
vector of Hamming weight $h:=\lfloor(1+\varepsilon)k\rfloor$;

  * •

$T\in\\{0,1\\}^{r\times q}$ be chosen by independently setting each of its
entries to be $1$ with probability $1/(4hr)$, and to be $0$ otherwise.

It then outputs $(A,\boldsymbol{x},\ell,T)$.

We first analyze the algorithm’s running time. A suitable prime $q$ can be
found in $\operatorname{poly}(r)$ time using, e.g., trial division (recall
that $r$ is given in unary). The basis $A$ can be computed in deterministic
polynomial time from the generating set of column vectors $(B\mid qI_{q})$,
where $B$ is a basis of $\ker(H)\subseteq\mathbb{F}_{q}^{q}$ (lifted to the
integers). It is clear that $\ell$ can be computed in deterministic polynomial
time, and that $\boldsymbol{x}$ and $T$ can be computed in randomized
polynomial time. So, the algorithm runs in randomized polynomial time.

It remains to show correctness, i.e., that $(A,\boldsymbol{x},\ell,T)$
satisfies the two conditions in Definition 2.6 with suitable probability over
the random choices of $\boldsymbol{x}$ and $T$. First, Item 1 is always
satisfied, because by Theorem 3.1 we have

$\lambda_{1}(\mathcal{L})\geq(2k)^{1/p}=\ell^{1/p}\ \text{.}$

In the rest of the proof we consider Item 2 of Definition 2.6. Let
$W:=(\boldsymbol{x}+\mathcal{L})\cap B_{q,h}$. Because

$\lVert\boldsymbol{w}\rVert_{p}^{p}=h\leq(1+\varepsilon)k=\alpha^{p}\cdot\ell$

for each $\boldsymbol{w}\in W$, we have $W\subseteq
V:=(\boldsymbol{x}+\mathcal{L})\cap\mathcal{B}_{p}^{q}(\alpha\cdot\ell^{1/p})$.

By Lemma 3.3,
$\Pr_{\boldsymbol{x}}[\left|{W}\right|\geq\binom{q}{h}/(10q^{k})]>1-1/10=9/10$.
If this event holds, and

$\frac{\binom{q}{h}}{10q^{k}}\geq h!\cdot q^{240r\sqrt{h}}\ \text{,}$ (12)

then by Theorem 2.7 we have $\\{0,1\\}^{r}\subseteq T(W)\subseteq T(V)$ with
probability at least $1-1/10=9/10$ (over the choice of $T$). So, it suffices
to show that the condition in Equation 12 holds for all sufficiently large
$k$, and hence for all sufficiently large $r$. By taking a union bound over
the $1/10$ failure probabilities from Lemma 3.3 and Theorem 2.7, we get that
the algorithm’s overall success probability is at least $1-2/10>2/3$ for all
sufficiently large $r$, as needed.

Using the standard bound $\binom{q}{h}\geq(q/h)^{h}$ for binomial coefficients
and that $h\geq(1+\varepsilon)k-1$, we have that

$\frac{\binom{q}{h}}{10q^{k}}\geq\frac{q^{h-k}}{10h^{h}}=\Omega\Big{(}\frac{q^{\varepsilon
k-1}}{h^{h}}\Big{)}\ \text{.}$ (13)

Furthermore, by the choice of $k$ relative to $r$ and $h\leq(1+\varepsilon)k$,
we have that

$h!\cdot q^{240r\sqrt{h}}\leq h^{h}\cdot
q^{240k^{1/2-\delta}\sqrt{(1+\varepsilon)k}}\leq h^{h}\cdot q^{o(k)}\
\text{.}$ (14)

So, by combining Equations 13 and 14, in order to establish Equation 12 it
suffices to show that $q^{(1-o(1))\varepsilon k}\geq h^{2h}$. By taking logs,
this is equivalent to

$(1-o(1))\cdot\varepsilon k\log q\geq 2h\log h\ \text{.}$ (15)

Finally, using that $k^{3(1+\varepsilon)/\varepsilon}\leq
q\leq\operatorname{poly}(k)$ and $h\leq(1+\varepsilon)k$, in order for
Equation 15 to hold it suffices to have

$(1-o(1))\cdot\varepsilon k\cdot\frac{3(1+\varepsilon)}{\varepsilon}\cdot\log
k=(3-o(1))\cdot(1+\varepsilon)\cdot k\log k\geq 2(1+\varepsilon)\cdot k\log
k+O(k)\ \text{,}$

which indeed holds for all sufficiently large $k$, as needed. ∎

We emphasize that Theorem 3.4 uses randomness only to sample $\boldsymbol{x}$
and $T$. As an immediate corollary, we obtain our main hardness result,
Theorem 1.1—which, to recall, asserts that for all constants $p\in[1,\infty)$
and $\gamma<2^{1/p}$, there is no polynomial-time algorithm for
$\gamma$-$\mathrm{GapSVP}_{p}$ unless $\mathsf{NP}\subseteq\mathsf{RP}$.

###### Proof of Theorem 1.1.

Combine Item 2 of Corollary 2.11 with Theorem 3.4. ∎

##  4 Efficient Decoding Near Minkowski’s Bound

In this section, we show that a recent result of Mook and Peikert [MP22],
which builds on work of Guruswami and Sudan [GS98] and Koetter and Vardy
[KV03] on list-decoding Reed-Solomon codes, yields a polynomial-time algorithm
for decoding lattices $\mathcal{L}=\mathcal{L}^{\perp}(H)$ with
$H=H_{q}(k,\mathbb{F}_{q})$ up to distance $\Theta(\sqrt{k})$. We additionally
observe that by choosing $k=\Theta(q/\log q)$, such lattices are
asymptotically nearly tight with Minkowski’s bound (Equation 5). Putting these
observations together, we obtain an efficient algorithm for decoding to a
distance within a $O(\sqrt{\log q})$ factor of Minkowski’s bound (here $q=n$
is the lattice rank and dimension).

###  4.1 Construction and Algorithm

Define the additive quotient group $\mathbb{R}_{q}:=\mathbb{R}/(q\mathbb{Z})$
and the Euclidean norm of any $\hat{\boldsymbol{y}}\in\mathbb{R}_{q}^{n}$ as

$\lVert\hat{\boldsymbol{y}}\rVert:=\min\\{\lVert\boldsymbol{y}\rVert:\boldsymbol{y}\in\hat{\boldsymbol{y}}+q\mathbb{Z}^{n}\\}\
\text{.}$ (16)

Equivalently, $\lVert\hat{\boldsymbol{y}}\rVert$ is the standard
$\mathbb{R}^{n}$ Euclidean norm of the unique real vector
$\boldsymbol{y}\equiv\hat{\boldsymbol{y}}\pmod{q\mathbb{Z}^{n}}$ having
coordinates in $[-q/2,q/2)$. In additive arithmetic that mixes elements of
$\mathbb{F}_{q}$ and $\mathbb{R}_{q}$, we implicitly ‘lift’ the former to the
latter in the natural way.

We again use the fact that for evaluation set $S=\mathbb{F}_{q}$, the matrix
$H=H_{q}(k,\mathbb{F}_{q})$ defined in Equation 7 is a parity-check matrix of
the Reed-Solomon code $\mathrm{RS}_{q}[q-k,\mathbb{F}_{q}]$, and therefore
$\mathcal{L}^{\perp}(H_{q}(k,\mathbb{F}_{q}))=\mathrm{RS}_{q}[q-k,\mathbb{F}_{q}]+q\mathbb{Z}^{q}$.
This view lets us take advantage of the decoding algorithm from the following
theorem of [MP22], which gives an efficient (list) decoder in the $\ell_{2}$
norm for Reed-Solomon codes.888In fact, the cited result from [MP22] is more
general, giving a decoder for _$\mathbb{F}_{p}$ -subfield subcodes_ of Reed-
Solomon codes over finite fields of order $q=p^{r}$, for a prime $p$. Here we
need only the special case where the Reed-Solomon code is over a prime field
(i.e., where $r=1$). On the other hand, we note that if Proposition 4.1 were
extended to handle _generalized_ Reed-Solomon codes, then we would get a
corresponding strengthening of Corollary 4.2 for decoding lattices
$\mathcal{L}^{\perp}(H_{q}(k,S))$ with general $S$, not just
$S=\mathbb{F}_{q}$.

######  Proposition 4.1 ([MP22, Algorithm 1 and Theorem 3.4]).

Let $q$ be a prime, $S\subseteq\mathbb{F}_{q}$ be an evaluation set of size
$n:=\left|{S}\right|$, $k\leq n$ be a nonnegative integer, and
$\varepsilon>0$. There is a deterministic algorithm that, on input $q$, $S$,
$k$, $\varepsilon$, and a vector $\hat{\boldsymbol{y}}\in\mathbb{R}_{q}^{n}$,
outputs all codewords $\boldsymbol{c}\in\mathrm{RS}_{q}[n-k,S]$ such that
$\lVert\hat{\boldsymbol{y}}-\boldsymbol{c}\rVert^{2}\leq(1-\varepsilon)(k+1)/2$,
in time polynomial in $n$, $\log q$, and $1/\varepsilon$.999Formally, the
runtimes of the decoding algorithms in Propositions 4.1 and 4.2 additionally
depend on the lengths of the respective “received words”
$\hat{\boldsymbol{y}}$ and $\boldsymbol{y}$ that they take as input, which
must be specified to finite precision. However, for simplicity we describe the
algorithms in the “Real RAM model,” while noting that their runtime dependence
on the encoding lengths of $\hat{\boldsymbol{y}},\boldsymbol{y}$ is
polynomial.

The following corollary, which is the main result of this section, says that
by taking $S=\mathbb{F}_{q}$ and $k=\Theta(q/\log q)$, (1) the root Hermite
factor of $\mathcal{L}^{\perp}(H)$ is within an $O(\sqrt{\log q})$ factor of
Minkowski’s bound (Equation 5), and (2) it is possible to efficiently decode
this lattice to a distance of $\Omega(\sqrt{k})=\Omega(\sqrt{q/\log q})$,
which is again within an $O(\sqrt{\log q})$ factor of Minkowski’s bound.

We remark that by setting $\varepsilon\leq 1/(k+1)$ in Corollary 4.2, we get
efficient decoding to a distance at least $\sqrt{k/2}$ but less than
$\sqrt{(k+1)/2}$, which is slightly more than half the lower bound of
$\sqrt{2k}$ on the minimum Euclidean distance of the lattice (Theorem 3.1).
Recall that this lower bound is tight when $k$ is a proper divisor of $q-1$
(see Lemma 3.2), so with this parameterization we get efficient _list_
decoding (i.e., the algorithm may return more than one lattice vector)
slightly beyond the unique-decoding bound of half the minimum distance.

######  Corollary 4.2 (Efficient decoding near Minkowski’s bound).

Let $H=H_{q}(k,\mathbb{F}_{q})$ for a prime $q$ and $k:=\lfloor q/(2\log
q)\rfloor\leq q/2$, where all logarithms are base two. Then for
$\mathcal{L}:=\mathcal{L}^{\perp}(H)\subseteq\mathbb{Z}^{q}$:

  1. 1.

$\sqrt{q/\log
q-2}\leq\sqrt{2k}\leq\lambda_{1}(\mathcal{L})\leq\sqrt{q}\cdot\det(\mathcal{L})^{1/q}\leq\sqrt{2q}$.

  2. 2.

For any $\varepsilon>1/\operatorname{poly}(q)$, there is an algorithm that, on
input $q$ and a vector $\boldsymbol{y}\in\mathbb{R}^{q}$, outputs all lattice
vectors $\boldsymbol{v}\in\mathcal{L}$ satisfying
$\lVert\boldsymbol{y}-\boldsymbol{v}\rVert\leq\sqrt{(1-\varepsilon)(k+1)/2}$
in time polynomial in $q$.

###### Proof.

For Item 1, we have

$\sqrt{q/\log
q-2}\leq\sqrt{2k}\leq\lambda_{1}(\mathcal{L})\leq\sqrt{q}\cdot\det(\mathcal{L})^{1/q}=\sqrt{q}\cdot
q^{k/q}\leq\sqrt{2q}\ \text{.}$

The first inequality follows from the choice of $k$, the second inequality is
by Theorem 3.1, the third inequality is Minkowski’s bound (Equation 5), the
equality follows from Lemma 2.2 (recall that the rows of $H$ are linearly
independent), and the final inequality again follows from the choice of
$k$.101010Analyzing the derivative of $\log(\sqrt{2k}/q^{k/q})$ with respect
to $k$ shows that our choice of $k$ is asymptotically optimal for maximizing
the root Hermite factor of $\mathcal{L}^{\perp}(H_{q}(k,\mathbb{F}_{q}))$.

The algorithm claimed in Item 2 works as follows. First, it computes $k$ and
$\hat{\boldsymbol{y}}=\boldsymbol{y}\bmod
q\mathbb{Z}^{q}\in\mathbb{R}_{q}^{q}$ from the input $q$ and $\boldsymbol{y}$.
It then calls the algorithm from Proposition 4.1 on $q$, $S=\mathbb{F}_{q}$,
$k$, $\varepsilon$, and $\hat{\boldsymbol{y}}$, and receives as output zero or
more codewords $\boldsymbol{c}\in\mathrm{RS}_{q}[q-k,\mathbb{F}_{q}]$. For
each such $\boldsymbol{c}$, it outputs the unique vector
$\boldsymbol{v}:=\operatorname*{arg\,min}_{\boldsymbol{v}^{\prime}\in\boldsymbol{c}+q\mathbb{Z}^{q}}\lVert\boldsymbol{y}-\boldsymbol{v}^{\prime}\rVert\in\mathcal{L}$.

The value $k$ and vectors $\hat{\boldsymbol{y}}$, $\boldsymbol{v}$ can be
computed efficiently (assuming that $\boldsymbol{v}$ is well defined), so it
is clear from Proposition 4.1 that this algorithm runs in time polynomial in
$q$ (recall that the dimension $n=q$). It remains to show correctness. First,
it is immediate from the definitions that for any $r<q/2$, the function
$f(\boldsymbol{v})=\boldsymbol{v}\bmod q\mathbb{Z}^{q}$ is a bijection from
the set of lattice vectors

$\\{\boldsymbol{v}\in\mathcal{L}:\lVert\boldsymbol{y}-\boldsymbol{v}\rVert\leq
r\\}\ \text{,}$

to the set of codewords

$\\{\boldsymbol{c}\in\mathrm{RS}_{q}[q-k,\mathbb{F}_{q}]:\lVert\hat{\boldsymbol{y}}-\boldsymbol{c}\rVert\leq
r\\}\ \text{,}$

and that
$g(\boldsymbol{c}):=\operatorname*{arg\,min}_{\boldsymbol{v}^{\prime}\in\boldsymbol{c}+q\mathbb{Z}^{q}}\lVert\boldsymbol{y}-\boldsymbol{v}^{\prime}\rVert$
is the inverse function of $f$, i.e., $g=f^{-1}$. Moreover, because $q\geq 2$,
we have that the decoding distance $r$ satisfies

$r:=\sqrt{(1-\varepsilon)(k+1)/2}\leq\sqrt{(1-\varepsilon)(q/(2\log
q)+1)/2}\leq\sqrt{1-\varepsilon}\cdot q/2<q/2\ \text{.}$

Because the algorithm from Proposition 4.1 outputs (exactly)
$\\{\boldsymbol{c}\in\mathrm{RS}_{q}[q-k,\mathbb{F}_{q}]:\lVert\hat{\boldsymbol{y}}-\boldsymbol{c}\rVert\leq
r\\}$, it follows that the algorithm described above outputs (exactly)
$\\{\boldsymbol{v}\in\mathcal{L}:\lVert\boldsymbol{y}-\boldsymbol{v}\rVert\leq
r\\}$, as needed. ∎

######  Remark 4.3.

We remark that the main consequence of Item 1 of Corollary 4.2—namely, an
explicit construction of a family of lattices having root Hermite factors
within a $O(\sqrt{\log n})$ factor of Minkowski’s bound, obtained via
Construction A (where $n$ is the lattice dimension)—only needs a family of
codes satisfying milder conditions than what (generalized) Reed-Solomon codes
satisfy. Namely, achieving this result only requires a family of linear
$q$-ary codes $\mathcal{C}$ for prime $q$ with block length $n$, codimension
$k=\Theta(n/\log n)$, and minimum distance (in the Hamming metric)
$d=\Omega(k)$. The latter is a weaker condition than _maximum distance
separability_ (MDS), which requires that $d=k+1$. Indeed, $d=\Omega(k)$
implies that the corresponding Construction-A lattice
$\mathcal{C}+q\mathbb{Z}^{n}$ has an $\ell_{2}$ minimum distance of
$\Omega(\min\\{\sqrt{k},q\\})$, which is $\Omega(\sqrt{k})$ when $k=O(q^{2})$.
So, unlike our main hardness result, Corollary 4.2 does not use Theorem 3.1 in
any essential way.

Finally, we also note that obtaining a direct analog of Item 2 of Corollary
4.2—i.e., efficiently decoding to within an $O(\sqrt{\log n})$ factor of
Minkowski’s bound on $\mathcal{C}+q\mathbb{Z}^{n}$—additionally requires an
efficient algorithm for decoding $\mathcal{C}$ to an $\ell_{2}$ distance of
$\Omega(\sqrt{k})$, but that this is in turn a weaker requirement than what
Proposition 4.1 fulfills.

##  5 Attempted Derandomization

In this section we describe some of our unsuccessful attempts, and associated
barriers, to adapt the _randomized_ locally dense lattice construction from
Section 3 into a _deterministic_ one. More specifically: for some
$p\in[1,\infty)$ and $\alpha\in(0,1)$, our goal is a deterministic algorithm
that, given any positive integer $r$ (in unary), outputs a
$(p,\alpha,r,R=\operatorname{poly}(r))$-locally dense lattice in
$\operatorname{poly}(r)$ time. Recall from Definition 2.6 that this requires
constructing an explicit rank-$R$ lattice and “dense coset” (both integral)
containing at least $2^{r}$ vectors that have norm at most $\alpha$ times (a
known lower bound on) the lattice’s minimum distance.111111Recall that a
locally dense lattice must also come with a suitable linear transform $T$. In
this section we do not address the construction of such $T$, because
deterministically constructing a lattice and dense coset is already
challenging enough. We hope that such a construction and its analysis will
naturally reveal a suitable choice of $T$ as well.

As in Section 3, we focus on the case where the lattice has the form
$\mathcal{L}=\mathcal{L}^{\perp}(H)\subseteq\mathbb{Z}^{S}$, where
$H=H_{q}(k,S)$ for some prime $q$, positive integer $k$, and set
$S\subseteq\mathbb{F}_{q}$ of cardinality $n=R=\left|{S}\right|$ (which all
may be set by the algorithm). Recall from Section 3.2 that for appropriate
parameters, there exists a dense coset $\boldsymbol{x}+\mathcal{L}$ having
$n^{\Omega(k)}$ short vectors (indeed, binary vectors of a particular Hamming
weight), and that an appropriate random choice of coset has this property with
good probability. To derandomize, we need to deterministically construct a
dense integral coset $\boldsymbol{x}+\mathcal{L}$, or equivalently, its
syndrome $\boldsymbol{u}=H\boldsymbol{x}\in\mathbb{F}_{q}^{k}$. This is the
problem that we address in this section. We thank Swastik Kopparty [Kop20] for
explaining its connections to the approaches considered in Sections 5.1 and
5.2.

As a first observation, we note that _not every_ syndrome (coset) is suitable,
and some unsuitable ones are easy to describe. Clearly, the all-zeros syndrome
$\boldsymbol{0}\in\mathbb{F}_{q}^{k}$ is unsuitable, because it corresponds to
(the zero coset of) the lattice $\mathcal{L}$ itself, which has only one
vector shorter than the minimum distance. More generally, by the triangle
inequality, for any $\boldsymbol{x}\in\mathbb{Z}^{S}$ such that
$\lVert\boldsymbol{x}\rVert<(1-\alpha)\lambda_{1}(\mathcal{L})$, the lattice
coset $\boldsymbol{x}+\mathcal{L}$ has at most one vector of length at most
$\alpha\lambda_{1}(\mathcal{L})$, namely $\boldsymbol{x}$ itself (if it is
short enough). So, when $\lambda_{1}(\mathcal{L})\geq\sqrt{2k}$ (e.g., as
implied by Theorem 3.1), if $\lVert\boldsymbol{x}\rVert<(1-\alpha)\sqrt{2k}$
then the coset $\boldsymbol{x}+\mathcal{L}$ has at most one vector of length
at most $\alpha\sqrt{2k}$. (A similar argument holds for all other $\ell_{p}$
norms.) Stated in terms of syndromes: no “too small” integer linear
combination of the columns of $H$ is a suitable syndrome, because it
corresponds to shifting the lattice by “too little.”

###  5.1 Binary Coset Vectors and Reed-Solomon List Decoding Bounds

Optimistically, we might hope to show a close deterministic analog of the
probabilistic result from Lemma 3.3, namely, an efficient deterministic
construction of a parity-check matrix $H=H_{q}(k,S)$ and a shift
$\boldsymbol{x}\in\mathbb{Z}^{S}$ where the coset
$\boldsymbol{x}+\mathcal{L}^{\perp}(H)$ has sufficiently many _binary_ vectors
of some specified Hamming weight
$h\leq\alpha\cdot(2k)\leq\alpha\cdot\lambda_{1}^{(1)}(\mathcal{L}^{\perp}(H))$
for some positive constant $\alpha<1$.

However, even with a relaxed requirement of $h\leq 2k$, the hoped-for
deterministic analog would imply explicit Reed-Solomon list-decoding
configurations that go beyond the current state of the art, due to Guruswami
and Rudra [GR05]. While this does not rule out the desired analog entirely, it
does present an apparent barrier: achieving the analog would likely require
new techniques, and would lead to a significant step forward in our
understanding of Reed-Solomon codes.

######  Lemma 5.1.

There is an efficient deterministic algorithm that, given a prime $q$, a
positive integer $k\leq q$, a set $S\subseteq\mathbb{F}_{q}$ of cardinality
$\left|{S}\right|\geq k$ defining $H=H_{q}(k,S)$ and
$\mathcal{L}=\mathcal{L}^{\perp}(H)\subseteq\mathbb{Z}^{S}$, an integer
$h\in\\{k,\ldots,\left|{S}\right|\\}$, and any shift
$\boldsymbol{x}\in\mathbb{Z}^{S}$ (or its syndrome
$\boldsymbol{u}=H\boldsymbol{x}\in\mathbb{F}_{q}^{k}$), outputs a vector
$\boldsymbol{r}\in\mathbb{F}_{q}^{S}$ for which there are at least
$\left|{(\boldsymbol{x}+\mathcal{L})\cap B_{S,h})}\right|$ codewords in the
Reed-Solomon code $\mathrm{RS}_{q}[h-k+1,S]$ that each agree with
$\boldsymbol{r}$ in at least $h$ coordinates.

###### Proof.

The algorithm works as follows.

  1. 1.

Compute the coset’s syndrome
$\boldsymbol{u}=H\boldsymbol{x}\in\mathbb{F}_{q}^{k}$.

Note that for each $i\in[k]$, the syndrome’s $i$th coordinate $u_{i}$ is the
$i$th power sum of the subset $T\subseteq S$ indicated by any binary vector
$\boldsymbol{x}_{T}\in(\boldsymbol{x}+\mathcal{L})\cap B_{S,h}$, i.e.,
$u_{i}=(H\boldsymbol{x})_{i}=(H\boldsymbol{x}_{T})_{i}=p_{i}(T)\in\mathbb{F}_{q}$.
In particular, $h=\left|{T}\right|\equiv u_{0}\pmod{q}$ for any such $T$. (So,
if $h\not\equiv u_{0}\pmod{q}$, no such $T$ exists and the algorithm may
output any vector.)

  2. 2.

Use Newton’s identities (Equation 10) to compute (from $\boldsymbol{u}$) the
values $s_{i}=e_{i}(T)\in\mathbb{F}_{q}$ for each $i\in[k]$, which are the
first $k\leq h=\left|{T}\right|$ elementary symmetric polynomials of any such
$T$.

  3. 3.

Finally, construct the polynomial

$r(x)=\sum_{i\in[k]}(-1)^{i}\cdot s_{i}\cdot x^{h-i}\in\mathbb{F}_{q}[x]$

and output the vector $\boldsymbol{r}=(-r(s))_{s\in S}\in\mathbb{F}_{q}^{S}$
obtained by evaluating $-r(x)$ at each element of $S$.

We now show that the algorithm is correct. Let $T\subseteq S$ be the subset
indicated by a binary vector
$\boldsymbol{x}_{T}\in(\boldsymbol{x}+\mathcal{L})\cap B_{S,h}$, and let
$f_{T}(x)=\prod_{t\in T}(x-t)\in\mathbb{F}_{q}[x]$ be the root polynomial of
$T$. As argued above in Item 2, $s_{i}=e_{i}(T)$ for each $i\in[k]$, so by
Equation 11, we have

$f_{T}(x)=r(x)+g_{T}(x)$

for some $g_{T}(x)$ where $\deg(g_{T})\leq h-k$ (or $g_{T}$ is identically
zero). Because $f_{T}(t)=0$ for every $t\in T$, we have $g_{T}(t)=-r(t)$ for
every $t\in T$, i.e., the Reed-Solomon codeword in $\text{RS}[h-k+1,S]$
defined by $g_{T}$ agrees with $\boldsymbol{r}$ in at least
$\left|{T}\right|=h$ positions. Finally, the claim follows by noting that each
distinct binary vector $\boldsymbol{x}_{T}\in(\boldsymbol{x}+\mathcal{L})\cap
B_{S,h}$ yields a distinct subset $T\subseteq S$, which yields a distinct root
polynomial $f_{T}$ and thereby a distinct polynomial $g_{T}=f_{T}-r$. ∎

For an analog of Lemma 3.3, we want an explicit (i.e., deterministically and
efficiently constructible) lattice $\mathcal{L}=\mathcal{L}^{\perp}(H)$ and
shift $\boldsymbol{x}$ such that $\left|{(\boldsymbol{x}+\mathcal{L})\cap
B_{S,h}}\right|$ is super-polynomial (in $\left|{S}\right|$), for some Hamming
weight $h\leq 2k\leq\lambda_{1}^{(1)}(\mathcal{L})$. By Lemma 5.1, this
implies an explicit received word and Reed-Solomon code of dimension $h-k+1$
for which super-polynomially many codewords agree with the received word in at
least $h$ coordinates. This is an agreement-to-dimension ratio of
$h/(h-k+1)=1+(k-1)/(h-k+1)\geq 2-O(1/k)$. However, the state of the art for
explicit Reed-Solomon list-decoding configurations [GR05, Corollary 2]
requires a ratio of $2-\Omega(1)$ in order to get a super-polynomial list
size.

######  Remark 5.2.

It is not clear whether a useful converse of Lemma 5.1 holds, i.e., whether an
explicit ‘bad’ list-decoding configuration for Reed-Solomon codes would yield
a corresponding explicit locally dense lattice. This is because the difference
between the received word and a nearby codeword may not correspond to (the
evaluations of) the root polynomial of the positions at which they agree, but
is only divisible by it.

######  Remark 5.3.

Everything in the proof of Lemma 5.1 generalizes from binary vectors to _non-
negative_ integer vectors of $\ell_{1}$ norm $h$ and their corresponding
_multisets_ $T$, except for the final step: the codeword corresponding to
$g_{T}(x)$ is guaranteed to agree with $\boldsymbol{r}$ only at each
_distinct_ $t\in T$, and the number of these is only the _Hamming_ weight (not
the $\ell_{1}$ norm $h$) of the integer vector. It appears that this gap can
be overcome (restoring agreement $h$) by instead using univariate
_multiplicity codes_ , which are generalizations of Reed-Solomon where the
coordinates correspond to ‘multiple evaluations’ of a polynomial _and its
derivatives_ ; see [Kop14]. For such codes, we do not know whether any
explicit list-decoding configurations with substantially different parameters
from Reed-Solomon codes are known.

By contrast, Lemma 5.1 does not seem to generalize easily to _arbitrary_
integer vectors that may have negative entries (e.g., ternary $\\{0,\pm
1\\}$-vectors of a given Hamming weight). So, considering negative entries may
provide a route to constructing locally dense lattices without having to
overcome the Reed-Solomon list-decoding barriers.

###  5.2 A Fourier-Analytic Approach

We next outline an approach for using Fourier analysis over
$\mathbb{F}_{q}^{k}$ for prime $q$ and $k\ll q$ to show that an explicit coset
$\boldsymbol{x}+\mathcal{L}^{\perp}(H)$ for $H=H_{q}(k,\mathbb{F}_{q}))$
contains many vectors of $\ell_{1}$ norm at most
$h\leq\alpha\cdot(2k)\leq\alpha\cdot\lambda_{1}^{(1)}(\mathcal{L}^{\perp}(H))$
for some integer $h$, where $\alpha\in(0,1)$ is a constant as above.

The approach uses techniques similar to those used by Cheng and Wan [CW04] and
Guruswami and Rudra [GR05] for constructing explicit Hamming balls containing
many Reed-Solomon codewords (i.e., for constructing explicit “bad”
configurations for list-decoding Reed-Solomon codes), and by Cheng and Wan
[CW09] for showing deterministic hardness of the minimum distance problem on
codes.

Specifically, we perform a Fourier-analytic calculation similar to ones
appearing in those works in an attempt to lower bound the number of short
vectors $\boldsymbol{x}\in\mathbb{F}_{q}^{q}$ satisfying
$H\boldsymbol{x}=\boldsymbol{s}$ for some syndrome
$\boldsymbol{s}\in\mathbb{F}_{q}^{k}$ (which is equivalent to lower bounding
the number of short vectors in the lattice coset
$\mathcal{L}^{\perp}_{\boldsymbol{s}}(H)$). The calculation starts by
establishing a correspondence between polynomials in $\mathbb{F}_{q}[x]$ of
degree less than $k$ and the Fourier coefficients of a certain indicator
function $1_{W}$. It then uses a combination of the Weil bound (Equation 25)
and the triangle inequality to upper bound the total contribution of the terms
corresponding to non-constant polynomials in the Fourier expansion of the
$h$-fold convolution $1_{W}^{(\ast h)}$ of $1_{W}$, which essentially counts
the number of non-negative integer vectors of $\ell_{1}$ norm $h$ with a given
syndrome (see Equation 26).

Unfortunately, this calculation (just barely) fails to show anything useful
for our purposes. The rough idea of why is as follows. The argument seeks to
show that the sum of magnitudes ($\ell_{1}$ norm) of all the Fourier
coefficients of $1_{W}^{(\ast h)}$ corresponding to non-constant polynomials
is less than the zero coefficient of $1_{W}^{(\ast h)}$ (which is real-valued,
positive, and corresponds to the zero polynomial). The Weil bound shows that
there is a multiplicative gap of about $\sqrt{q}$ between the value of the
zero coefficient and the magnitude of any non-constant coefficient of $1_{W}$,
and this gap is amplified to about $q^{h/2}$ for the corresponding Fourier
coefficients of $1_{W}^{(\ast h)}$. However, because there are about $q^{k}$
non-constant polynomials in $\mathbb{F}_{q}[x]$ of degree less than $k$, we
need to take $h\geq 2k$ in order for the zero coefficient of $1_{W}^{(\ast
h)}$ to be large enough, which conflicts with the requirement that $h<2k$.

Because the calculation is not directly useful for our purposes, and due to
its similarity to those in prior work, we defer it to Appendix B. There we
also discuss some approaches for making the argument work.

###  5.3 Point-Counting Proxies

In this section we outline a possible approach toward proving local density
for a deterministic version of our construction, using “smooth” functions that
serve as proxies for point-counting functions. The hope is to use these
functions to prove a lower bound on the number of sufficiently short points in
_any_ coset $\boldsymbol{x}+\mathcal{L}^{\perp}(H)$ meeting some easy-to-
ensure conditions. The approach is centered on analytical techniques
originally due to [MO90, EOR91], which were successfully used on the integer
lattice $\mathbb{Z}^{n}$ for complexity-theoretic purposes in [AS18, BP20]. In
the present context of Reed-Solomon lattices, our attempts have been
inconclusive: while we did not manage to prove what we are seeking, we also do
not see any inherent barrier, and further effort may lead to a favorable
outcome.

For any $p\geq 1$, $\ell_{p}$ norm bound $r\geq 0$, and lattice coset
$\boldsymbol{x}+\mathcal{L}\subset\mathbb{R}^{n}$, define

$N_{p}(r;\boldsymbol{x}+\mathcal{L}):=\left|{(\boldsymbol{x}+\mathcal{L})\cap\mathcal{B}_{p}^{n}(r)}\right|$
(17)

to be the number of points in $\boldsymbol{x}+\mathcal{L}$ of $\ell_{p}$ norm
at most $r$. Similarly, for any $\tau>0$, define the function

$\Theta_{p}(\tau;\boldsymbol{x}+\mathcal{L}):=\sum_{\boldsymbol{v}\in\boldsymbol{x}+\mathcal{L}}\exp(-\tau\lVert\boldsymbol{v}\rVert_{p}^{p})\
\text{.}$ (18)

In what follows, for brevity we often omit the coset
$\boldsymbol{x}+\mathcal{L}$ when it is fixed and clear from context.

First, for any $\tau>0$ we immediately have

$N_{p}(r)\leq\exp(\tau\cdot r^{p})\cdot\Theta_{p}(\tau)\ \text{,}$ (19)

because each point counted by $N_{p}(r)$ contributes at least $\exp(-\tau\cdot
r^{p})$ to $\Theta_{p}(\tau)$, and all other points contribute positively. The
work of [MO90, EOR91] showed that for any coset of the _integer_ lattice
$\mathcal{L}=\mathbb{Z}^{n}$, the upper bound from Equation 19 is fairly tight
(up to $\exp(O(\sqrt{n}))$ factors) for suitably chosen $\tau$, namely, the
one for which $\mu_{p}(\tau;\boldsymbol{x}+\mathcal{L})=r^{p}$, where

$\mu_{p}(\tau;\boldsymbol{x}+\mathcal{L}):=\operatorname*{\mathrm{E}}_{\boldsymbol{v}\sim
D_{p}(\tau;\boldsymbol{x}+\mathcal{L})}\left[\lVert\boldsymbol{v}\rVert_{p}^{p}\right]$
(20)

and $D_{p}(\tau)$ is the probability distribution supported on
$\boldsymbol{x}+\mathcal{L}$ that assigns probability
$\exp(-\tau\lVert\boldsymbol{v}\rVert_{p}^{p})/\Theta_{p}(\tau)$ to each
$\boldsymbol{v}$. In other words, $\mu_{p}(\tau)$ is the $p$th moment of the
$\ell_{p}$ norm of a sample from $D_{p}(\tau)$, and when $\tau$ is chosen to
make this moment equal $r^{p}$, Equation 19 is fairly tight for any coset of
the integer lattice.

Optimistically, if we could show that Equation 19 is fairly tight for suitable
$\tau$ (as a function of $r$) and every coset of our special lattices, then we
would have

$N_{p}(r)\approx\exp(\tau\cdot
r^{p})\cdot\Theta_{p}(\tau)=\exp(\tau\cdot\alpha^{p}\cdot
2k)\cdot\Theta_{p}(\tau)\ \text{,}$

where
$r=\alpha\cdot(2k)^{1/p}\leq\alpha\cdot\lambda_{1}^{(p)}(\mathcal{L}^{\perp}(H))$
for some constant $\alpha<1$ is our distance of interest for local density,
and $\tau$ is determined by this $r$. Furthermore, if we could also show that,
say, $\Theta_{p}(\tau)\geq\exp(-\tau k)$ for this $\tau$ and a suitable choice
of coset (e.g., by shifting the lattice by some $\boldsymbol{x}$ with
$\lVert\boldsymbol{x}\rVert_{p}^{p}=k$), then for any constant
$\alpha>1/2^{1/p}$ we could conclude that there are $\exp(\Omega(\tau k))$
sufficiently short points in the coset. Finally, if we could show that
$\tau\geq k^{c-1}$ for some constant $c>0$, this would yield a subexponential
number of short coset vectors, as needed.

#### An approach.

Toward this end, we observe that several parts of the analysis from [MO90,
EOR91] immediately generalize to cosets of arbitrary lattices, not just the
integer lattice $\mathbb{Z}^{n}$. In particular, for any lattice coset and any
$\tau>0$, by a routine calculation we have

$\displaystyle\frac{\partial}{\partial\tau}\ln\Theta_{p}(\tau)$
$\displaystyle=-\mu_{p}(\tau)<0\ \text{,}$ (21)
$\displaystyle\frac{\partial^{2}}{\partial\tau^{2}}\ln\Theta_{p}(\tau)$
$\displaystyle=\operatorname*{\mathrm{E}}_{\boldsymbol{v}\sim
D_{p}(\tau)}\left[\lVert\boldsymbol{v}\rVert_{p}^{2p}\right]-\mu_{p}(\tau)^{2}>0\
\text{.}$ (22)

In words, $\ln\Theta_{p}(\tau)$ is decreasing and concave up, and its second
partial derivative (with respect to $\tau$) is the variance of
$\lVert\boldsymbol{v}\rVert_{p}^{p}$ when $\boldsymbol{v}$ is sampled from
$D_{p}(\tau)$. Moreover, by an elegant (and non-obvious) argument, for any
$\tau,\delta>0$ we have the lower bound

$N_{p}(\mu_{p}(\tau)^{1/p})\geq\exp((\tau+\delta)\cdot\mu_{p}(\tau+2\delta))\cdot
H_{p}(\tau,\delta)\ \text{,}$ (23)

where

$H_{p}(\tau,\delta):=\Theta_{p}(\tau+\delta)-\exp(-\delta\mu_{p}(\tau))\cdot\Theta_{p}(\tau)-\exp(\delta\mu_{p}(\tau+2\delta))\cdot\Theta_{p}(\tau+2\delta)\
\text{.}$ (24)

Using the Taylor series for $\ln\Theta_{p}(\tau)$ around $\tau$ and Equation
21, for any $\delta>0$ we have

$\ln\Theta_{p}(\tau)\leq\ln\Theta_{p}(\tau+\delta)+\delta\mu_{p}(\tau)-\frac{\delta^{2}}{2}\inf_{\tau^{\prime}\in[\tau,\tau+\delta]}\frac{\partial^{2}}{\partial\tau^{2}}\ln\Theta_{p}(\tau^{\prime})\
\text{,}$

and similarly for $\ln\Theta_{p}(\tau+2\delta)$. So, if we could suitably
lower-bound the above infimum on the second partial derivative (which, to
recall from Equation 22, is positive) for appropriate $\delta$, by taking
$\exp(\cdot)$ of both sides and rearranging we could show that, say,
$H_{p}(\tau,\delta)\geq\Theta_{p}(\tau+\delta)/2$. The work of [MO90, EOR91]
actually does this for the integer lattice $\mathbb{Z}^{n}$, by exploiting its
product structure to show that the infimum is proportional to $n$, but here
the path forward is less clear.

If the above could be achieved, then we would get the lower bound

$N_{p}(\mu_{p}(\tau)^{1/p})\geq\exp((\tau+\delta)\cdot\mu_{p}(\tau+2\delta))\cdot\Theta_{p}(\tau+\delta)/2\approx\exp(\tau\cdot\mu_{p}(\tau))\cdot\Theta_{p}(\tau)/2\
\text{,}$

showing that Equation 19 is fairly tight when $r=\mu_{p}(\tau)^{1/p}$. As
explained above, the final goal would then be to identify an explicit coset
for which the right-hand side is at least subexponentially large in the
lattice dimension, when $\tau$ is set so that
$\mu_{p}(\tau)=\alpha^{p}\cdot(2k)$ for some constant $\alpha<1$.

## References

  * [ABSS93] S. Arora, L. Babai, J. Stern, and Z. Sweedyk.  The hardness of approximate optima in lattices, codes, and systems of linear equations.  _J. Comput. Syst. Sci._ , 54(2):317–331, 1997.  Preliminary version in FOCS 1993.
  * [Ajt98] M. Ajtai.  The shortest vector problem in $L_{2}$ is NP-hard for randomized reductions (extended abstract).  In _STOC_ , pages 10–19. 1998.
  * [AK11] P. Austrin and S. Khot.  A simple deterministic reduction for the gap minimum distance of code problem.  _IEEE Trans. Inf. Theory_ , 2014.  Preliminary verison in ICALP 2011.
  * [AR04] D. Aharonov and O. Regev.  Lattice problems in NP cap coNP.  _J. ACM_ , 52(5):749–765, 2005.  Preliminary version in FOCS 2004.
  * [AS18] D. Aggarwal and N. Stephens-Davidowitz.  (Gap/S)ETH hardness of SVP.  In _STOC_. 2018.
  * [BP20] H. Bennett and C. Peikert.  Hardness of bounded distance decoding on lattices in $\ell_{p}$ norms.  In _CCC_. 2020.
  * [BPT22] H. Bennett, C. Peikert, and Y. Tang.  Improved hardness of BDD and SVP under Gap-(S)ETH.  In _ITCS_. 2022.
  * [CN98] J. Cai and A. Nerurkar.  Approximating the SVP to within a factor $(1+1/\textrm{dim}^{\epsilon})$ is NP-hard under randomized reductions.  In _CCC_. 1998.
  * [Cra] M. Craig.  Automorphisms of prime cyclotomic lattices.  Preprint.
  * [CS99] J. Conway and N. J. A. Sloane.  _Sphere packings, lattices, and groups_.  Springer, 1999.
  * [CW04] Q. Cheng and D. Wan.  On the list and bounded distance decodibility of the Reed-Solomon codes (extended abstract).  In _FOCS_. 2004.
  * [CW09] Q. Cheng and D. Wan.  A deterministic reduction for the gap minimum distance problem.  _IEEE Trans. Inf. Theory_ , 58(11):6935–6941, 2012.  Preliminary version in STOC 2009.
  * [DMS99] I. Dumer, D. Micciancio, and M. Sudan.  Hardness of approximating the minimum distance of a linear code.  _IEEE Trans. Inf. Theory_ , 2003.  Preliminary version in FOCS 1999.
  * [DP19] L. Ducas and C. Pierrot.  Polynomial time bounded distance decoding near Minkowski’s bound in discrete logarithm lattices.  _Des. Codes Cryptogr._ , 87(8):1737–1748, 2019.
  * [DvW21] L. Ducas and W. van Woerden.  On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography.  Cryptology ePrint Archive, Report 2021/1332, 2021.  https://ia.cr/2021/1332.
  * [EOR91] N. D. Elkies, A. M. Odlyzko, and J. A. Rush.  On the packing densities of superballs and other bodies.  _Inventiones mathematicae_ , 105:613–639, December 1991.
  * [GG98] O. Goldreich and S. Goldwasser.  On the limits of nonapproximability of lattice problems.  _J. Comput. Syst. Sci._ , 60(3):540–563, 2000.  Preliminary version in STOC 1998.
  * [GP12] E. Grigorescu and C. Peikert.  List-decoding Barnes-Wall lattices.  _Comput. Complex._ , 26(2):365–392, 2017.  Preliminary version in CCC 2012.
  * [GR05] V. Guruswami and A. Rudra.  Limits to list decoding Reed-Solomon codes.  _IEEE Trans. Inf. Theory_ , 52(8):3642–3649, 2006.  Preliminary version in STOC 2005.
  * [GS98] V. Guruswami and M. Sudan.  Improved decoding of Reed-Solomon and algebraic-geometry codes.  _IEEE Trans. Inf. Theory_ , 45(6):1757–1767, 1999.  Preliminary version in FOCS 1998.
  * [Hal] J. I. Hall.  Notes on coding theory.  Available at https://users.math.msu.edu/users/halljo/classes/CODENOTES/CODING-NOTES.HTML.
  * [HR07] I. Haviv and O. Regev.  Tensor-based hardness of the shortest vector problem to within almost polynomial factors.  _Theory Comput._ , 8(1):513–531, 2012.  Preliminary version in STOC 2007.
  * [Kho03] S. Khot.  Hardness of approximating the shortest vector problem in high $\ell_{p}$ norms.  _J. Comput. Syst. Sci._ , 72(2):206–219, 2006.  Preliminary version in FOCS 2003.
  * [Kho04] S. Khot.  Hardness of approximating the shortest vector problem in lattices.  _J. ACM_ , 52(5):789–808, 2005.  Preliminary version in FOCS 2004.
  * [Kop14] S. Kopparty.  Some remarks on multiplicity codes.  In A. Barg, editor, _Discrete Geometry and Algebraic Combinatorics_ , Contemporary Mathematics. American Mathematical Society, 2014\.
  * [Kop20] S. Kopparty.  Personal communication, 2020.
  * [Kow10] E. Kowalski.  Exponential sums over finite fields: elementary methods.  https://people.math.ethz.ch/~kowalski/exponential-sums-elementary.pdf, 2010\.
  * [KV03] R. Koetter and A. Vardy.  Algebraic soft-decision decoding of Reed-Solomon codes.  _IEEE Trans. Inf. Theory_ , 49(11):2809–2825, 2003.
  * [LLM06] Y. Liu, V. Lyubashevsky, and D. Micciancio.  On bounded distance decoding for general lattices.  In _RANDOM_ , pages 450–461. 2006.
  * [Mea92] D. G. Mead.  Newton’s identities.  _The American Mathematical Monthly_ , 99(8):749, October 1992.
  * [Mic98] D. Micciancio.  The shortest vector in a lattice is hard to approximate to within some constant.  _SIAM J. Comput._ , 30(6):2008–2035, 2000.  Preliminary version in FOCS 1998.
  * [Mic12] D. Micciancio.  Inapproximability of the shortest vector problem: Toward a deterministic reduction.  _Theory Comput._ , 8(1):487–512, 2012.
  * [Mic14] D. Micciancio.  Locally dense codes.  In _CCC_. 2014.
  * [MN08] D. Micciancio and A. Nicolosi.  Efficient bounded distance decoders for Barnes-Wall lattices.  In _ISIT_ , pages 2484–2488. IEEE, 2008.
  * [MO90] J. E. Mazo and A. M. Odlyzko.  Lattice points in high-dimensional spheres.  _Monatshefte für Mathematik_ , 110(1):47–61, March 1990.
  * [MP22] E. Mook and C. Peikert.  Lattice (list) decoding near Minkowski’s inequality.  _IEEE Trans. Inf. Theory_ , 68(2):863–870, 2022.
  * [O’D14] R. O’Donnell.  _Analysis of Boolean Functions_.  Cambridge University Press, 2014.  ISBN 978-1-10-703832-5.
  * [Pei07] C. Peikert.  Limits on the hardness of lattice problems in $\ell_{p}$ norms.  _Computational Complexity_ , 17(2):300–351, May 2008.  Preliminary version in CCC 2007.
  * [Pei16] C. Peikert.  A decade of lattice cryptography.  _Found. Trends Theor. Comput. Sci._ , 10(4):283–424, 2016.
  * [RR06] O. Regev and R. Rosen.  Lattice problems and norm embeddings.  In _STOC_. 2006.
  * [Saw14] W. Sawin.  How tight is the Weil bound for this exponential sum?  MathOverflow, 2014.  https://mathoverflow.net/q/182599.
  * [vEB81] P. van Emde Boas.  Another NP-complete partition problem and the complexity of computing short vectors in a lattice.  Technical Report, 1981.  Available at https://staff.fnwi.uva.nl/p.vanemdeboas/vectors/mi8104c.html.

##  Appendix A Proof of Theorem 2.10

Here we restate and prove Theorem 2.10.

See 2.10

###### Proof.

Let $B\in\mathbb{Z}^{d\times r}$, $\boldsymbol{t}\in\mathbb{Z}^{d}$, $s>0$ be
the input instance of $\gamma$-$\mathrm{GapCVP}_{p}^{\prime}$. Assume without
loss of generality that $\boldsymbol{t}\neq\boldsymbol{0}$ (if
$\boldsymbol{t}=\boldsymbol{0}$, simply output an arbitrary YES instance of
$\gamma^{\prime}$-$\mathrm{GapSVP}_{p}$). The reduction outputs
$(B^{\prime},s^{\prime})$, where

$\displaystyle B^{\prime}$
$\displaystyle:=\begin{pmatrix}BTA&BT\boldsymbol{x}-\boldsymbol{t}\\\ \beta
A&\beta\boldsymbol{x}\end{pmatrix}\text{ with
}\beta:=\frac{\gamma^{\prime}s}{\ell^{1/p}\cdot(1-(\alpha\gamma^{\prime})^{p})^{1/p}}\neq
0\ \text{,}$ $\displaystyle s^{\prime}$
$\displaystyle:=(s^{p}+\alpha^{p}\beta^{p}\ell)^{1/p}\ \text{.}$

It is clear that the reduction runs in polynomial time. To show correctness,
we start by showing that the columns of $B^{\prime}$ are linearly independent,
i.e., that $B^{\prime}$ is a lattice basis, and hence the lattice it generates
has rank $R+1$. Recall that $A\in\mathbb{Z}^{n\times R}$ (for some $n$) is a
lattice basis, so it has linearly independent columns. Let
$\boldsymbol{u}\in\mathbb{R}^{R+1}\setminus\\{\boldsymbol{0}\\}$. If $(\beta
A\mid\beta\boldsymbol{x})\cdot\boldsymbol{u}\neq\boldsymbol{0}$ then
$B^{\prime}\boldsymbol{u}\neq\boldsymbol{0}$. Otherwise,
$(A\mid\boldsymbol{x})\cdot\boldsymbol{u}=\boldsymbol{0}$ and so $u_{n+1}\neq
0$ by linear independence of $A$’s columns. Then

$(BTA\mid
BT\boldsymbol{x}-\boldsymbol{t})\cdot\boldsymbol{u}=BT(A\mid\boldsymbol{x})\cdot\boldsymbol{u}-u_{n+1}\cdot\boldsymbol{t}=-u_{n+1}\cdot\boldsymbol{t}\neq\boldsymbol{0}\
\text{,}$

because $\boldsymbol{t}\neq\boldsymbol{0}$ by assumption. Hence
$B^{\prime}\boldsymbol{u}\neq\boldsymbol{0}$, as needed.

We now show the main claim about $(B^{\prime},s^{\prime})$. First, suppose
that the input $\mathrm{GapCVP}^{\prime}_{p}$ instance $(B,\boldsymbol{t},s)$
is a YES instance. Then by Definition 2.8 there exists an
$\boldsymbol{c}\in\\{0,1\\}^{r}$ such that $\lVert
B\boldsymbol{c}-\boldsymbol{t}\rVert_{p}\leq s$. Moreover, by Item 2 of
Definition 2.6, there exists
$\boldsymbol{v}=\boldsymbol{x}+A\boldsymbol{z}\in\boldsymbol{x}+\mathcal{L}(A)$
for some $\boldsymbol{z}\in\mathbb{Z}^{R}$ such that
$\lVert\boldsymbol{v}\rVert_{p}^{p}\leq\alpha^{p}\cdot\ell$ and
$T\boldsymbol{v}=\boldsymbol{c}$. For such a $\boldsymbol{z}$, we have
$T(\boldsymbol{x}+A\boldsymbol{z})=T\boldsymbol{v}=\boldsymbol{c}$ and
therefore

$\displaystyle\lambda_{1}^{(p)}(\mathcal{L}(B^{\prime}))^{p}$
$\displaystyle\leq\lVert B^{\prime}\cdot(\boldsymbol{z},1)\rVert_{p}^{p}$
$\displaystyle=\lVert
BTA\boldsymbol{z}+BT\boldsymbol{x}-\boldsymbol{t}\rVert_{p}^{p}+\beta^{p}\lVert
A\boldsymbol{z}+\boldsymbol{x}\rVert_{p}^{p}$ $\displaystyle=\lVert
B\boldsymbol{c}-\boldsymbol{t}\rVert_{p}^{p}+\beta^{p}\lVert
A\boldsymbol{z}+\boldsymbol{x}\rVert_{p}^{p}$ $\displaystyle\leq
s^{p}+\alpha^{p}\beta^{p}\ell$ $\displaystyle=(s^{\prime})^{p}\ \text{,}$

as needed.

Next, suppose that the input $\mathrm{GapCVP}^{\prime}_{p}$ instance is a NO
instance. We will show that
$\lambda_{1}^{(p)}(\mathcal{L}(B^{\prime}))\geq\gamma^{\prime}s^{\prime}$ by
showing that $\lVert
B^{\prime}\cdot(\boldsymbol{z},w)\rVert_{p}^{p}>(\gamma^{\prime}s^{\prime})^{p}$
for all $(\boldsymbol{z},w)\in\mathbb{Z}^{R+1}\setminus\\{\boldsymbol{0}\\}$,
separately analyzing the cases $w=0$ and $w\neq 0$. When $w=0$, we have that
$\boldsymbol{z}\neq\boldsymbol{0}$, and so by Item 1 of Definition 2.6,

$\lVert
B^{\prime}\cdot(\boldsymbol{z},w)\rVert_{p}^{p}\geq\beta^{p}\cdot\lambda_{1}^{(p)}(\mathcal{L}(A))^{p}>\beta^{p}\cdot\ell\
\text{.}$

And, since
$\beta^{p}\cdot\ell\cdot(1-(\alpha\gamma^{\prime})^{p})=(\gamma^{\prime}s)^{p}$
by definition, we have (by definition of $s^{\prime}$)

$\beta^{p}\cdot\ell\geq(\gamma^{\prime}s)^{p}+(\alpha\beta\gamma^{\prime})^{p}\cdot\ell=(\gamma^{\prime}s^{\prime})^{p}\
\text{.}$

When $w\neq 0$, by the definition of $\mathrm{GapCVP}^{\prime}_{p}$ NO
instances, we have

$\lVert
B^{\prime}\cdot(\boldsymbol{v},w)\rVert_{p}^{p}\geq\mathrm{dist}_{p}(w\boldsymbol{t},\mathcal{L}(B))^{p}>(\gamma
s)^{p}\ \text{.}$

Then, by the definitions of $\gamma$, $\beta$, and $s^{\prime}$, we have

$(\gamma
s)^{p}\geq(\gamma^{\prime})^{p}\cdot\frac{s^{p}}{1-(\alpha\gamma^{\prime})^{p}}=(\gamma^{\prime})^{p}\cdot\left(s^{p}+\frac{(\alpha\gamma^{\prime}s)^{p}}{1-(\alpha\gamma^{\prime})^{p}}\right)=(\gamma^{\prime})^{p}\cdot(s^{p}+\alpha^{p}\beta^{p}\ell)=(\gamma^{\prime}s^{\prime})^{p}\
\text{.}$

The claim follows. ∎

##  Appendix B A Fourier-Analytic Approach to Derandomization

In this appendix we perform and discuss the Fourier-analytic calculation
described in Section 5.2. We introduce definitions and basic facts briefly,
and refer the reader to [Kow10] and [O’D14, Chapter 8] for details. The
_additive Fourier characters_ of $\mathbb{F}_{q}^{k}$ are the homomorphisms
from the additive group $\mathbb{Z}_{q}^{k}$ of $\mathbb{F}_{q}^{k}$ to the
multiplicative group of $\mathbb{C}$. Concretely, they are the $q^{k}$
functions
$\Psi_{\boldsymbol{u}}(\boldsymbol{x}):=\omega^{\langle\boldsymbol{u},\boldsymbol{x}\rangle}$
indexed by $\boldsymbol{u}\in\mathbb{F}_{q}^{k}$, where $\omega$ is an
arbitrary fixed $q$th primitive root of unity (e.g., $\omega=\exp(2\pi i/q)$).
For a function $f:\mathbb{F}_{q}^{k}\to\mathbb{C}$, its $\boldsymbol{u}$th
Fourier coefficient $\hat{f}(\boldsymbol{u})$ for
$\boldsymbol{u}\in\mathbb{F}_{q}^{k}$ is defined as

$\hat{f}(\boldsymbol{u}):=\operatorname*{\mathrm{E}}_{\boldsymbol{b}\sim\mathbb{F}_{q}^{k}}[f(\boldsymbol{b})\overline{\Psi_{\boldsymbol{u}}(\boldsymbol{b})}]\
\text{,}$

and the Fourier expansion of $f$ is

$f(\boldsymbol{x})=\sum_{\boldsymbol{u}\in\mathbb{F}_{q}^{k}}\hat{f}(\boldsymbol{u})\Psi_{\boldsymbol{u}}(\boldsymbol{x})\
\text{.}$

Let
$W=W(k,q):=\\{(1,a,a^{2},\ldots,a^{k-1})^{T}:a\in\mathbb{F}_{q}\\}\subseteq\mathbb{F}_{q}^{k}$
denote the set of columns of the matrix $H_{q}(k,\mathbb{F}_{q})$, and let
$1_{W}:\mathbb{F}_{q}^{k}\to\\{0,1\\}$ denote the indicator function of $W$.
The Fourier coefficients of $1_{W}$ satisfy

$\widehat{1_{W}}(\boldsymbol{u})=\operatorname*{\mathrm{E}}_{\boldsymbol{b}\sim\mathbb{F}_{q}^{k}}[1_{W}(\boldsymbol{b})\overline{\Psi_{\boldsymbol{u}}(\boldsymbol{b})}]=\frac{1}{q^{k}}\sum_{\boldsymbol{b}\in
W}\overline{\Psi_{\boldsymbol{u}}(\boldsymbol{b})}=\frac{1}{q^{k}}\sum_{a\in\mathbb{F}_{q}}\Psi(-p_{\boldsymbol{u}}(a))\
\text{,}$

where $\Psi(x)=\omega^{x}$ is an additive character of $\mathbb{F}_{q}$ and
$p_{\boldsymbol{u}}(x)=\sum_{i=0}^{k-1}u_{i}x^{i}\in\mathbb{F}_{q}[x]$ is a
polynomial of degree less than $k\leq q$.121212Note that formally, we are
indexing the Fourier coefficients by $\mathbb{F}_{q}^{[k]}$, i.e., the
coordinates of $\boldsymbol{u}\in\mathbb{F}_{q}^{[k]}$ are indexed from zero,
by the elements of $[k]=\\{0,\ldots,k-1\\}$. For non-constant polynomials
$p_{\boldsymbol{u}}(x)$, the Weil bound for additive character sums (see
[Kow10, Theorem 3.2]) asserts that

$q^{k}\cdot|\widehat{1_{W}}(\boldsymbol{u})|=\Big{|}\sum_{a\in\mathbb{F}_{q}}\Psi(-p_{\boldsymbol{u}}(a))\Big{|}\leq(k-2)\sqrt{q}\
\text{.}$ (25)

The _convolution_ of two functions $f,g:\mathbb{F}_{q}^{k}\to\mathbb{C}$ is
the function defined as $(f\ast
g)(\boldsymbol{x}):=\operatorname*{\mathrm{E}}_{\boldsymbol{y}\sim\mathbb{F}_{q}^{k}}[f(\boldsymbol{x}-\boldsymbol{y})g(\boldsymbol{y})]$.
Importantly, Fourier coefficients are multiplicative under convolution:

$\widehat{(f\ast
g)}(\boldsymbol{u})=\hat{f}(\boldsymbol{u})\hat{g}(\boldsymbol{u})\ \text{.}$

Furthermore, the $h$-fold convolution of $1_{W}(\boldsymbol{x})$ with itself,
denoted $1_{W}^{(\ast h)}(\boldsymbol{x})$, counts, up to a normalization
factor of $q^{hk}$, the number of sequences
$(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{h})\in W^{h}$ such that
$\sum_{i=1}^{h}\boldsymbol{w}_{i}=\boldsymbol{x}$.131313 Technically, we care
about the number of _multisets_ (rather than sequences) of vectors $V\subseteq
W$, $\left|{V}\right|=h$ such that $\sum_{\boldsymbol{w}\in
V}\boldsymbol{w}=\boldsymbol{x}$. Indeed, there is a bijection between such
multisets and their indicator vectors
$\boldsymbol{y}^{\prime}\in(\mathbb{Z}^{\geq 0})^{q}$, which are such that
$\lVert\boldsymbol{y}^{\prime}\rVert_{1}=h$ and
$H\boldsymbol{y}^{\prime}=\boldsymbol{x}$. However, the number of such
multisets is at most an $h!$ factor less than the number of such sequences,
and this factor seems inconsequential for our purposes; see Equation 26 and
the subsequent discussion.

Let $U_{0}:=\\{(u_{0},0,\ldots,0):u_{0}\in\mathbb{F}_{q}\\}$ denote the set of
coefficient vectors corresponding to constant polynomials, i.e., corresponding
to polynomials $p_{\boldsymbol{u}}(x)=u_{0}$ for $u_{0}\in\mathbb{F}_{q}$.
Putting everything together, we get that

$\displaystyle\frac{1}{q^{hk}}\cdot\Big{|}\\{(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{h})\in
W^{h}:\sum_{i=1}^{h}\boldsymbol{w}_{i}=\boldsymbol{x}\\}\Big{|}$
$\displaystyle=1_{W}^{(\ast h)}(\boldsymbol{x})$
$\displaystyle=\sum_{\boldsymbol{u}\in\mathbb{F}_{q}^{k}}\widehat{1_{W}^{(\ast
h)}}(\boldsymbol{u})\cdot\Psi_{\boldsymbol{u}}(\boldsymbol{x})$
$\displaystyle=\sum_{\boldsymbol{u}\in\mathbb{F}_{q}^{k}}(\widehat{1_{W}}(\boldsymbol{u}))^{h}\cdot\Psi_{\boldsymbol{u}}(\boldsymbol{x})$
$\displaystyle=\sum_{\boldsymbol{u}\in
U_{0}}(\widehat{1_{W}}(\boldsymbol{u}))^{h}\cdot\Psi_{\boldsymbol{u}}(\boldsymbol{x})+\sum_{\boldsymbol{u}\in\mathbb{F}_{q}^{k}\setminus
U_{0}}(\widehat{1_{W}}(\boldsymbol{u}))^{h}\cdot\Psi_{\boldsymbol{u}}(\boldsymbol{x})$
$\displaystyle=\frac{1}{q^{hk}}\sum_{u_{0}\in\mathbb{F}_{q}}(q\cdot\Psi(-u_{0}))^{h}\cdot\Psi(u_{0}x_{0})+\sum_{\boldsymbol{u}\in\mathbb{F}_{q}^{k}\setminus
U_{0}}(\widehat{1_{W}}(\boldsymbol{u}))^{h}\cdot\Psi_{\boldsymbol{u}}(\boldsymbol{x})$
$\displaystyle=\frac{1}{q^{h(k-1)}}\sum_{u_{0}\in\mathbb{F}_{q}}\Psi(u_{0}(x_{0}-h))+\sum_{\boldsymbol{u}\in\mathbb{F}_{q}^{k}\setminus
U_{0}}(\widehat{1_{W}}(\boldsymbol{u}))^{h}\cdot\Psi_{\boldsymbol{u}}(\boldsymbol{x})\
\text{.}$

Now let $\boldsymbol{s}\in\mathbb{F}_{q}^{k}$ be such that $s_{0}=h\bmod q$.
Multiplying the above equality by $q^{hk}$, we have

$\displaystyle\texttt{split}\Big{|}\\{(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{h})\in
W^{h}:\sum_{i=1}^{h}\boldsymbol{w}_{i}=\boldsymbol{s}\\}\Big{|}$
=qh+1+qhk∑u∈Fqk∖U0(^1W(u))h⋅Ψu(s) (26) (27) ≥qh+1-qk⋅((k-2)q)h, (28)

where the equality uses the fact that $s_{0}=h\bmod{q}$, the first inequality
uses the triangle inequality, and the second inequality uses the Weil bound
(Equation 25). Taking $k=q^{\varepsilon^{\prime}}$ for some constant
$\varepsilon^{\prime}>0$, the last bound is roughly $q^{h}-q^{k}\cdot
q^{(1/2+\varepsilon^{\prime})h}=q^{h}-q^{k+(1/2+\varepsilon^{\prime})h}$,
which we want to be subexponentially large in $q$.

However, in order to even make the above quantity positive, we must take
$h>k/(1/2-\varepsilon^{\prime})=(2+\varepsilon)k$ for some constant
$\varepsilon>0$, whereas our application needs $h<2k$ (since we know only that
$\lambda_{1}^{(1)}(\mathcal{L}^{\perp}(H))\geq 2k$). Indeed, this same
condition shows up in related work: our requirement that $h>(2+\varepsilon)k$
is essentially the same as the requirement that “$g\geq(2+\varepsilon)(h+1)$”
in the premise of [CW09, Theorem 2.1], even though the setting there is
slightly different. In particular, in each case the “$2$” in the
$2+\varepsilon$ factor comes from (the inverse of) the exponent in the Weil
bound’s $q^{1/2}$ factor.

#### Toward making the approach work.

The above argument ‘just barely’ fails—i.e., improving the constant from
$2+\varepsilon$ to $2-\varepsilon$ would suffice for our purposes—so one might
hope to make it work by showing that one of the inequalities in Equation 26 is
loose. First, one might hope to strengthen the Weil bound by reducing its
$\sqrt{q}$ factor to $q^{1/2-\delta}$ for some constant $\delta>0$.
Furthermore, the Weil bound is a “worst-case” statement about character sums
evaluated on _arbitrary_ polynomials, whereas for the argument above an
improvement to $q^{1/2-\delta}$ on average (i.e., for _random_ polynomials)
would suffice. Unfortunately, as shown in [Saw14], the $\sqrt{q}$ factor is
optimal even for such an “average-case Weil bound.” So, the main possibility
for improvement is to avoid naïvely using the triangle inequality in the first
inequality. Indeed, there could be substantial “phase cancellations” among the
terms in the sum $\sum_{\boldsymbol{u}\in\mathbb{F}_{q}^{k}\setminus
U_{0}}(\widehat{1_{W}}(\boldsymbol{u}))^{h}\cdot\Psi_{\boldsymbol{u}}(\boldsymbol{s})$
for some special (or perhaps arbitrary) syndromes $\boldsymbol{s}$. It seems
likely that such cancellations occur, but we do not know how to show it. (We
emphasize that Equation 26 holds for _any_ $\boldsymbol{s}$ with $s_{0}=h\bmod
q$; it is agnostic to the rest of $\boldsymbol{s}$.)

Finally, we note another possible modification to the argument, which is to
work with the “symmetrized set” $W^{\prime}:=\pm
W=\\{\pm(1,a,a^{2},\ldots,a^{k-1})^{T}:a\in\mathbb{F}_{q}\\}$ instead of $W$.
A multiset of $h$ vectors from $W^{\prime}$ naturally corresponds to a
“signed” vector $\boldsymbol{y}^{\prime}\in\mathbb{Z}^{q}$, whereas such a
multiset of vectors in $W$ corresponds to an “unsigned” vector
$\boldsymbol{y}\in(\mathbb{Z}^{\geq 0})^{q}$. That is, we can count coset
vectors having negative coordinates when working with $W^{\prime}$ instead of
$W$. However, it is unclear to us how to use this relaxation to any advantage.