Search-to-Decision Reductions for Lattice Problems with
Approximation Factors (Slightly) Greater Than One

arXiv:1512.04138v5 [cs.CC] 24 Apr 2017

Noah Stephens-Davidowitz∗
Courant Institute of Mathematical Sciences,
New York University.
noahsd@gmail.com

Abstract
We show the first dimension-preserving search-to-decision reductions for approximate SVP
and CVP. In particular, for any γ ≤ 1 + O(log n/n), we obtain an efficient dimension-preserving
reduction from γO( n/ log n) -SVP to γ-GapSVP and an efficient dimension-preserving reduction
from γO( n) -CVP to γ-GapCVP. These results generalize the known equivalences of the search and
decision versions of these problems in the exact case when γ = 1. For SVP, we actually obtain
something slightly stronger than a search-to-decision reduction—we reduce γO( n/ log n) -SVP to γunique SVP, a potentially easier problem than γ-GapSVP.

Disclaimer
When I wrote this paper, I was unaware of prior work due to Cheng [Che13] and Hu and Pan [HP14].
Cheng gives an efficient dimension-preserving search-to-decision reduction for approximate SVP
that is essentially identical to the deterministic SVP reduction that I present in Theorem 1.3. Hu and
Pan show how to extend this to approximate CVP, which I also do in Theorem 1.4. In particular, my
claim that the reductions presented in this paper were the first such reductions is clearly false.
I thank Priyanka Mukhopadhyay and Divesh Aggarwal for bringing this to my attention, and I
apologize to Cheng, Hu, and Pan for failing to properly cite them originally.
The main results of this paper (i.e., Theorems 1.1 and 1.2) are still novel and achieve better parameters than the similar reductions in [Che13, HP14]. I leave the rest of this paper as it was before I
learned about [Che13, HP14].

1

Introduction

A lattice L = {∑ ai bi : ai ∈ Z } ⊂ R n is the set of all integer linear combinations of linearly independent basis vectors b1 , . . . , bn ∈ R n .
The two most important computational problems on lattices are the Shortest Vector Problem
(SVP) and the Closest Vector Problem (CVP). For any approximation factor γ = γ(n) ≥ 1, γ-SVP
is the search problem that takes as input a lattice and asks us to find a non-zero vector in this lattice
whose length is within a factor of γ of the minimal possible value. γ-CVP is the search problem
that takes as input both a lattice and a target vector t ∈ R n and asks us to find a vector in L whose
distance to t is within a factor of γ of the minimal distance. The natural decisional variants of these
∗ Supported

by the National Science Foundation (NSF) under Grant No. CCF-1320188. Any opinions, findings, and
conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the
views of the NSF.

1

problems are called GapSVP and GapCVP respectively. Specifically, γ-GapSVP asks us to approximate the length of the shortest non-zero vector of a lattice up to a factor of γ, and γ-GapCVP asks us
to approximate the distance from t to the lattice up to a factor of γ.
All four of these problems are interesting for a wide range of approximation factors γ. Indeed,
algorithms for these problems have found a remarkable number of applications in computer science
(e.g., [LLL82, Len83, Kan87, Odl90, JS98, NS01, DPV11]). And, over the past twenty years, many
strong cryptographic primitives have been constructed with their security based on the (worst-case)
hardness of γ-GapSVP with approximation factors γ = poly(n) that are polynomial in the dimension
(e.g., [Ajt96, MR07, GPV08, Gen09, Pei09, Reg09, LPR10, BV11, BV14]).
Due to their importance, there has been much work towards understanding the relationship between these problems (and their many close relatives). Since the fastest known algorithms for these
problems run in time that is exponential in the dimension n, even with γ = poly(n), dimensionpreserving reductions between lattice problems are of particular importance [Kan87, GMSS99, Mic08,
LM09, Ste15, Ste16]. Perhaps the best-known such reduction is the efficient dimension-preserving
reduction from γ-SVP to γ-CVP (and from γ-GapSVP to γ-GapCVP) due to Goldreich, Micciancio,
Safra, and Seifert [GMSS99]. This proves that the time complexity of γ-SVP, as a function of the dimension n, cannot be more than a polynomial factor higher than the time complexity of γ-CVP. We
stress that we could not reach this conclusion if the reduction increased the dimension significantly,
which is why dimension-preserving reductions interest us.
As a much simpler example, we note that there is a trivial dimension-preserving reduction from
γ-GapSVP to γ-SVP that works by just finding a short vector in the input lattice and outputting its
length. There is of course a similar reduction for CVP as well. More interestingly, there are relatively simple dimension-preserving search-to-decision reductions in the special case when γ = 1—i.e.,
finding exact shortest vectors is no harder than computing the exact lengths of shortest vectors, and
finding exact closest vectors to targets is no harder than computing the exact distances between targets and lattices. (See, e.g., [Kan87] or [MG02], or simply consider the reductions in the sequel with
γ = 1.) However, prior to this work, there were no known search-to-decision reductions for either
SVP or CVP for any approximation factor γ > 1.
This state of affairs was quite frustrating because, with very few exceptions, our best algorithms
for the decision problems work by just solving the corresponding search problem. In other words,
we don’t really know how to “recognize” that a lattice has a short non-zero vector (or a vector close
to some target) without just finding such a vector.1 If there are better techniques, then we would be
thrilled to find them! But, if this extremely natural approach is actually optimal, then it would be
nice to prove it by formally reducing the search problems to their decision variants. (Of course, it is
conceivable that the search and decision problems have the same complexity, even if no search-todecision reduction exists. One might reasonably argue that this is even the most likely scenario. But,
we can at least hope that Nature would not be so unprincipled.)
The ideal positive result in this area would be an efficient dimension-preserving reduction from
γ-SVP to γ-GapSVP for all γ ≥ 1, and likewise for CVP. But, this seems completely out of reach at the
moment (perhaps because no such reductions exist). So, as a more approachable goal, we can try to
find non-trivial reductions that lose in the approximation factor. Indeed, as we mentioned above, we
know that search and decision problems are equivalent in the exact case. Can it truly be the case that
equivalence holds when γ = 1, but nothing non-trivial holds for any γ > 1—even, say, a reduction
from n100 -CVP to (1 + 2−n )-GapCVP?!
p
author knows of three rather specific exceptions. There is an efficient algorithm for n/ log n-GapCVP with
preprocessing [AR05], while the best efficient algorithm for search CVP with preprocessing only achieves factor of
p
γ = n/ log n [DRS14]. There is a 2n/2+o ( n)-time algorithm for 2-GapSVP for which no analogous search algorithm is
known [ADRS15]. And, in the special case of ideal lattices in the ring of integers of a number field, γ-GapSVP is trivial for
some values of γ for which γ-SVP appears to be hard. (See, e.g., [PR07].)
1 The

2

1.1

Our results

We make some progress towards resolving these issues by presenting dimension-preserving searchto-decision reductions for both approximate SVP and approximate CVP. Our reductions generalize
the known equivalences in the exact case. But, they lose quite a bit in the approximation factor,
and their running times depend on the decision approximation factor. They are therefore primarily
interesting when the decision approximation factor is very close to one, as we explain below.
Theorem 1.1 (SVP reduction). For any γ = γ(n) ≥ 1 and a = a(n) ≥ log(n + 1), there is a dimensionpreserving (randomized) reduction from γn/a -SVP to γ-GapSVP that runs in time 2O( a) · γO(n) .
Theorem 1.1 is primarily interesting for any γ ≤ 1 + O(log n/n) and a = Θ(log n). For such
parameters, the running time is poly(n) and the search approximation factor is γO(n/ log n) ≤ O(1).
However, we note that the theorem is non-trivial whenever we have 1 < γ ≤ 1 + ε and a ≤ εn, where
ε > 0 is some small universal constant.2
We actually reduce γn/a -SVP to γ-unique SVP, which is a potentially easier problem than γGapSVP. (See Definition 2.12 for the formal definition of γ-unique SVP, and Theorem 3.3 for the
reduction.) The reduction described above then follows from this result together with Lyubashevsky
and Micciancio’s reduction from γ-unique SVP to γ-GapSVP [LM09]. We obtain
√ a few additional
corollaries as well. E.g., this shows a dimension-preserving reduction from n-CVP to γ-unique
SVP (and thus to γ-GapSVP as well) that runs in time poly(n) · γO(n) . This also gives an alternative and arguably more natural proof of Aggarwal and Dubey’s result that γ-unique SVP is NP-hard
(under randomized reductions) for γ ≤ 1 + 1/nε for any constant ε > 0 [AD15].
With some more work, we are also able to use our SVP reduction to derive the following searchto-decision reduction for CVP.
Theorem 1.2 (CVP reduction). For any γ = γ(n) ≥ 1 and ℓ = ℓ(n) ≥ 1, there is a dimension-preserving
(randomized) reduction from γn/ℓ -CVP to γ-GapCVP that runs in time nO(ℓ) · γO(n) .
This result is primarily interesting when ℓ is any constant and γ ≤ 1 + O(log n/n), in which case
the reduction runs in polynomial time and the search approximation factor is γO(n) ≤ poly(n). But,
it is still non-trivial for 1 < γ ≤ 1 + ε and ℓ ≤ εn/ log n, where ε > 0 is some universal constant.
We actually show a (deterministic) nO(ℓ) -time reduction from γn/ℓ -CVP to γ-GapCVP that works
in the presence of a poly(n)-SVP oracle. (See Theorem 4.1.) The above result then follows from
instantiating this oracle via our SVP reduction.
Finally, we show deterministic reductions that achieve much worse parameters.
Theorem 1.3 (Deterministic SVP reduction). For any γ = γ(n) ≥ 1 and p = p(n) ≥ 2, there is
a deterministic dimension-preserving reduction from γ′ -SVP to γ-GapSVP that runs in time poly(n) · p,
2
where γ′ := γO(n / log p) .
Theorem 1.4 (Deterministic CVP reduction). For any γ = γ(n) ≥ 1 and p = p(n) ≥ 2, there is
a deterministic dimension-preserving reduction from γ′ -CVP to γ-GapCVP that runs in time poly(n) · p,
2
where γ′ := γO(n / log p) .
It is easy to see that our randomized reductions always give a better trade-off between the approximation factor and running time for non-trivial parameters. So, these new reductions are primarily interesting because they are deterministic and because they demonstrate additional potential
approaches for future work in this area.
We note that all of our reductions are Cook reductions. (They make many oracle calls, sometimes
adaptively.)
2 In

particular, we can choose ε so that, with a = εn and γ ≤ 1 + ε, we get a reduction from γ1/ε -SVP to γ-GapSVP
that runs in time O(2n ). For larger values of a or γ, the reduction is subsumed by the known 2n+o ( n)-time algorithm for
SVP [ADRS15].

3

1.2

Techniques

SVP. Our main SVP reduction works by finding a sublattice of the input lattice that has one relatively short vector but a significantly longer “second-shortest vector.” (I.e., we wish to find a sublattice of the input lattice that satisfies the promise of γ-unique SVP. See Definition 2.12.) To accomplish
this, we use lattice sparsification, which was introduced by Khot [Kho05] and refined in a series of
works [DK13, DRS14, Ste16].
The “sparsified” sublattice is given by

L′ := {y ∈ L : hz, B−1 yi ≡ 0 mod p} ,
where p is some prime and z ∈ Z np is chosen uniformly at random. We would like to say that
each short vector in L will land in L′ with probability roughly 1/p, independently of all other short
vectors. Of course, if x, y ∈ L and x = ky for some k 6≡ 0 mod p, then clearly x will land in L′ if
and only if y does. So, we cannot have anything close to independence in this case. Luckily, [Ste16]
shows that this is essentially “the only bad case.”
Specifically, a lattice vector x ∈ L is non-primitive if x = ky for some k ≥ 2 and y ∈ L. Otherwise,
x is primitive. (Note in particular that a shortest lattice vector is always primitive.) [Ste16] showed
that sparsification behaves very nicely if we restrict our attention to primitive short lattice vectors.
I.e., the distribution of short primitive vectors in the sparsified sublattice L′ is statistically close to the
distribution that selects each short primitive vector from L independently with probably 1/p. (See
Theorem 3.1 for the precise statement, which is taken directly from [Ste16, Theorem 4.1].)
So, let ξ (L, r) be the number of primitive lattice points of length at most r. Suppose there exists
some radius r such that ξ (L, γr) is not much larger than ξ (L, r).3 Then, if we take p ≈ ξ (L, γr), we
can expect L′ to contain a primitive vector of length at most r but no other primitive vectors of length less
than γr with probability Θ(ξ (L, r)/ξ (L, γr)). In other words, with this probability, L′ will be a valid
instance of γ-unique SVP with λ1 (L′ ) ≤ r, so that we can use an oracle for γ-unique SVP to find a
non-zero lattice vector of length at most r.
The parameter a in the reduction determines how large of a ratio ξ (L, γr)/ξ (L, r) we are “willing
to tolerate.” In particular, a simple proof shows that, for a ≥ n log γ, there is always a radius r ≤
γn/a · λ1 (L) such that this ratio is bounded by 2O( a) . We can therefore obtain a valid γ-unique SVP
instance with λ1 (L′ ) ≤ r ≤ γn/a · λ1 (L) with probability at least 2−O( a) . So, our main reduction
essentially works by sampling L′ repeatedly, a total of 2O( a) times, and calling its γ-unique SVP
oracle on each sampled sublattice L′ .
CVP. Our search-to-decision reduction for CVP is a simple “guided” variant of Babai’s celebrated
nearest-hyperplane algorithm [Bab86]. Babai’s algorithm works by dividing the lattice into (n − 1)dimensional lattice hyperplanes and then restricting our search to the closest hyperplane to the target.
However, it is possible that the closest lattice hyperplane does not actually contain very close lattice
points. As a result, Babai’s algorithm can lead to quite large approximation factors.
So, we instead use our GapCVP oracle to “test many nearby hyperplanes” to find one that is
guaranteed to contain a γ-approximate closest lattice point. By repeating this n times over hyperplanes of progressively lower dimensions, we will find a γn -approximate closest vector to the target.
To find a γn/ℓ -approximate closest vector, we do the same thing with all nearby (n − ℓ)-dimensional
hyperplanes.
In order to make this algorithm efficient, we need to limit the number of hyperplanes that we
must consider. This amounts to finding a short non-zero vector in the dual lattice. We can find such
a vector by using our search-to-decision reduction for SVP (together with the known reduction from
GapSVP to GapCVP [GMSS99]). Unfortunately, this costs us a factor of γO(n) in the running time.
3 It might be helpful to think of the heuristic that ξ (L, γr ) /ξ (L, r ) ≈ γ n . This holds in the limit as r → ∞, and it holds
for random lattices in expectation.

4

Deterministic reductions. Our alternative deterministic search-to-decision reductions for SVP and
CVP are very similar to the reduction from unique SVP to GapSVP in [LM09]. They essentially work
by finding the coordinates of a short (or close) lattice vector “bit by bit.” I.e., in the CVP case, we
first use our GapCVP oracle to compare the distance from the target to all lattice vectors whose last
coordinate is even with its distance from all lattice vectors whose last coordinate is odd. If, say, the
odd estimate is lower, then we restrict our attention to the lattice coset of all lattice vectors whose last
coordinate is odd. We choose the remaining bits similarly, eventually obtaining the coordinates of a
relatively close lattice vector. Our more general reductions follow from “working in base p instead
of base 2.”

1.3

Related work

Some efficient dimension-preserving search-to-decision reductions were known for other lattice problems prior to this work. For example, Regev showed such a reduction for Learning with Errors,
an important average-case lattice problem with widespread applications in cryptography [Reg09].
(Both the search and decision versions of LWE are average-case problems.) And, Liu, Lyubashevsky,
and Micciancio implicitly use a search-to-decision reduction for Bounded Distance Decoding in their
work [LLM06]. Finally, Aggarwal and Dubey showed how to use some of the ideas from [LM09]
to obtain a search-to-decision reduction for unique SVP [AD15]. While all of these works are quite
interesting, they are concerned with promise problems, and not the two most important and natural
lattice problems, SVP and CVP.
More generally, this work can be seen as part of the ongoing study of the relationships between
lattice problems under dimension-preserving reductions. By now, this area has become quite fruitful
(e.g., [Kan87, GMSS99, Mic08, LM09, Ste16]). See [Ste15] for a brief survey of well-known dimensionpreserving reductions between various lattice problems.
Most prior work used sparsification to remove a relatively small number of “annoying” short
vectors from a lattice without losing too many “good” short vectors (e.g., [Kho05, DK13, DRS14]). In
our main SVP reduction, our goal is instead to remove “all but one” short vector. (Independent work
of Bai, Wen, and Stehlé used sparsification in a similar way to reduce Bounded Distance Decoding to
unique SVP [BWS16].) To obtain our result, we rely heavily on the sparsification analysis of [Ste16],
which is tighter and more general than prior work.
Interestingly, Kumar and Sivakumar used a procedure that is very similar to sparsification in their
study of unique SVP, published in 2001 [KS01]. Indeed, they repeatedly sparsify a lattice with p = 2
to obtain a sequence of sublattices such that at least one of these sublattices (1) contains a shortest
non-zero vector of the original lattice; and (2) contains no other vectors of this length (up to sign, of
course). However, the length of the “second-shortest vector” can be arbitrarily close to that of the
shortest vector in their construction, even in a fixed dimension n. I.e., they use a restricted form of
sparsification to effectively reduce 1-SVP to 1-unique SVP. Our main SVP reduction can be thought of
as an updated version of their result. We use tools that were not available fifteen years ago to obtain a
lower bound on the ratio between the shortest vector and the “second-shortest vector” that depends
only on the dimension n.
To prove hardness of (1 + 1/poly (n))-unique SVP, Aggarwal and Dubey used the result of Kumar
and Sivakumar to show a reduction from SVP to γ-unique SVP that works for a restricted subset of
lattices [AD15]. In particular, Aggarwal and Dubey chose a set of lattices such that, over these lattices
(1) SVP is NP-hard (as proven by Khot [Kho05]); and (2) this reduction yields γ = 1 + 1/poly(n). In
contrast, we directly reduce 2-SVP to (1 + 1/poly(n))-unique SVP over all lattices by using a much
stronger (and unfortunately more complicated) form of Kumar and Sivakumar’s reduction.
While the author knows of no other use of our specific variant of Babai’s algorithm, we feel that
it is quite natural and not particularly novel. For example, a similar idea was used in a different
context by Micciancio [Mic08, Corollary 7]. Our primary contribution on this front is the observation
that this method gives a non-trivial search-to-decision reduction when the decision approximation
factor is very small, and when it is combined with our SVP reduction.
5

We rely heavily on Lyubashevsky and Micciancio’s dimension-preserving reduction from γ-unique
SVP to γ-GapSVP [LM09]. Their result is necessary to prove Theorem 1.1, and our deterministic
“bit-by-bit” SVP reduction is very similar to Lyubashevsky and Micciancio’s reduction. The main
difference between our deterministic SVP reduction and that of Lyubashevsky and Micciancio is
that [LM09] work only with lattices that satisfy the promise of γ-unique SVP. They show that this
promise is enough to guarantee that the γ-GapSVP oracle essentially behaves as an exact GapSVP oracle. In contrast, our reduction works over general lattices, so we have to worry about accumulating
error. (We also use a different method to “reduce the dimension of the lattice.”)

1.4

Directions for future work

We view this paper as a first step towards a better understanding of the relationship between the
search and decision variants of approximate SVP and CVP. In particular, we show that efficient,
dimension-preserving search-to-decision reductions do in fact exist for approximation factors γ >
1. Prior to this work, one might have reasonably conjectured that such reductions do not exist for
non-trivial parameters. But, our reductions lose quite a bit in the approximation factor, and the
running times of our main reductions blow up quickly as the approximation factor increases. They
are therefore primarily interesting for very small approximation factors γ = 1 + o(1).
Results for such low values of γ have sometimes led to similar results for larger approximation
factors. For example, hardness of γ-GapSVP was originally proven for γ = 1 + 2−poly(n) [Ajt98],
and then for γ = 1 + 1/poly(n) [CN99], before better inapproximability results were found [Mic01,
Kho05, HR12]. We therefore ask whether better search-to-decision reductions exist, and in particular,
whether non-trivial efficient dimension-preserving reductions exist for larger approximation factors.
More specifically, we note that our main reductions are only efficient when the decision approximation factor is γ = 1 + O(log n/n) because their running time is proportional to γO(n) . This seems
inherent to our technique in the case of SVP, and the CVP reduction suffers the same fate because it
uses the SVP reduction as a subroutine. However, we see no reason why the running time should
necessarily increase with the approximation factor, and this might simply be an artifact of our techniques. So, perhaps we can find reductions that do not have this problem. (One might try, for example, to eliminate the need for the SVP oracle in our CVP reduction.) Indeed, the reductions in
Section 5 manage to avoid this pitfall, but they blow up the approximation factor much more and
never actually outperform our main reductions.
In the other direction, we ask whether the search and decision versions of SVP and CVP can
be separated in any way. I.e., can we show that, for some γ > 1, there is no efficient dimensionpreserving reduction from γ-CVP to γ-GapCVP or no such reduction from γ-SVP to γ-GapSVP
(under reasonable complexity-theoretic assumptions or even restrictions on the behavior of the reduction)? Can we find algorithms that solve the decision problems faster than our current searchbased techniques allow (something more general than the rather specific examples mentioned in
footnote 1)? Of course, any such result would be a major breakthrough.

Acknowledgments
I would like to thank Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Daniel Dadush, Daniele Micciancio, and Oded Regev, all of whom provided helpful commentary on earlier drafts of this paper.
In particular, Divesh noted that our SVP reduction shows
hardness of unique SVP (Corollary 3.5),
√
and Daniele noted that it implied a reduction from n-CVP to γ-GapSVP (Corollary 2.17). I also
thank the anonymous reviewers for their helpful comments.

6

2

Preliminaries

We write log x for the logarithm of x in base 2. We write kxk for the Euclidean norm of x ∈ R n . We
omit any mention of the bit length of the input throughout. In particular, all of our algorithms take as
input vectors in R n (with some reasonable representation) and run in time f (n) · poly(m) for some f ,
where m is the maximal bit length of an input vector. We are primarily interested in the dependence
on n, so we suppress the factor of poly(m).

2.1

Lattice basics

A rank d lattice L ⊂ R n is the set of all integer linear combinations of d linearly independent vectors
B = (b1 , . . . , bd ). B is called a basis of the lattice and is not unique. We write L(B) to signify the
lattice generated by B. By taking the ambient space to be span(L), we can implicitly assume that a
lattice has full rank n, and we therefore will often implicitly assume that d = n.
The dual lattice is
L∗ := {w ∈ span(L) : ∀y ∈ L, h w, yi ∈ Z } .

Similarly, the dual basis B∗ := B(B T B)−1 = (b1∗ , . . . , b∗d ) is the unique list of vectors in span(L)
satisfying hb∗i , b j i = δi,j . L∗ is itself a rank d lattice with basis B∗ .
We write λ1 (L) := minx∈L\{0} kxk for the length of the shortest non-zero vector in the lattice.
Similarly, we write λ2 (L) := min{r > 0 : dim(span(L ∩ rB2n )) ≥ 2} for the length of the shortest
lattice vector that is linearly independent from a lattice vector of length λ1 (L). For any point t ∈ R n ,
we write dist(t, L) := minx∈L kx − tk for the distance between t and L. The covering radius µ(L) :=
maxt∈span(L) dist(t, L) is the maximal such distance achievable in the span of the lattice.
The following two bounds will be useful.4
Theorem 2.1 ([BHW93, Theorem 2.1]). For any lattice L ⊂ R n and r > 0,

|{y ∈ L : kyk ≤ rλ1 (L)}| ≤ 2⌈2r⌉ n − 1.
Lemma 2.2 ([Ban93, Theorem 2.2]). For any lattice L ⊂ R n , λ1 (L∗ ) · µ(L) ≤ n/2.
We derive a simple though rather specific corollary of Lemma 2.2 that we will use twice. The
corollary says that a dual vector w ∈ L∗ \ {0} that is relatively short, kwk ≤ γ · λ1 (L∗ ), can be used
to partition L into (n − 1)-dimensional lattice hyperplanes, such that the closest vector to any target
t must lie in one of the O(γn) hyperplanes closest to t.
Corollary 2.3. For any lattice L ⊂ R n with basis (b1 , . . . , bn ) and associated dual basis (b1∗ , . . . , b∗n ), γ ≥ 1,
and any target t ∈ R n , if kb1∗ k ≤ γ · λ1 (L∗ ), then any closest lattice vector to t must lie in a lattice hyperplane
L′ + ib1 , where L′ := L(b2 , . . . , bn ) and i is an integer with |i − hb1∗ , ti| ≤ γn/2.
Proof. Let y ∈ L be a closest lattice vector to t. It follows from the definition of a lattice that y ∈
L′ + ib1 for some integer i = hb1∗ , yi. We have

|i − hb1∗ , ti| = |h b1∗ , y − ti| ≤ kb1∗ kky − tk ≤ γλ1 (L∗ ) · µ(L) ≤ γn/2 ,
where we have used Lemma 2.2.
4 We

note that tighter bounds exist for the number of lattice points in a ball of radius r [KL78, PS09], but we use the
bound of [BHW93] because it is simpler. Using a tighter bound here would improve the hidden constants in the exponents
of our running times.

7

2.2

LLL-reduced bases

e1 , . . . , b
e n ) by
Given a basis, B = (b1 , . . . , bn ), we define its Gram-Schmidt orthogonalization (b
ei = π
b
{ b1 ,...,b i −1 } ⊥ ( b i ) ,

and the Gram-Schmidt coefficients µi,j by

µi,j =

e ji
hbi , b
.
e j k2
kb

Here, π A represents orthogonal projection onto the subspace A and {b1 , . . . , bi−1 }⊥ denotes the subspace of vectors in R n that are orthogonal to b1 , . . . , bi−1 .
Definition 2.4. A basis B = (b1 , . . . , bn ) is LLL-reduced if
1. for 1 ≤ j < i ≤ n, |µi,j | ≤ 1/2; and
e i − 1 k2 .
e i k2 ≥ (3/4 − µ2 ) · kb
2. for 2 ≤ i ≤ n, kb
i,i−1

Theorem 2.5 ([LLL82]). There exists an efficient algorithm that takes as input a (basis for) a lattice and
outputs an LLL-reduced basis for the lattice.
Lemma 2.6. For any lattice L ⊂ R n with LLL-reduced basis B = (b1 , . . . , bn ) and y = ∑ ai bi ∈ L, we
have
ky k
|ai | ≤ 23n/2−i ·
,
λ1 (L)
for all i.
e i k ≥ kb1 k/2i/2 ≥
Proof. It follows immediately from the definition of an LLL-reduced basis that kb
n/2
λ1 (L)/2
for all i. For each i, we have
n

ky k ≥

∑ |aj µ j,i | · kbe i k =

j=1





e i k ≥ | ai | − 1
|a j µ j,i | · kb
2
j= i+1
n

| ai | −

∑

n

∑
j= i+1


|a j | · 2−n/2 · λ1 (L) .

In particular, | an | ≤ 2n/2 · kyk/λ1 (L). We assume for induction that | a j | ≤ 23n/2− j · kyk/λ1 (L) for
all j with i < j ≤ n. Then, plugging in to the above, we have

kyk ≥ |ai | · 2−n/2 · λ1 (L) −

n

∑
j= i+1

2n− j−1 kyk ≥ | ai | · 2−n/2 · λ1 (L) − 2n−i−1 · kyk .

The result follows by rearranging.
Lemma 2.7 ([Bab86]). If B = (b1 , . . . , bn ) is an LLL-reduced basis, then µ(L) ≤

2.3

Lattice problems

√

e n k.
n2n/2−1 · kb

We now list the computational problems that concern us. All of the below definitions are standard.
Definition 2.8. For any parameter γ = γ(n) ≥ 1, γ-SVP (the Shortest Vector Problem) is the search problem
defined as follows: The input is a basis B for a lattice L ⊂ R n . The goal is to output a lattice vector x with
0 < kxk ≤ γλ1 (L).
Definition 2.9. For any parameter γ = γ(n) ≥ 1, γ-CVP (the Closest Vector Problem) is the search problem
defined as follows: The input is a basis B for a lattice L ⊂ R n and a target vector t ∈ R n . The goal is to output
a lattice vector x with kx − tk ≤ γ dist(t, L).
8

Definition 2.10. For any parameter γ = γ(n) ≥ 1, the decision problem γ-GapSVP is defined as follows:
The input is a basis B for a lattice L ⊂ R n and a number d > 0. The goal is to output yes if λ1 (L) < d and
no if λ1 (L) ≥ γ · d.
Definition 2.11. For any parameter γ = γ(n) ≥ 1, the decision problem γ-GapCVP is defined as follows:
The input is a basis B for a lattice L ⊂ R n , a target t ∈ R n , and a number d > 0. The goal is to output yes if
dist(t, L) < d and no if dist(t, L) ≥ γ · d.
Definition 2.12. For any parameter γ = γ(n) ≥ 1, γ-uSVP (the Unique Shortest Vector Problem) is
the search promise problem defined as follows: The input is a basis B for a lattice L ⊂ R n with λ2 (L) ≥
γ(n) · λ1 (L). The goal is to output a lattice vector x with kxk = λ1 (L).

2.4

Known results

We will need the following known reductions and hardness results.
Theorem 2.13 ([Kho05]). For any constant γ ≥ 1, γ-GapSVP (and therefore γ-SVP) is NP-hard under
randomized reductions.
Theorem 2.14 ([GMSS99]). For any γ ≥ 1, there is an efficient dimension-preserving reduction from γGapSVP to γ-GapCVP (and from γ-SVP to γ-CVP).
Theorem 2.15 ([LM09, Theorem 6.1]). For any 1 ≤ γ(n) ≤ poly(n), there is an efficient dimensionpreserving reduction from γ-uSVP to γ-GapSVP.
√
√
Theorem 2.16 ([MG02, Theorem 4.2]). There is an efficient reduction from n-CVP to 2-SVP. Furthermore, all of the oracle calls of the reduction are made in dimension n + 1, where n is the input dimension.
Reductions like that of Theorem 2.16 that increase the dimension by one are good enough for
nearly all applications of perfectly dimension-preserving reductions. But, we can use a simple idea
to convert Theorem 2.16 into a reduction that preserves the dimension exactly. (Micciancio uses
essentially the same trick in the proof of [Mic08, Corollary 7].)
√
√
Corollary 2.17. There is a dimension-preserving efficient reduction from n-CVP to 2-SVP.
Proof. On input t ∈ R n and a lattice L ⊂ R n , the reduction first uses its SVP oracle to find a vector
b1∗ ∈ L∗ in the dual with 0 < kb1∗ k < 2λ1 (L∗ ). Let B∗ := (b1∗ , . . . , b∗n ) be a basis for L∗ , and let
B = (b1 , . . . , bn ) be the associated primal basis. (Since b1∗ is a primitive lattice vector, it is always
possible to find such a basis.) Let L′ := L(b2 , . . . , bn ) be the lattice generated by B with the first
basis vector removed. Finally, let a := hb1∗ , ti. For i = ⌊ a⌋ − n, . . . , ⌈ a⌉ + n, the reduction runs the
procedure from Theorem 2.16 on input t − ib1 and L′ , receiving as output yi ∈ L′ . The reduction
then simply outputs a closest vector to t amongst the vectors yi + ib1 ∈ L.
It is clear that the reduction is efficient. Furthermore, note that the reduction only uses the procedure from Theorem 2.16 with (n − 1)-dimensional input. (Formally, we must project L′ and t − ib1
onto span(L′ ) ∼
= R n−1.) Since that procedure increases dimension by one, this new reduction preserves dimension. For correctness, we note that Corollary 2.3 implies that there is a closest vector to
t in one of the lattice hyperplanes L′ + iyi . The result then follows from Theorem 2.16.

2.5

A note on decision and estimation

Formally, we consider gapped decision problems, which take as input a number d > 0 and some additional input I and require us to output YES if f ( I ) ≤ d and NO if f ( I ) > γd, where f is some
function and γ is the approximation factor. (For example, I may be some representation of a lattice
and f ( I ) may be the length of the shortest vector in the lattice.) However, it is sometimes convenient
to work with estimation problems, which take only I as input and ask for a numerical output d˜ with
f ( I ) ≤ d˜ ≤ γ f ( I ).
9

For the specific problems that we consider (and most “sufficiently nice” problems), the estimation
variants are equivalent to the gapped decision problems as long as the lattice is “represented reasonably” by the input. For example, if f ( I ) can be represented as a string of length at most poly(| I |)
(e.g., f ( I ) might be a rational number with bounded numerator and denominator), then we can use
binary search and a gapped decision oracle to estimate f ( I ) efficiently. This is true, for example,
whenever the input is interpreted as a list of vectors with rational coordinates, using the standard
representation of rational numbers. (See [MG02] for a careful discussion of this and related issues
in the context of lattice problems.) We therefore make no distinction between gapped decision problems and estimation problems in the sequel, without worrying about the specific form of our input,
or more generally, the specific representation of numbers.

3
3.1

Reducing SVP to uSVP (and GapSVP) via sparsification
Sparsification

For a lattice L ⊂ R n , we write Lprim for the set of all primitive vectors in L, and ξ (L, r) := |Lprim ∩
rB2n |/2 for the number of primitive lattice vectors contained in a (closed) ball of radius r around
the origin (counting x and −x as a single vector). The following theorem from [Ste16] shows that
sparsification behaves nicely with respect to primitive vectors, which is enough for our use case.
Theorem 3.1 ([Ste16, Theorem 4.1]). For any lattice L ⊂ R n with basis B, primitive lattice vectors
y0 , y1 , . . . , y N ∈ Lprim with yi 6= ±y0 for all i > 0, and prime p ≥ 101, if ξ (L, k yi k) ≤ p/(20 log p)
for all i, then


N
1
1
− 2 ≤ Pr hz, B−1 y0 i ≡ 0 mod p and hz, B−1 yi i 6≡ 0 mod p ∀i > 0 ≤ ,
p
p
p

where z ∈ Z np is chosen uniformly at random.

From this, we can immediately derive the following proposition, which is a slight variant of [Ste16,
Proposition 4.2].
Proposition 3.2. There is an efficient (randomized) algorithm that takes as input a basis B for a lattice L ⊂ R n
and a prime p ≥ 101 and outputs a full-rank sublattice L′ ⊆ L such that for any r1 , r2 , with λ1 (L) ≤ r1 ≤
r2 < pλ1 (L) and ξ (L, r2 ) ≤ p/(20 log p), we have
Pr[λ1 (L′ ) ≤ r1 and λ2 (L′ ) > r2 ] ≥

ξ (L, r1 ) 
ξ (L, r2 ) 
.
· 1−
p
p

Proof. The algorithm takes as input a basis B for a lattice L ⊂ R n . It then samples z ∈ Z np uniformly
at random and outputs
L′ := {y ∈ L : hz, B−1 yi ≡ 0 mod p} .

Let N := ξ (L, r2 ) ≤ p/(20 log p), and let y1 , . . . , y N ∈ L be the N unique primitive vectors in L
satisfying ky1 k ≤ · · · ≤ ky N k ≤ r2 (taking only one vector from each pair ±y). Note that we have
λ1 (L′ ) ≤ r1 and λ2 (L′ ) > r2 if and only if yi ∈ L′ for some i ≤ ξ (L, r1 ) and y j ∈
/ L′ for all j 6= i.
(Here, we have used the fact that r2 < pλ1 (L) to guarantee that vectors of the form pyi ∈ L′ do not
cause λ2 (L′ ) to be less than r2 .)
Applying Theorem 3.1, we see that this happens with probability at least 1/p − ( N − 1)/p2 >
1/p − N/p2 for any fixed i. The result follows by noting that these are disjoint events, so that the
probability that at least one of these events occurs is the sum of their individual probabilities, which
is at least
1
N
ξ (L, r2 ) 
ξ (L, r1 ) 
,
− 2 =
· 1−
ξ (L, r1 ) ·
p
p
p
p
as needed.

10

3.2

The reduction

We now present the main step in our search-to-decision reduction for SVP.
Theorem 3.3. For any γ = γ(n) ≥ 1 and a = a(n) ≥ log(n + 1), there is a dimension-preserving
(randomized) reduction from γn/a -SVP to γ-uSVP that runs in time 2O( a) · γO(n) .
Proof. We may assume without loss of generality that a ≤ n/2, since the result is trivial for larger
a. (There are known 2O(n) -time algorithms for SVP [AKS01, ADRS15].) We may also assume that
2a > γn , since this does not affect the asymptotic running time. Let k := ⌈4an/(n− a) ⌉ = 2O( a) .
On input a lattice L ⊂ R n , the reduction does the following k times. For i = 0, . . . , ℓ := ⌊ n/a⌋, let
pi be a prime with 2ki+1 < pi < 4ki+1 . The reduction calls the procedure from Proposition 3.2 with
input L and pi , receiving as output Li . It then calls its uSVP oracle on each Li , receiving as output xi .
Finally, it simply outputs a shortest non-zero xi .
It is clear that the reduction runs in time poly(n) · k = 2O( a) , as needed.5 For each i, let ri be
minimal such that ξ (L, ri ) ≥ ki . In particular, r0 = λ1 (L). And, recalling the definition of ξ, we have

|L ∩ rℓ B2n | > 2ξ (L, rℓ ) ≥ 2kℓ > 2 · (4an/(n− a) )n/a−1 = 2 · 4n .
So, applying Theorem 2.1, we have that rℓ /r0 = rℓ /λ1 (L) > 2.
Therefore, there exists an i such that ri+1 /ri > 21/ℓ ≥ 2a/n > γ. Let j be minimal such that
r j+1 /r j > γ. In particular, this means that ξ (L, γr j ) < k j+1 and γr j ≤ 2γλ1 (L) < p j λ1 (L). So, we
may apply Proposition 3.2 to obtain
ξ (L, r j ) ξ (L, r j )ξ (L, γr j )
−
pj
p2j
kj 
k j+1 
>
· 1−
pj
pj
1
>
.
2k

Pr[λ1 (L j ) ≤ r j and λ2 (L j ) > γr j ] ≥

Therefore, after running the above procedure k times, the algorithm will output a non-zero vector of
length at most ri with at least some positive constant probability.
Finally, by the definition of r j , we have r j /λ1 (L) = r j /r0 ≤ γ j ≤ γℓ ≤ γn/a . Therefore, the
algorithm outputs a γn/a -approximate shortest vector with at least constant probability, as needed.

3.3

Corollaries

From this, we derive some immediate corollaries. The first is our main SVP result.
Proof of Theorem 1.1. We may assume without loss of generality that γ ≤ 2, since otherwise the result
is trivial as there are known 2O(n) -time algorithms for SVP. Therefore, by Theorem 2.15, there is an
efficient dimension-preserving reduction from γ-uSVP to γ-GapSVP. The result then follows from
Theorem 3.3.
√
By combining Theorem 3.3 with Corollary 2.17, we obtain the following reduction from n-CVP
to γ-uSVP (and therefore γ-GapSVP).
5 The reader might notice that the theorem quotes a running time of 2O ( a ) · γO ( n) instead of just 2O ( a ) . Note that this
looser bound on the running time is exactly what allowed us to assume 2a > γ n above. Equivalently, we could simply
require a > n log γ in the theorem statement and achieve a running time of 2O( a) . But, we wish to avoid misunderstanding
by explicitly stating that the running time is at least γO( n) in the theorem statement.

11

√
Corollary 3.4. For any γ = γ(n) ≥ 1, there is a dimension-preserving (randomized) reduction from nCVP to γ-uSVP that runs in time poly(n) · γO(n) .
√
Similarly, there is a dimension-preserving (randomized) reduction from n-CVP to γ-GapSVP with the
same running time.
√
Proof. Setting a := 2n log(γ) + log(n + 1) in Theorem 3.3 gives a reduction from 2-SVP to γ-uSVP
with the claimed running time. The first result then follows from Corollary 2.17. The second result
follows from Theorem 2.15.
We also obtain an alternative proof of the hardness of (1 + 1/poly(n))-uSVP, as originally shown
by Aggarwal and Dubey [AD15].
Corollary 3.5. For any constant ε > 0, (1 + 1/nε )-uSVP is NP-hard (under randomized reductions).
Proof. For γ ≤ 1 + O(log n/n), taking a := n log(γ) + log(n + 1) in Theorem 3.3 gives a polynomialtime reduction from 2-SVP to γ-uSVP. It then follows from Theorem 2.13 that γ-uSVP is NP-hard
(under randomized reductions).
The full result then follows by noting that there is a simple reduction from (1 + 1/nε )-uSVP to (1 +
1/n)-uSVP for any constant ε ∈ (0, 1). In particular, given input L ⊂ R n with basis B := (b1 , . . . , bn ),
let N := ⌈n1/ε ⌉ = poly(n), and let r := 3kb1 k > 2λ1 (L). Let L′ := L(b1 , . . . , bn , ren+1 , . . . , re N ) ⊂
R N be the rank N lattice obtained by “adding N − n perpendicular vectors of length r to L.” The
result follows by noting that N ε ≥ n so that L′ is a valid instance of (1 + 1/N ε )-uSVP if L is a valid
instance of (1 + 1/n)-uSVP, and the two instances have the same solution.
Finally, we note that a reduction to GapSVP immediately implies a reduction to GapCVP, by
Theorem 2.14. We will need this in the next section.
Corollary 3.6. For any γ = γ(n) ≥ 1 and a = a(n) ≥ log(n + 1), there is a dimension-preserving
(randomized) reduction from γn/a -SVP to γ-GapCVP that runs in time 2O( a) · γO(n) .
Proof. Combine Theorem 1.1 with Theorem 2.14.

4

Reducing CVP to GapCVP

Theorem 4.1. For any γ = γ(n) ≥ 1, h = h(n) ≥ 1, and integer ℓ = ℓ(n) ≥ 1, there is a (deterministic)
algorithm with access to a γ-GapCVP oracle and a h-SVP oracle that solves γn/ℓ -CVP in time (poly(n) · h)ℓ .
Furthermore, the dimension of the algorithm’s oracle calls never exceeds the dimension of the input lattice.
Proof. We show how to handle the case ℓ = 1 and then describe how to extend the result to arbitrary
ℓ. On input a lattice L ⊂ R n and t ∈ R n , the algorithm behaves as follows. If n = 1, then it solves
the CVP instance directly. Otherwise, it first uses its SVP oracle to find a dual vector b1∗ ∈ L∗ with
kb1∗ k ≤ h · λ1 (L∗ ). Let b2∗ , . . . , b∗n ∈ L∗ such that (b1∗ , . . . , b∗n ) is a basis of L∗ , and let (b1 , . . . , bn ) ∈ L
be the associated basis of the primal. (This is always possible if b1∗ is primitive in L∗ . If b1∗ is not
primitive, then we can simply replace it with a primitive vector that is a scalar multiple of b1∗ .)
Next, let a := hb1∗ , ti and L′ := L(b2 , . . . , bn ). Then, for i = ⌊ a − h · n⌋, . . . , ⌈ a + h · n⌉, the
algorithm uses its GapCVP oracle to compute di such that dist(t − i · b1 , L′ ) ≤ di ≤ γ · dist(t − i ·
b1 , L′ ). The algorithm then picks an index i such that di is minimal and calls itself recursively on
input L′ and t − i · b1 , receiving as output y ∈ L′ . Finally, it outputs y + ib1 ∈ L.
It is clear that the running time is as claimed. By Corollary 2.3, there must exist some j such
that dist(t − j · b1 , L′ ) = dist(t, L), so that d j ≤ γ dist(t, L). Therefore, di ≤ γ · dist(t, L), and
dist(t − i · b1 , L′ ) ≤ γ · dist(t, L). The result then follows from induction on the dimension n.
To handle arbitrary ℓ ≥ 1, the algorithm simply tries all recursive paths up to depth ℓ and chooses
the path that yields the lowest approximate distance according to its γ-GapCVP oracle. Note that
there are at most (2hn + 2)ℓ = (poly(n) · h)ℓ such paths, so the running time is as claimed.
12

We obtain our main CVP reduction by combining the above result with our SVP reduction.
Proof of Theorem 1.2. We may assume without loss of generality that ℓ is an integer.
We can instantiate the SVP oracle required in Theorem 4.1 above by using Corollary 3.6. In particular, taking a := n log γ + log(n + 1) in Corollary 3.4 gives a reduction from 2-SVP to γ-GapCVP that
runs in time poly(n) · γO(n) . By using this reduction to instantiate the h-SVP oracle in Theorem 4.1
with h = 2, we get a dimension-preserving reduction from γn/ℓ -CVP to γ-CVP that runs in time
nO(ℓ) · γO(n) , as needed.

5

Deterministic reductions

We now show deterministic search-to-decision reductions for SVP and CVP that achieve significantly
worse parameters. Both reductions use the same basic idea, which is essentially to “find the coordinates of a short (or close) lattice point bit-by-bit.”

5.1

The deterministic CVP reduction

We present the CVP reduction first because it is simpler.
Proof of Theorem 1.4. We may assume without loss of generality that p is an integer and γ2 < p, since
the result is trivial for larger γ.
On input a lattice L ⊂ R n and t ∈ R n , the reduction behaves as follows. If n = 1, then it solves
the CVP instance directly. Otherwise, it first uses the procedure from Theorem 2.5, to compute an
LLL-reduced basis B = (b1 , . . . , bn ) for L. It then finds the nth coordinate of a close lattice vector to
t “in base p,” as follows. Let t0 = t, and let Li := L(b1 , . . . , bn−1 , pi · bn ) for all i. For i = 0, . . . , ℓ − 1,
with ℓ ≥ 1 to be set in the analysis, the reduction uses its γ-GapCVP oracle to compute di,0 , . . . , di,p−1
such that dist(ti − jpi · bn , Li+1 ) ≤ di,j ≤ γ dist(ti − jpi · bn , Li+1 ). It then sets ti+1 = ti − j · pi · bn ,
where j is chosen such that di,j is minimal.
Let
'
$
eni
h tℓ , b
′
ℓ
· bn .
t : = tℓ − p ·
e n k2
pℓ · kb

The reduction then calls itself recursively on input L′ := L(b1 , . . . , bn−1 ) and t′ , receiving as output
y′ ∈ L′ . Finally, the reduction outputs y′ + t − t′ ∈ L.
Take


n + log n + 2
ℓ :=
= O(n/ log p) .
2 log( p/γ)

It is clear that the running time is as claimed. We first show by induction that dist(ti , Li ) ≤ γi ·
dist(t, L). For i = 0, this is trivial. For any i > 0, let x be a closest vector in Li−1 to ti−1 , and assume
for induction that kx − ti−1 k ≤ γi−1 dist(t, L). Note that we can write x = x′ + cpi−1 · bn , where
x′ ∈ Li and c ∈ {0, . . . , p − 1}. In particular,
di,c ≤ γ dist(ti−1 − cpi−1 · bn , Li ) = γkx − ti−1 k ≤ γi dist(t, L) .
It follows from the definition of ti that dist(ti , Li ) ≤ di,c ≤ γi dist(t, L), as needed.
We now wish to show that dist(t′ , L′ ) = dist(tℓ , Lℓ ). Suppose not. Then, clearly we have that
e n k/2. (To see this, consider the “distance in the direction of b
e n .”) Combining this
dist(tℓ , Lℓ ) ≥ pℓ kb
√ n/2 e
ℓ
e
with the above, we have dist(t, L) ≥ ( p/γ) · kbn k/2 ≥ n2
· kbn k, contradicting Lemma 2.7.
Combining everything together, we see that dist(t′ , L′ ) ≤ γℓ · dist(t, L). Finally, we assume for
induction that ky′ − t′ k ≤ γℓ·(n−1) dist(t′ , L′ ) ≤ γℓ·n dist(t, L). It follows that k(y′ − t′ + t) − tk =
2
ky′ − t′ k ≤ γℓn dist(t, L) = γO(n / log p) dist(t, L), as needed.

13

5.2

The deterministic SVP reduction

The SVP reduction uses essentially the same idea, but it is a bit more technical because the GapSVP
oracle is so much weaker. The reduction is very similar to the reduction from unique SVP to GapSVP
in [LM09].
Proof of Theorem 1.3. We may assume without loss of generality that p is a prime and γ3 < p, since
the result is trivial for larger γ. On input a lattice L ⊂ R n , the reduction behaves as follows. If n = 1,
it solves the SVP instance directly. Otherwise, let (b1 , . . . , bn ) be an LLL-reduced basis for L (which
we can compute efficiently by Theorem 2.5).
Our goal is to compute a sequence of sublattices L = L(0) ⊂ L(1) ⊂ · · · ⊂ L(ℓ) , with ℓ ≥ 1 to
be set in the analysis, such that the index of L(i+1) over L(i) is p, and λ1 (L(i+1) ) ≤ γ · λ1 (L(i) ). In
( i) ( i) ( i)
( i)
( i)
( i)
particular, we will take L(i) := L(b1 , . . . , bn−2 , a1 bn−1 + a2 bn , a3 bn ) for some a1 , a2 , a3 , starting
( 0)

( 0)

( 0)

with a1 := 1, a2 := 0, and a3 := 1. To compute the remaining coefficients, the reduction behaves
( i)

( i)

as follows for i = 0, . . . , ℓ − 1. For j = 0, . . . , p − 1, let Li,j := L(b1 , . . . , bn−2 , a1 bn−1 + a2 bn +
( i)

( i)

( i)

( i)

( i)

ja3 bn , pa3 bn ) and let Li,p := L(b1 , . . . , bn−2 , p · ( a1 bn−1 + a2 bn ), a3 bn ). For each j, the reduction
uses its GapSVP oracle to compute di,j such that λ1 (Li,j ) ≤ di,j ≤ γλ1 (Li,j ). Let j such that di,j is
minimal. The reduction then sets the coefficients so that L(i+1) := Li,j .6
(ℓ)

(ℓ)

Let k1 be the largest power of p that divides a1 , and let k2 be the largest power of p that divides

a3 . If k1 ≥ k2 , the reduction sets L′ := L(b1 , . . . , bn−2 , bn ) to be “L without bn−1 .” Otherwise, it sets
(ℓ)

(ℓ)

L′ := L(b1 , . . . , bn−2, a1 bn−1 + a2 bn ) to be “L(ℓ) without bn .” It then calls itself recursively on L′
and returns the result.
Take


n+3
ℓ :=
= O(n/ log p) .
log( p/γ2 )

The running time is clear. We first show that λ1 (L(i+1) ) ≤ γ · λ1 (L(i) ) for all i. Indeed, let v ∈ L(i)
such that kvk = λ1 (L(i) ). As in the previous proof, it suffices to observe that v ∈ Li,c for some c, as
this will imply that
λ1 (L(i+1) ) ≤ min di,j ≤ di,c ≤ γλ1 (Li,c ) = γkvk = γλ1 (L(i) ) ,
i

( i)

( i)

( i)

as needed. To see this, note that we can write v = ∑in=−12 ri bi + rn−1 · ( a1 bn−1 + a2 bn ) + rn · a3 bn
where ri ∈ Z. If rn−1 ≡ 0 mod p, then clearly v ∈ Li,p . Otherwise, there is a c ∈ {0, . . . , p − 1} such
that crn−1 ≡ rn mod p. Then,
v=

=

n −2

( i)

i=1
n −2

b n − 1 + a2 b n ) + r n a3 b n

( i)

bn−1 + a2 bn + ca3 bn ) + (rn − crn−1 ) a3 bn .

∑ r i b i + r n − 1 · ( a1

∑ r i b i + r n − 1 · ( a1

i=1

( i)

( i)

( i)

( i)

( i)

Note that by definition rn − crn−1 ≡ 0 mod p, so it follows that v ∈ Li,c , as needed.
In particular, λ1 (L(ℓ) ) ≤ γℓ λ1 (L). Now, we claim that λ1 (L′ ) ≤ λ1 (L(ℓ) ). Note that any point
y = ∑ ai bi ∈ L(ℓ) \ L′ has either | an | ≥ pmax(k1 ,k2 ) ≥ pℓ/2 or | an−1 | ≥ pℓ/2 (depending on whether or
not k1 ≥ k2 ). But, by Lemma 2.6, this implies that kyk ≥ 2−n/2−1 · pℓ/2 · λ1 (L) > γℓ λ1 (L). Therefore,
any vector in L(ℓ) of length at most λ1 (L(ℓ) ) ≤ γℓ · λ1 (L) must be in L′ , as needed.
Finally, as in the previous proof, we can show by a simple induction argument that the output
2
vector has length at most γℓ(n−1) λ1 (L′ ) ≤ γℓn λ1 (L) = γO(n / log p) · λ1 (L), as needed.
6 I.e.,

( i +1)

a2

( i +1)

if j < p, the reduction sets a1
( i)

( i +1)

: = a2 , and a3

( i)

( i)

( i +1)

: = a1 , a2

( i)

( i)

( i +1)

: = a2 + ja3 , and a3

: = a3 .

14

( i)

( i +1)

: = pa3 . Otherwise, it sets a1

( i)

: = pa1 ,

References
[AD15]

Divesh Aggarwal and Chandan Dubey. Improved hardness results for unique Shortest
Vector Problem, 2015. http://eccc.hpi-web.de/report/2013/076/.

[ADRS15] Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. Solving
the Shortest Vector Problem in 2n time via discrete Gaussian sampling. In STOC, 2015.
[Ajt96]

Miklós Ajtai. Generating hard instances of lattice problems. In STOC, 1996.

[Ajt98]

Miklós Ajtai. The Shortest Vector Problem in L2 is NP-hard for randomized reductions.
In STOC, 1998.

[AKS01]

Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice
vector problem. In STOC, 2001.

[AR05]

Dorit Aharonov and Oded Regev. Lattice problems in NP intersect coNP. Journal of the
ACM, 52(5):749–765, 2005. Preliminary version in FOCS’04.

[Bab86]

L. Babai. On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica,
6(1):1–13, 1986.

[Ban93]

W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers.
Mathematische Annalen, 296(4):625–635, 1993.

[BHW93] U. Betke, M. Henk, and J.M. Wills. Successive-minima-type inequalities. Discrete & Computational Geometry, 9(1):165–175, 1993.
[BV11]

Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from
(standard) LWE. In FOCS. 2011.

[BV14]

Zvika Brakerski and Vinod Vaikuntanathan. Lattice-based FHE as secure as PKE. In ITCS,
2014.

[BWS16]

Shi Bai, Weiqiang Wen, and Damien Stehlé. Improved reduction from the Bounded Distance Decoding problem to the unique Shortest Vector Problem in lattices. In ICALP, 2016.

[Che13]

Kuan Cheng.
Some complexity results and bit unpredictable for Short
Vector Problem.
Cryptology ePrint Archive, Report 2013/052,
2013.
http://eprint.iacr.org/2013/052.

[CN99]

Jin-Yi Cai and Ajay Nerurkar. Approximating the SVP to within a factor (1+1/dimε ) is
NP-hard under randomized reductions. Journal of Computer and System Sciences, 59(2):221
– 239, 1999.

[DK13]

Daniel Dadush and Gabor Kun. Lattice sparsification and the approximate Closest Vector
Problem. In SODA, 2013.

[DPV11]

Daniel Dadush, Chris Peikert, and Santosh Vempala. Enumerative lattice algorithms in
any norm via M-ellipsoid coverings. In FOCS, 2011.

[DRS14]

Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. On the Closest Vector
Problem with a distance guarantee. In CCC, 2014.

[Gen09]

Craig Gentry. Fully homomorphic encryption using ideal lattices. In STOC, 2009.

[GMSS99] Oded Goldreich, Daniele Micciancio, Shmuel Safra, and Jean-Paul Seifert. Approximating
shortest lattice vectors is not harder than approximating closest lattice vectors. Information
Processing Letters, 71(2):55 – 61, 1999.
15

[GPV08]

Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and
new cryptographic constructions. In STOC, 2008.

[HP14]

Gengran Hu and Yanbin Pan. Improvements on reductions among different variants of
SVP and CVP. In Information Security Applications: 14th International Workshop, WISA, 2014.

[HR12]

Ishay Haviv and Oded Regev. Tensor-based hardness of the Shortest Vector Problem to
within almost polynomial factors. Theory of Computing, 8(23):513–531, 2012. Preliminary
version in STOC’07.

[JS98]

Antoine Joux and Jacques Stern. Lattice reduction: A toolbox for the cryptanalyst. Journal
of Cryptology, 11(3):161–185, 1998.

[Kan87]

Ravi Kannan. Minkowski’s convex body theorem and integer programming. Mathematics
of Operations Research, 12(3):pp. 415–440, 1987.

[Kho05]

Subhash Khot. Hardness of approximating the Shortest Vector Problem in lattices. Journal
of the ACM, 52(5):789–808, September 2005. Preliminary version in FOCS’04.

[KL78]

G. A. Kabatjanskiı̆ and V. I. Levenšteı̆n. Bounds for packings on the sphere and in space.
Problemy Peredači Informacii, 14(1):3–25, 1978.

[KS01]

S. Ravi Kumar and D. Sivakumar. On the unique shortest lattice vector problem. Theoretical Computer Science, 255(12):641 – 648, 2001.

[Len83]

Hendrik W Lenstra Jr. Integer programming with a fixed number of variables. Mathematics of operations research, 8(4):538–548, 1983.

[LLL82]

A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász. Factoring polynomials with rational
coefficients. Math. Ann., 261(4):515–534, 1982.

[LLM06]

Yi-Kai Liu, Vadim Lyubashevsky, and Daniele Micciancio. On Bounded Distance Decoding for general lattices. In RANDOM, 2006.

[LM09]

Vadim Lyubashevsky and Daniele Micciancio. On Bounded Distance Decoding, unique
shortest vectors, and the minimum distance problem. In CRYPTO, 2009.

[LPR10]

Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and Learning with
Errors over rings. In EUROCRYPT, 2010.

[MG02]

Daniele Micciancio and Shafi Goldwasser. Complexity of Lattice Problems: a cryptographic
perspective, volume 671 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, Boston, Massachusetts, March 2002.

[Mic01]

Daniele Micciancio. The Shortest Vector Problem is NP-hard to approximate to within
some constant. SIAM Journal on Computing, 30(6):2008–2035, March 2001. Preliminary
version in FOCS 1998.

[Mic08]

Daniele Micciancio. Efficient reductions among lattice problems. In SODA, 2008.

[MR07]

Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on
Gaussian measures. SIAM Journal on Computing, 37(1):267–302, 2007.

[NS01]

Phong Q Nguyen and Jacques Stern. The two faces of lattices in cryptology. In Cryptography and lattices, pages 146–180. Springer, 2001.

[Odl90]

Andrew M Odlyzko. The rise and fall of knapsack cryptosystems. Cryptology and computational number theory, 42:75–88, 1990.
16

[Pei09]

Chris Peikert. Public-key cryptosystems from the worst-case Shortest Vector Problem. In
STOC, 2009.

[PR07]

Chris Peikert and Alon Rosen. Lattices that admit logarithmic worst-case to average-case
connection factors. In STOC, 2007.

[PS09]

Xavier Pujol and Damien Stehlé. Solving the shortest lattice vector problem in time 22.465n .
IACR Cryptology ePrint Archive, 2009:605, 2009.

[Reg09]

Oded Regev. On lattices, Learning with Errors, random linear codes, and cryptography.
Journal of the ACM, 56(6):Art. 34, 40, 2009.

[Ste15]

Noah Stephens-Davidowitz. Dimension-preserving reductions between lattice problems.
http://noahsd.com/latticeproblems.pdf, 2015.

[Ste16]

Noah Stephens-Davidowitz. Discrete Gaussian sampling reduces to CVP and SVP. In
SODA, 2016.

17

