arXiv:1709.01535v1 [] 5 Sep 2017

Just Take the Average!
An Embarrassingly Simple 2n-Time Algorithm for SVP (and CVP)
Divesh Aggarwal
Centre for Quantum Technologies
dcsdiva@nus.edu.sg

Noah Stephens-Davidowitz∗
New York University
noahsd@gmail.com

Abstract
n+o(n)

We show a 2
-time (and space) algorithm for the Shortest Vector Problem on lattices
(SVP) that works by repeatedly running an embarrassingly simple “pair and average” sievinglike procedure on a list of lattice vectors. This matches the running time (and space) of the
current fastest known algorithm, due to Aggarwal, Dadush, Regev, and Stephens-Davidowitz
(ADRS, in STOC, 2015), with a far simpler algorithm. Our algorithm is in fact a modification
of the ADRS algorithm, with a certain careful rejection sampling step removed.
The correctness of our algorithm follows from a more general “meta-theorem,” showing that
such rejection sampling steps are unnecessary for a certain class of algorithms and use cases. In
particular, this also applies to the related 2n+o(n) -time algorithm for the Closest Vector Problem
(CVP), due to Aggarwal, Dadush, and Stephens-Davidowitz (ADS, in FOCS, 2015), yielding a
similar embarrassingly simple algorithm for γ-approximate CVP for any γ = 1 + 2−o(n/ log n) .
(We can also remove the rejection sampling procedure from the 2n+o(n) -time ADS algorithm for
exact CVP, but the resulting algorithm is still quite complicated.)

1

Introduction

A lattice L ⊂ Rn is the set of all integer linear combinations of some linearly independent basis
vectors b1 , . . . , bn ∈ Rn ,
L :=

n
nX
i=1

o

zi bi : zi ∈ Z .

The two most important computational problems on lattices are the Shortest Vector Problem
(SVP) and the Closest Vector Problem (CVP). Given a basis b1 , . . . , bn for a lattice L ⊂ Rn , SVP
asks us to find a shortest non-zero vector in L, and CVP asks us to find a closest lattice vector to
some target vector t ∈ Rn . (Throughout this paper, we define distance in terms of the Euclidean, or
ℓ2 , norm.) CVP seems to be the harder of the two problems, as there is an efficient reduction from
CVP to SVP that preserves the dimension n [GMSS99], but both problems are known to be NPhard [vEB81, Ajt98]. They are even known to be hard to approximate for certain approximation
factors [Mic01, DKRS03, Kho05, HR12].
∗

Supported by the National Science Foundation (NSF) under Grant No. CCF-1320188, and the Defense Advanced
Research Projects Agency (DARPA) and Army Research Office (ARO) under Contract No. W911NF-15-C-0236.

1

Algorithms for solving these problems, both exactly and over a wide range of approximation
factors, have found innumerable applications since the founding work by Lenstra, Lenstra, and
Lovász in 1982 [LLL82]. (E.g., [LLL82, Len83, Sha84, Kan87, dB89].) More recently, following
the celebrated work of Ajtai [Ajt04] and Regev [Reg09], a long series of works has resulted in
many cryptographic constructions whose security is based on the assumed worst-case hardness of
approximating these (or closely related) problems. (See [Pei16] for a survey of such constructions.)
And, some of these constructions are now nearing widespread deployment. (See, e.g., [NIS16,
ADPS16, BCD+ 16].)
Nearly all of the fastest known algorithms for lattice problems—either approximate or exact—
work via a reduction to either exact SVP or exact CVP (typically in a lower dimension). Even the
fastest known polynomial-time algorithms (which solve lattice problems only up to large approximation factors) work by solving exact SVP on low-dimensional sublattices [Sch87, GN08, MW16].
Therefore, algorithms for exact lattice problems are of particular importance, both theoretically
and practically (and both for direct applications and to aid in the selection of parameters for
cryptography). Indeed, much work has gone into improving the running time of these algorithms
(e.g., [Kan87, AKS01, AKS02, PS09, MV10, MV13]), culminating in 2n+o(n) -time algorithms for
both problems based on the technique of discrete Gaussian sampling, from joint work with Dadush
and Regev [ADRS15] and follow-up work with Dadush [ADS15].
In order to explain our contribution, we first give a high-level description of the SVP algorithm from [ADRS15]. (The presentation below does not represent the way that we typically view
the [ADRS15] algorithm.)

1.1

Sieving by averages

One can think of the SVP algorithm from [ADRS15] as a rather strange variant of randomized
sieving. Recall that the celebrated randomized sieving technique due to Ajtai, Kumar, and Sivakumar [AKS01] starts out with a list of 2O(n) not-too-long random vectors X 1 , . . . , X M sampled from
some efficiently samplable distribution. The sieving algorithm then repeatedly (1) searches for pairs
of vectors (X i , X j ) that happen to be remarkably close together; and then (2) replaces the old list
of vectors with the differences of these pairs X i − X j .
The [ADRS15] algorithm similarly starts with a randomly chosen collection of 2n+o(n) nottoo-long vectors X 1 , . . . , X M and repeatedly (1) selects pairs of vectors according to some rule;
and (2) replaces the old list of vectors with some new vectors generated from these pairs. However,
instead of taking the differences X i −X j of pairs (X i , X j ), the [ADRS15] algorithm takes averages,
(X i + X j )/2.
Notice that the average (X i + X j )/2 of two lattice vectors X i , X j ∈ L will not generally be in
the lattice. In fact, this average will be in the lattice if and only if the two vectors are equivalent
mod 2L, i.e., X i ≡ X j mod 2L. Therefore, at a minimum, the [ADRS15] algorithm should select
pairs that lie in the same coset mod 2L. (Notice that there are 2n possible cosets.) I.e., the simplest
possible version of “sieving by averages” just repeats Procedure 1 many times (starting with a list
of 2n+o(n) vectors, which is sufficient to guarantee that we can pair nearly every vector with a
different unique vector in the same coset). The [ADRS15] algorithm is more complicated than this,
but it still only uses the cosets of the vectors mod 2L when it decides which vectors to pair.
It might seem like a rather big sacrifice to only look at a vector’s coset, essentially ignoring
all geometric information. For example, the [ADRS15] algorithm (and our variant) is likely to
miss many opportunities to pair two vectors whose average is very short. But, in exchange for
2

Pair and Average (X 1 , . . . , X M )
Input : List of vectors X i ∈ L − t
Output : List of vectors Y i ∈ L − t
for each unpaired vector X i do
if there exists an unpaired vector X j with X j ≡ X i mod 2L then
add (X i + X j )/2 to the output
end
end
Procedure 1: The basic “pair and average” procedure, which computes the averages (X i +
X j )/2 of disjoint pairs (X i , X j ) satisfying X i ≡ X j mod 2L.
this sacrifice, we get very strong control over the distribution of the vectors at each step. In
particular, before applying Procedure 1, the [ADRS15] algorithm uses a careful rejection sampling
procedure over the cosets to guarantee that at each step of the algorithm, the vectors are distributed
as independent samples from a distribution that we understand very well (the discrete Gaussian,
which we describe in Section 1.3). I.e., at each step, the algorithm randomly throws away many
of the vectors in each coset according to some rule that depends only on the list of cosets, and it
only runs Procedure 1 on the remaining vectors, as shown in Procedure 2. This rejection sampling
procedure is so selective that, though the algorithm starts out with 2n+o(n) vectors, it typically
finishes with only about 2n/2 vectors.
Reject-and-Average Sieve (ℓ; X 1 , . . . , X M )
Input : Number of steps ℓ, list of vectors X i ∈ L − t
Output : List of vectors Y i ∈ L − t
for i = 1, . . . , ℓ do
for j = 1, . . . , M do
set cj to be the coset of X j mod 2L
end
{j1 , . . . , jm } ← f (c1 , . . . , cM )
(X 1 , . . . , X M ′ ) ← Pair and Average(X j1 , . . . , X jm )
M ← M′
end
output (X 1 , . . . , X M ).
Procedure 2: The “reject and average” sieving procedure, which repeatedly applies some
rejection sampling procedure f according to the cosets of the X i mod 2L and then applies
Procedure 1 (Pair and Average) to the “accepted” vectors. Here, f is some (possibly randomized) function that maps a list of cosets (c1 , . . . , cM ) mod 2L to a set of “accepted” indices
{j1 , . . . , jm } ⊆ {1, . . . , M }.
This does seem quite wasteful (since the algorithm typically throws away the vast majority of
its input vectors) and a bit naive (since the algorithm ignores, e.g., the lengths of the vectors). But,
because we get such good control over the output distribution, the result is still the fastest known

3

algorithm for SVP.1 (The [ADS15] algorithm for CVP relies on the same core idea, plus a rather
complicated recursive procedure that converts an approximate CVP algorithm with certain special
properties into an exact CVP algorithm.)

1.2

Our contribution

Our main contribution is to show that the rejection sampling procedure used in the [ADRS15]
algorithm is unnecessary! Indeed, informally, we show that “any collection of vectors that can be
found via such a procedure (when the input vectors are sampled independently from an appropriate
distribution) can also be found without it.” (We make this precise in Theorem 3.4.) In particular,
the SVP algorithm in [ADRS15] can be replaced by an extremely simple algorithm, which starts
with a list of 2n+o(n) vectors sampled from the right distribution and then just runs Procedure 1
repeatedly. (Equivalently, it runs Procedure 2 with f taken to be the trivial function that always
outputs all indices, {1, . . . , M }.)
Theorem 1.1 (SVP, informal). There is a 2n+o(n) -time (and space) algorithm for SVP that starts
with 2n+o(n) vectors sampled from the same distribution as the [ADRS15] algorithm and then simply
applies Procedure 1 repeatedly, ℓ = O(log n) times.
The situation for CVP is, alas, more complicated because Procedure 2 is not the most difficult
part of the exact CVP algorithm from [ADS15]. Indeed, while this algorithm does run Procedure 2
and we do show that we can remove the rejection sampling procedure, the resulting algorithm
retains the complicated recursive structure of the original [ADS15] algorithm. However, [ADS15]
also shows a much simpler non-recursive version of their algorithm that solves CVP up to an
extremely good approximation factor. If we are willing to settle for such an algorithm, then we get
the same result for CVP.
Theorem 1.2 (CVP, informal). There is a 2n+o(n) -time (and space) algorithm that approximates
CVP up to an approximation factor γ for any γ = 1 + 2−o(n/ log n) that starts with 2n+o(n) vectors
from the same distribution as the [ADS15] algorithm and then simply applies Procedure 1 repeatedly,
ℓ = o(n/ log n) times.
In practice, such a tiny approximation factor is almost always good enough for applications.

1.3

Proof techniques

To describe the technical ideas behind our result, we now define the discrete Gaussian distribution,
which plays a fundamental role in the algorithms in [ADRS15, ADS15] and a big part in our analysis.
For any vector x ∈ Rn and parameter s > 0, we define its Gaussian mass as
ρs (x) := exp(−πkxk2 /s2 ) ,
and we extend this definition to a shift of a lattice L ⊂ Rn with shift vector t ∈ Rn in the natural
way,
X
ρs (L − t) :=
ρs (y − t) .
y∈L

1
There are various “heuristic” sieving algorithms for SVP that run significantly faster (e.g., in time
(3/2)n/2 [BDGL16]) but do not have formal proofs of correctness. One of the reasons that these algorithms lack
proofs is because we do not understand their output distributions.

4

The discrete Gaussian distribution DL−t,s is the probability distribution over L − t induced by this
measure, given by
ρs (y − t)
Pr [X = y − t] :=
X∼DL−t,s
ρs (L − t)

for any y ∈ L.
For very large parameters s > 0, we can sample from the discrete Gaussian DL−t,s efficiently [GPV08, BLP+ 13]. (Notice that DL−t,s tends to concentrate on shorter vectors as the
parameter s > 0 gets smaller. In particular, [ADRS15] showed that about 1.38n independent samples from the discrete Gaussian DL,s with an appropriately chosen parameter s will contain a shortest non-zero lattice vector with high probability. See Proposition A.7.) So, in [ADRS15, ADS15],
we use Procedure 2 with a carefully chosen rejection sampling procedure f in order to convert many
independent samples from DL−t,s with a relatively large parameter s to some smaller number of
independent samples from DL−t,s/2ℓ/2 .
This rejection sampling is certainly necessary if we wish to use Procedure 1 to sample from the
discrete Gaussian distribution. Our new observation is that, even when we do not do this rejection
sampling, the output of Procedure 1 still has a nice distribution. In particular, if we fix the coset
mod 2L of a pair of discrete Gaussian vectors (X i , X j ) with parameter √
s > 0, then their average
will be distributed as a mixture of discrete Gaussians with parameter s/ 2 over the cosets of 2L.
I.e., while the probability of their average landing in any particular coset will not in general be
proportional to the Gaussian mass of the coset, the distribution inside each coset will be exactly
Gaussian. (See Lemma 3.1.)
This observation is sufficient to prove that no matter what rejection sampling procedure f we
use in Procedure 2, if the input consists of independent samples from DL−t,s , the output will always
be distributed as some mixture of samples from D2L+c−t,s/2ℓ/2 over the cosets c ∈ L/(2L). I.e., while
the output distribution might distribute weight amongst the cosets differently, if we condition on a
fixed number of vectors landing in each coset, the output will always be distributed as independent
discrete Gaussian vectors with parameter s/2ℓ/2 . It follows immediately that “rejection sampling
cannot help us.” In particular, the probability that the output of Procedure 2 will contain a
particular vector (say a shortest non-zero vector) with any rejection sampling procedure f will
never be greater than the probability that we would see that vector without rejection sampling
(i.e., when f is the trivial function that outputs {1, . . . , M }).2 See Corollary 3.3 and Theorem 3.4
for more detail.

1.4

An open problem—towards a 2n/2 -time algorithm

Our result shows that all known applications of the 2n+o(n) -time discrete Gaussian sampling algorithms in [ADRS15, ADS15] work just as well if we remove the rejection sampling procedure from
these algorithms. This in particular includes the SVP application mentioned in Theorem 1.1 and
the approximate CVP application mentioned in Theorem 1.2. (More generally, we can remove the
rejection sampling procedure from any application that simply relies on finding a set of vectors
with a certain property in the output distribution, such as a shortest non-zero vector, all shortest
non-zero vectors, a vector that is close to a shortest lattice vector in L − t, etc.)
2

Notice that this property is far from obvious without the observation that the output distribution is always a
mixture of Gaussians over the cosets. For example, if we modified Procedure 2 so that f acted on the X i themselves,
rather than just their cosets mod 2L, then this property would no longer hold.

5

However, [ADRS15] also presents a 2n/2+o(n) -time algorithm that samples
from DL−t,s as long
√
as the parameter s > 0 is not too small. (In particular, we need s ≥ 2η1/2 (L), where η1/2 (L) is
the smoothing parameter of the lattice. See [ADRS15] or [Ste17] for the details.) This algorithm
is similar to the 2n+o(n) -time algorithms in that it starts with independent discrete Gaussian vectors with some high parameter, and it gradually lowers the parameter using a rejection sampling
procedure together with a procedure that takes the averages of pairs of vectors that lie in the same
coset modulo some sublattice. But, it fails for smaller parameters specifically because the rejection
sampling procedure that it uses must throw out too many vectors in this case. (In [Ste17], we use
a different rejection sampling procedure that never throws away too many
vectors, but we do not
√
n/2+o(n)
know how to implement it in 2
time for small parameters s < 2η1/2 (L).) If we could find
a suitable variant of this algorithm that works for small parameters, we would be able to solve SVP
in 2n/2+o(n) time.
So, we are naturally very interested in understanding what happens when we simply remove
the rejection sampling procedure from this algorithm. And, the fact that this works out so nicely
for the 2n+o(n) -time algorithm works seems quite auspicious! Unfortunately, we are unable to say
very much at all about the resulting distribution in the 2n/2+o(n) -time case.3 So, we leave the study
of this distribution as an open problem.

Organization
In Section 2, we review a few basic facts necessary to prove our main “meta-theorem,” Theorem 3.4,
which shows that “rejection sampling is unnecessary.” In Section 3, we finish this proof. In particular, this implies Theorem 1.1 and 1.2. For completeness, in the appendix, we prove these theorems
more directly and show the resulting algorithms in full detail.

Acknowledgments
We thank Oded Regev and Daniel Dadush for many helpful discussions.

2

Preliminaries

We write N := {0, 1, . . .} for the natural numbers (including zero). We make little to no distinction
between a random variable and its distribution. For x = (x1 , . . . , xn ) ∈ Rn , we write kxk :=
(x21 +· · ·+x2n )1/2 for the Euclidean norm of x. For any set S, we write S ∗ := {(x1 , . . . , xM ) : xi ∈ S}
for the set lists over S of finite length. (The order of elements in a list M ∈ S ∗ will never concern
us. We could therefore instead use multisets.)

2.1

Lattices

A lattice L ⊂ Rn is the set of integer linear combinations
L := {a1 b1 + · · · + an bn : ai ∈ Z}
3

After one step of “pairing and averaging,” we know exactly the distribution that we get, and it is a weighted
combination of Gaussians over the cosets of a certain sublattice! This seems quite auspicious. Unfortunately, the
particular sublattice is not the same sublattice that we use to pair the vectors in the next step, and we therefore are
unable to say much at all about what happens even after two steps.

6

of some linearly independent basis vectors B := (b1 , . . . , bn ). We sometimes write L(B) for the
lattice spanned by B.
We write L/(2L) for the set of cosets of L over 2L. E.g., if b1 , . . . , bn is a basis for L, then
each coset c ∈ L/(2L) corresponds to a unique vector a1 b1 + · · · + an bn with ai ∈ {0, 1}, and
this correspondence is a bijection. Notice that the cosets in L/(2L) have a group structure under
addition that is isomorphic to Zn2 .

2.2

The discrete Gaussian

For a parameter s > 0 and vector x ∈ Rn , we write
ρs (x) := exp(−πkxk2 /s2 )
for the Gaussian mass of x with parameter s > 0. Up to scaling, the Gaussian mass is the unique
function on Rn that is invariant under rotations and a product function. In particular, it satisfies
the following nice rotation identity,
ρs (x)ρs (y) = ρ√2s (x + y)ρ√2s (x − y)

(1)

for any parameter s > 0 and vectors x, y ∈ Rn . This identity is fundamental to the results
of [ADRS15, ADS15]. (See [RS17, Ste17] for a more detailed description of this connection and
some additional results.)
We extend the Gaussian mass to a shift t ∈ Rn of a lattice L ⊂ Rn in the natural way,
ρs (L − t) :=

X

y∈L

ρs (y − t) ,

and we call this the Gaussian mass of L − t with parameter s.
We will need the following identity from [ADS15]. (See [RS17, Ste17] for a much more general
identity.)
Lemma 2.1. For any lattice L ⊂ Rn , shift t, and parameter s > 0, we have
X

c∈L/(2L)

ρs (2L + c − t)2 = ρs/√2 (L)ρs/√2 (L − t) .

Proof. We have
X

c∈L/(2L)

ρs (2L + c − t)2 =
=

X

X

c∈L/(2L) y 1 ,y 2 ∈L

X

X

c∈L/(2L) y 1 ,y 2 ∈L

=

X

X

c∈L/(2L) w,y1 ∈L

= ρs/√2 (L − t)

ρs (2y 1 + c − t)ρs (2y 2 + c − t)
ρs/√2 (y 1 + y 2 + c − t)ρs/√2 (y 1 − y 2 )

ρs/√2 (2y 1 − w + c − t)ρs/√2 (w)

X

ρs/√2 (w)

w∈L

= ρs/√2 (L − t)ρs/√2 (L) ,
as needed.
7

2.3

Dominating distributions

Intuitively, we say that some random list M ∈ S ∗ dominates another random list M′ ∈ S ∗ if for
every fixed list S ∈ S ∗ , “M is at least as likely to contain S as a subsequence as M′ is.”
Definition 2.2 (Dominating distribution). For some finite set S (which we identify with {1, . . . , N }
′ )∈
without loss of generality) and two random lists M := (X1 , . . . , XM ) ∈ S ∗ and M′ := (X1′ , . . . , XM
′
∗
′
′
S (where M and M might themselves be random variables), we say that M dominates M if for
any (k1 , . . . , kN ) ∈ NN ,
Pr[|{j : Xj = i}| ≥ ki , ∀i] ≥ Pr[|{j : Xj′ = i}| ≥ ki , ∀i] .

We note the following basic facts about dominant distributions, which show that domination
yields a partial order over random variables on S ∗ , and that this partial order behaves nicely under
taking sublists.
Fact 2.3. For any finite set S and random variable M ∈ S ∗ that dominates some other random
variable M′ ∈ S ∗ ,
1. M dominates itself;
2. if M′ dominates some random variable M′′ ∈ S ∗ , then M also dominates M′′ ; and
3. for any function f : S ∗ → S ∗ that maps a list of elements to a sublist, M dominates f (M′ ).

3

No need for rejection!

We now show our main observation: if X 1 ∈ L − t and X 2 ∈ L − t are sampled from the discrete
Gaussian over a fixed coset 2L + c − t for some c ∈ L/(2L), then their average (X 1 + X 2 )/2 is
distributed as a mixture
√ of Gaussians over the cosets 2L + d − t for d ∈ L/(2L) with parameter
lowered by a factor of 2.
Lemma 3.1. For any lattice L ⊂ Rn , shift t ∈ Rn , parameter s > 0, coset c ∈ L/(2L), s > 0, and
y ∈ L, we have
Pr

X 1 ,X 2 ∼D2L+c−t,s

[(X 1 + X 2 )/2 = y − t] = ρs/√2 (y − t) ·

ρs/√2 (2L + c + y)
ρs (2L + c − t)2

In particular, for any d ∈ L/(2L) and y ∈ 2L + d,
Pr

X 1 ,X 2 ∼D2L+c−t,s

[(X 1 + X 2 )/2 = y − t | (X 1 + X 2 )/2 ∈ 2L + d − t] =

.

ρs/√2 (y − t)

ρs/√2 (2L + d − t)

Proof. We have
ρs (2L + c − t)2 ·
=

X

x∈2L+c

Pr

X 1 ,X 2 ∼D2L+c−t,s

[(X 1 + X 2 )/2 = y − t]

ρs (x − t)ρs (2y − x − t)

= ρs/√2 (y − t)

X

x∈2L+c

ρs/√2 (x − y)

= ρs/√2 (y − t)ρs/√2 (2L + c + y) ,
8

(Eq. (1))

.

as needed. The “in particular” then follows from the fact that ρs/√2 (2L + c + y) = ρs/√2 (2L + c + d)
is constant for y ∈ 2L + d for some fixed d ∈ L/(2L).
Lemma 3.1 motivates the following definition, which captures a key property of the distribution
described in Lemma 3.1.
Definition 3.2. For a lattice L ⊂ Rn , shift t ∈ Rn , and parameter s > 0 we say that the random
list (X 1 , . . . , X M ) ∈ (L − t)∗ is a mixture of independent Gaussians over L − t with parameter s
if the “distributions within the cosets of 2L” are independent Gaussians with parameter s. I.e., for
any list of cosets (c1 , . . . , cM ) ∈ ((L − t)/(2L))∗ mod 2L, if we condition on X i ∈ 2L + ci for all i,
then the X i are independent with X i ∼ D2L+ci ,s .
We call (2L + X 1 , . . . , 2L + X M ) the coset distribution of the X i . We say that a mixture of
independent Gaussians M over L − t with parameter s > 0 dominates another, M′ , if the coset
distribution of M dominates the coset distribution of M′ (as in Definition 2.2).
In other words, mixtures of independent Gaussians are exactly the distributions obtained by
first sampling (c1 , . . . , cM ) ∈ ((L − t)/(2L))∗ from some arbitrary coset distributions and then
sampling X i ∼ DL+ci ,s independently for each i. We now list some basic facts that follow from
what we have done so far.
Corollary 3.3 (Properties of mixtures of Gaussians and Procedure 1). For any lattice L ⊂ Rn ,
shift t ∈ Rn , and parameter s > 0,
1. a mixture of independent Gaussians over L − t with parameter s is uniquely characterized by
its coset distribution;
2. if we apply Procedure 1 to a mixture of independent Gaussians over L√− t with parameter s,
the result will be a mixture of Gaussians over L − t with parameter s/ 2;
3. Procedure 1 preserves domination—i.e., if we apply Procedure 1 to two mixtures M, M′ of
Gaussians over L − t with parameter s and M dominates M′ , then the output of Procedure 1
on input M will dominate that of M′ ; and
4. if X 1 , X 2 are a mixture of independent Gaussians over L − t with parameter s with coset
distribution given by X 1 ≡ X 2 mod 2L and
Pr[2L + X 1 + t = c] = P

ρs (2L + c − t)2
2
d∈L/(2L) ρs (2L + d − t)

for any c ∈ L/(2L), then their average (X 1 + X 2 )/2 is distributed exactly as DL−t,s/√2 .
Proof. Item 1 follows immediately from the definition of a mixture of Gaussians. Items 2 and 3 are
immediate consequences of Lemma 3.1.
For Item 4, we apply Lemma 3.1 to see that for any y ∈ L,
Pr[(X 1 + X 2 )/2 = y − t] = P
=P

ρs/√2 (y − t)

d∈L/(2L) ρs (2L

ρs/√2 (y

+ d − t)2

− t)

2
d∈L/(2L) ρs (2L + d − t)

9

X

ρs/√2 (2L + c + y)

c∈L/(2L)

· ρs/√2 (L) .

The result then follows from Lemma 2.1. (Indeed, summing the left-hand side and the right-hand
side over all y ∈ L gives a proof of Lemma 2.1.)
In [ADRS15, ADS15], we performed a careful rejection sampling procedure f in Procedure 2 so
that, at each step of the algorithm, the output was distributed exactly as DL−t,s/2i/2 (up to some
small statistical distance). In particular, we applied the rejection sampling procedure guaranteed
by Theorem A.3 to obtain independent vectors distributed as in Item 4, which yield independent
Gaussians with a lower parameter when combined as in Procedure 1. But, Corollary 3.3 makes this
unnecessary. Indeed, Corollary 3.3 shows that “any collection of vectors that can be found with
any rejection sampling procedure can be found without it.” The following meta-theorem makes this
formal.
Theorem 3.4. For any (possibly randomized) rejection function f mapping lists of cosets modulo
2L to a subset of indices (as in Procedure 2), let A be the algorithm defined in Procedure 2. Let A′
be the same algorithm with f replaced by the trivial function that just outputs all indices (i.e., A′
just repeatedly runs Procedure 1 with no rejection).
Then, for any lattice L ⊂ Rn , shift vector t ∈ Rn , parameter s > 0, if A and A′ are each called on
input ℓ ≥ 1 and a list of M ≥ 2 independent samples from DL−t,s , the resulting output distributions
will be mixtures of independent Gaussians over L − t with parameter s/2ℓ/2 . Furthermore, the
distribution corresponding to A′ will dominate the distribution corresponding to A. In particular,
for any finite set S ⊂ L − t,
Pr

X 1 ,...,X M ∼DL−t,s

[S ⊆ A(ℓ, X 1 , . . . , X M )] ≤

Pr

X 1 ,...,X M ∼DL−t,s

[S ⊆ A′ (ℓ, X 1 , . . . , X M )] .

Proof. Notice that, since f only acts on the cosets of the X i , f “preserves mixtures of independent
Gaussians.” I.e., if (X 1 , . . . , X M ′ ) is some mixture of independent Gaussians over L − t with
parameter s′ > 0 and (j1 , . . . , jm ) ← f (2L + X 1 , . . . , 2L + X M ′ ), then (X j1 , . . . , X jm ) is also a
mixture of independent Gaussians over L − t with parameter s′ . (Notice that this would not be
true if f acted on vectors, rather than cosets.) Similarly, by Item 2, Procedure 1 maps
√ mixtures of
′
′
independent Gaussians over L − t with parameter s to mixtures with parameter s / 2. It follows
that for both A and A′ , after the ith step of the algorithm, the list of vectors is a mixture of
Gaussians over L − t with parameter s/2i/2 . And, the same holds after the application of f in
algorithm A. Therefore, the only question is the coset distributions.
By Fact 2.3, we see that (X 1 , . . . , X M ) dominates (X j1 , . . . , X jm ). Therefore, by Item 3, the
distribution of vectors corresponding to A′ dominates the distribution of A after the first step. If
we assume for induction that, after the (i − 1)st step, the distribution of vectors corresponding to
A′ dominates the distribution corresponding to A, then the exact same argument together with
another application of Fact 2.3 shows that the same holds after step i. The result follows.
Theorem 3.4, together with the corresponding algorithms in [ADRS15, ADS15], immediately
implies Theorems 1.1 and 1.2. For completeness, we give more direct proofs of these theorems in
the appendix, more-or-less recreating the corresponding proofs in [ADRS15, ADS15].

References
[ADPS16] Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum key
exchange — A new hope. In USENIX Security Symposium, 2016.
10

[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.
[ADS15]

Divesh Aggarwal, Daniel Dadush, and Noah Stephens-Davidowitz. Solving the Closest
Vector Problem in 2n time— The discrete Gaussian strikes again! In FOCS, 2015.

[Ajt98]

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

[Ajt04]

Miklós Ajtai. Generating hard instances of lattice problems. In Complexity of computations and proofs, volume 13 of Quad. Mat., pages 1–32. Dept. Math., Seconda Univ.
Napoli, Caserta, 2004. Preliminary version in STOC’96.

[AKS01]

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

[AKS02]

Miklós Ajtai, Ravi Kumar, and D. Sivakumar. Sampling short lattice vectors and the
closest lattice vector problem. In CCC, pages 41–45, 2002.

[Bab86]

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

[Ban93]

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

[BCD+ 16] Joppe W. Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan, and Douglas Stebila. Frodo: Take off the ring! Practical,
quantum-secure key exchange from LWE. In CCS, 2016.
[BDGL16] Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest
neighbor searching with applications to lattice sieving. In SODA, 2016.
[BLP+ 13] Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. Classical hardness of learning with errors. In STOC, pages 575–584, 2013.
[dB89]

R. de Buda. Some optimal codes have structure. Selected Areas in Communications,
IEEE Journal on, 7(6):893–899, Aug 1989.

[DKRS03] Irit Dinur, Guy Kindler, Ran Raz, and Shmuel Safra. Approximating CVP to within
almost-polynomial factors is NP-hard. Combinatorica, 23(2):205–243, 2003.
[GMSS99] O. Goldreich, D. Micciancio, S. Safra, and J.-P. Seifert. Approximating shortest lattice
vectors is not harder than approximating closest lattice vectors. Information Processing
Letters, 71(2):55 – 61, 1999.
[GN08]

Nicolas Gama and Phong Q. Nguyen. Finding short lattice vectors within Mordell’s
inequality. In STOC, 2008.

[GPV08]

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

11

[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.

[Kan87]

Ravi Kannan. Minkowski’s convex body theorem and integer programming. Math. Oper.
Res., 12(3):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.

[Kle00]

Philip Klein. Finding the closest lattice vector when it’s unusually close. In SODA,
2000.

[Len83]

H. W. Lenstra, Jr. Integer programming with a fixed number of variables. Math. Oper.
Res., 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.

[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.

[MV10]

Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time algorithms for
the Shortest Vector Problem. In SODA, 2010.

[MV13]

Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time
algorithm for most lattice problems based on Voronoi cell computations. SIAM Journal
on Computing, 42(3):1364–1391, 2013.

[MW16]

Daniele Micciancio and Michael Walter. Practical, predictable lattice basis reduction.
In Eurocrypt, 2016.

[NIS16]

NIST
post-quantum
standardization
call
for
proposals.
http://csrc.nist.gov/groups/ST/post-quantum-crypto/cfp-announce-dec2016.html,
2016. Accessed: 2017-04-02.

[Pei16]

Chris Peikert. A decade of lattice cryptography. Foundations and Trends in Theoretical
Computer Science, 10(4):283–424, 2016.

[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.

[RS17]

Oded Regev and Noah Stephens-Davidowitz. An inequality for Gaussians on lattices.
SIDMA, 2017.

[Sch87]

C.P. Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science, 53(23):201 – 224, 1987.
12

[Sha84]

Adi Shamir. A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem. IEEE Trans. Inform. Theory, 30(5):699–704, 1984.

[Ste17]

Noah Stephens-Davidowitz. On the Gaussian Measure Over Lattices. PhD thesis, New
York University, 2017.

[vEB81]

Peter van Emde Boas. Another NP-complete problem and the complexity of computing
short vectors in a lattice. Technical report, University of Amsterdam, Department of
Mathematics, Netherlands, 1981. Technical Report 8104.

A

Additional preliminaries

We will need some additional preliminaries. We write
λ1 (L) :=

min kyk

y∈L\{0}

for the length of the shortest non-zero vector in the lattice. And, for a target vector t ∈ Rn , we
write
dist(t, L) := min ky − tk
y∈L

for the distance from t to the lattice. Notice that this is the same as the length of the shortest
vector in L − t.

A.1

Some known algorithms

We will need the famous result of Lenstra, Lenstra, and Lovász [LLL82].
Theorem A.1 ([LLL82]). There is an efficient algorithm that take as input a lattice L ⊂ Rn and
outputs λ̃ > 0 with
λ1 (L) ≤ d˜ ≤ 2n/2 λ1 (L) .
We will also need the following celebrated result due to Babai [Bab86].
Theorem A.2 ([Bab86]). There is an efficient algorithm that takes as input a lattice L ⊂ Rn and
a target t ∈ Rn and outputs d˜ > 0 with
dist(t, L) ≤ d˜ ≤ 2n/2 dist(t, L) .

A.2

The distribution of disjoint pairs

Recall that Procedure 1 takes the Ti elements from the ith coset and converts them into ⌊Ti /2⌋
disjoint pairs. Therefore, for a list M := (X1 , . . . , XM ) ∈ S ∗ over some finite set S, we write ⌊M/2⌋
for the random variable obtained as in Procedure 1. I.e., up to ordering (which does not concern
′ ) ∈ (S × S)∗ is defined by
us), ⌊M/2⌋ := (X1′ , . . . , XM
′
|{j : Xj′ = (s, s)}| = ⌊|{j : Xj = s}|/2⌋
for each s ∈ S.
13

P

Theorem A.3 ([ADRS15, Theorem 3.3]). For any probabilities, p1 , . . . , pN ∈ [0, 1] with
pi =
2
1, integer M , and κ ≥ Ω(log M ) (the confidence parameter) with M ≥ 10κ /pmax , let M =
(X1 , . . . , XM ) ∈ {1, . . . , N }M be the distribution obtained by sampling each Xj independently from
the distribution that assigns to element i probability pi . Then, there exists a rejection sampling proce′ )∈
dure that, up to statistical distance exp(−Ω(κ)), maps M to the distribution M′ := (X1′ , . . . , XM
′
M
obtained by sampling each pair Xj independently from the distribution that
{(1, 1), . . . , (N, N )}
assigns to the pair (i, i) probability p2i /pcol , where


pcol
M := M ·
32κpmax
′

pmax := max pi , and pcol :=

P



,

p2i .
P

Corollary A.4. For any probabilities, p1 , . . . , pN ∈ [0, 1] with
pi = 1, integer M , and κ ≥
2
Ω(log M ) (the confidence parameter) with M ≥ 10κ /pmax , let M := (X1 , . . . , XM ) ∈ {1, . . . , N }M
be the distribution obtained by sampling each Xj independently from the distribution that assigns to
′ ) ∈ {(1, 1), . . . , (N, N )}M ′ be the distribution
element i probability pi , and let M′ := (X1′ , . . . , XM
′
obtained by sampling each pair Xj′ independently from the distribution that assigns to the pair (i, i)
probability p2i /pcol , where


pcol
′
,
M := M ·
32κpmax
pmax := max pi , and pcol :=

A.3

P

p2i . Then, M dominates M′ .

Additional facts about the discrete Gaussian

We will also need some additional facts about the discrete Gaussian.
Lemma A.5 ([Ban93]). For any lattice L ⊂ Rn , parameter s ≥ 1, and shift t ∈ Rn , ρs (L − t) ≤
sn ρ(L).
The following theorem shows that, if the parameter s is appropriately small, then DL−t,s + t
√
will be an approximate closest vector to t, with approximation factor roughly 1 + ns/ dist(t, L).
(This is a basic consequence of Banaszczyk’s celebrated theorem [Ban93].)
Proposition A.6 ([Ste17, Corollary 1.3.11], see alsop[ADS15, Corollary 2.8]). For any lattice
L ⊂ Rn , parameter s > 0, shift t ∈ Rn , and radius r > n/(2π) · s, with r > dist(t, L) and
r 2 > dist(t, L)2 +

ns2
· log(2π dist(t, L)2 /(ns2 )) ,
π

we have
Pr

X∼DL−t,s

where y :=

[kXk > r] < (2e)n/2+1 exp(−πy 2 /2) ,

p

r 2 − dist(t, L)2 /s.

√
The next theorem shows that exponentially many samples from DL,s with s ≈ λ1 (L)/ n is
sufficient to find a shortest non-zero lattice vector.

14

Proposition A.7 ([ADRS15, Proposition 4.3]). For any lattice L ⊂ Rn , and parameter
s :=
we have

q

20.198 πe/n · λ1 (L) ,

Pr [kXk = λ1 (L)] ≥ 1.38−n−o(n) .

X∼DL,s

The next corollary follows immediately from Proposition A.7 and Lemma A.5.
Corollary A.8. For any lattice L ⊂ Rn , and parameter
q

20.198 πe/n · λ1 (L) ≤ s ≤ 1.01 ·

we have

q

20.198 πe/n · λ1 (L) ,

Pr [kXk = λ1 (L)] ≥ 1.4−n−o(n) .

X∼DL,s

We will also need the following result from [ADS15], which is an immediate consequence of the
main identity in [RS17]. (See also [Ste17].)
Lemma A.9 ([ADS15, Corollary 3.3]). For any lattice L ⊂ Rn , shift t ∈ Rn , and parameter s > 0,
we have
max ρs (2L + c − t)2 ≤ ρs/√2 (L) max ρs/√2 (2L + c − t) .
c∈L

c∈L/(2L)

From this, we derive the following rather technical-looking inequality, which is implicit in [ADS15].
(This inequality comes up naturally in the proof of Corollary B.2. We separate it out here to make
that proof cleaner.)
Corollary A.10. For any lattice L ⊂ Rn , shift t ∈ Rn , parameter s > 0, and integer ℓ ≥ 0, we
have
ℓ−1
Y
i=0

ρs/2(i+1)/2 (L − t)ρs/2(i+1)/2 (L)

ρs/2i/2 (L − t) · maxc∈L/(2L) ρs/2i/2 (2L + c − t)
≥

ρs/2ℓ/2 (L − t)

maxc∈L/(2L) ρs (2L + c − t)
.
maxc∈L/(2L) ρs/2ℓ/2 (2L + c − t)
ρs (L − t)
·

Proof. From Lemma A.9, we see that for all i,
ρs/2(i+1)/2 (L)
maxc∈L/(2L) ρs/2i/2 (2L + c − t)

≥

maxc∈L/(2L) ρs/2i/2 (2L + c − t)

maxc∈L/(2L) ρs/2(i+1)/2 (2L + c − t)

.

Therefore, the product in the statement of the corollary is at least
ℓ−1
Y
i=0

ρs/2(i+1)/2 (L − t) · maxc∈L/(2L) ρs/2i/2 (2L + c − t)

ρs/2i/2 (L − t) · maxc∈L/(2L) ρs/2(i+1)/2 (2L + c − t)
=

ρs/2ℓ/2 (L − t)

maxc∈L/(2L) ρs (2L + c − t)
,
maxc∈L/(2L) ρs/2ℓ/2 (2L + c − t)
ρs (L − t)
·

where we have used the fact that this is a telescoping product.
15

B

Running Procedure 1 on Gaussian input

Theorem B.1. For any lattice L ⊂ Rn , shift t ∈ Rn , parameter s > 0, integer M , and confidence
parameter κ ≥ Ω(log M ), if X 1 , . . . , X M are sampled independently from DL−t,s with
M ≥ 10κ2 ·

ρs (L − t)
,
maxc∈L/(2L) ρs (2L + c − t)

then the output
√ of Procedure 1 applied to the X i will be a mixture of independent Gaussians with
parameter s/ 2 that dominates the distribution of
&

ρs/√2 (L − t) · ρs/√2 (L)
M
·
M ′ :=
32κ ρs (L − t) · maxd∈L/(2L) ρs (2L + d − t)

'

independent samples from DL−t,s/√2 , up to statistical distance exp(−Ω(κ)).
Proof. By Item 2 of Corollary 3.3, the resulting
√ distribution will in fact be a mixture of independent Gaussians over L − t with parameter s/ 2. Notice that, if M is the coset distribution of
(X 1 , . . . , X M ), then Procedure 1 first maps the X i into the mixture of independent Gaussians
over L − t with parameter s and coset distribution ⌊M/2⌋ and then takes the averages of the
corresponding pairs of these vectors.
We wish to apply Corollary A.4 over the coset distribution, with the probabilities pi := p2L+c
taken to be the weights of the cosets in the original distribution discrete Gaussian,
p2L+c :=
Notice that, by Lemma 2.1,

ρs (2L + c − t)
.
ρs (L − t)



pcol
M = M·
32κpmax
′



,

which is exactly what is needed to apply Corollary A.4. By the corollary, up to statistical distance
exp(−Ω(κ)) this distribution dominates the mixture of independent Gaussians over L − t with
parameter s whose coset distribution is given by c2k−1 = c2k for 1 ≤ k ≤ M ′ , with the oddindexed cosets c2k−1 sampled independently from the distribution that assigns to coset c ∈ L/(2L)
probability
pi
ρs (2L + c − t)2
=P
.
2
pcol
d∈L/(2L) ρs (2L + d − t)

Notice that this “squared” distribution” (so-called because the cosets are given weight proportional
to their square) is simply M ′ independent copies of the distribution from Item 4 of Corollary 3.3.
So, if we run Procedure 1 on this “squared” distribution, the output will be exactly M ′ independent
samples from DL−t,s/√2 .
Finally, by Fact 2.3, we see that, since the actual pairs dominate these “squared” pairs (up
to statistical distance exp(−Ω(κ))), the output must dominate M ′ independent samples from
DL−t,s/√2 .

16

Corollary B.2. For any lattice L ⊂ Rn , shift t ∈ Rn , parameter s > 0, integer M ≥ 2, and
confidence parameter κ ≥ Ω(log M ), if X 1 , . . . , X M are sampled independently from DL−t,s with
M ≥ (10κ)2ℓ ·

ρs (L − t)
,
maxc∈L/(2L) ρs (2L + c − t)

and we apply Procedure 1 repeatedly to the X i a total of ℓ ≥ 1 times, the result will be a mixture
of independent Gaussians with parameter s/2ℓ/2 that dominates the distribution of
&

ℓ−1
Y
ρs/2(i+1)/2 (L − t)ρs/2(i+1)/2 (L)
M
′
M :=
·
(32κ)ℓ i=0 ρs/2i/2 (L − t) · maxc∈L/(2L) ρs/2i/2 (2L + c − t)

'

independent samples from DL−t,s/2ℓ/2 , up to statistical distance ℓ exp(−Ω(κ)).
Proof. By Item 2 of Corollary 3.3, the output will in fact be a mixture of independent Gaussians
over L − t with parameter s/2ℓ/2 . The only question is what the coset distribution is.
To show that the coset distribution is as claimed, the idea is to simply apply Theorem B.1 ℓ
times. In particular, we prove the result via induction on ℓ. When ℓ = 1, this is exactly Theorem B.1.
For ℓ > 1, we assume the statement is true for ℓ − 1. In particular, before applying Procedure 1
the ℓth time, we have a mixture of independent Gaussians with parameter s/2ℓ/2 that dominates
&

ℓ−2
Y
ρs/2(i+1)/2 (L − t)ρs/2(i+1)/2 (L)
M
c :=
M
·
(32κ)ℓ i=0 ρs/2i/2 (L − t) · maxc∈L/(2L) ρs/2i/2 (2L + c − t)

≥ 10κ2 ·

'

ℓ−2
Y
ρs/2(i+1)/2 (L − t)ρs/2(i+1)/2 (L)
ρs (L − t)
·
maxc∈L/(2L) ρs (L + c − t) i=0 ρs/2i/2 (L − t) · maxc∈L/(2L) ρs/2i/2 (2L + c − t)

independent Gaussians up to statistical distance (ℓ − 1) exp(−Ω(κ)).
c samples dominates
By Fact 2.3, it suffices to prove that the output of Procedure 1 on these M
′
M independent samples from DL−t,s/2ℓ/2 up to statistical distance exp(−Ω(κ)). Indeed, this is
exactly what Theorem B.1 says, provided that
c ≥ 10κ2 ·
M

ρs/2(ℓ−1)/2 (L − t)

maxc∈L/(2L) ρs/2(ℓ−1)/2 (2L + c − t)

.

And, this inequality follows immediately from Corollary A.10 together with the assumed lower
c.
bound on M

C

The initial distribution

The following theorem was proven by Ajtai, Kumar, and Sivakumar [AKS01], building on work of
Schnorr [Sch87].
Theorem C.1 ([Sch87, AKS01]). There is an algorithm that takes as input a lattice L ⊂ Rn and
u ≥ 2 and outputs an un/y -reduced basis of L in time exp(O(u)) · poly(n), where we say that a basis
B = (b1 , . . . , bn ) of a lattice L is γ-reduced for some γ ≥ 1 if
1. kb1 k ≤ γ · λ1 (L); and
17

2. π{b1 }⊥ (b2 ), . . . , π{b1 }⊥ (bn ) is a γ-reduced basis of π{b1 }⊥ (L).
This next theorem is originally due to [GPV08], based on analysis of an algorithm originally
studied by Klein [Kle00]. We present a slightly stronger version due to [BLP+ 13] for convenience.
that
Theorem C.2 ([BLP+ 13, Lemma 2.3]). There is a probabilistic polynomial-time algorithm
√
e
takes as input a basis B for a lattice L ⊂ Rn with n ≥ 2, a shift t ∈ Rn , and ŝ > C log n · kBk
e
e
and outputs a vector that is distributed exactly as DL−t,ŝ , where kBk := maxkbi k.
Proposition C.3 ([ADS15, Proposition 4.5]). There is an algorithm that takes as input a lattice
L ⊂ Rn , shift t ∈ Rn , r > 0, and parameter u ≥ 2, such that if
√
r ≥ un/u (1 + nun/u ) · dist(t, L) ,

then the output of the algorithm is y ∈ L and a basis B′ of a (possibly trivial) sublattice L′ ⊆ L
such that all vectors from L − t of length at most r/un/u − dist(t, L) are also contained in L′ − y − t,
e ′ k ≤ r. The algorithm runs in time poly(n) · 2O(u) .
and kB

Proof. On input a lattice L ⊂ Rn , t ∈ Rn , and r > 0, the algorithm behaves as follows. First, it
calls the procedure from Theorem C.1 to compute a un/u -HKZ basis B = (b1 , . . . , bn ) of L. Let
e ,...,e
ek≤r
(b
bn ) be the corresponding Gram-Schmidt vectors. Let k ≥ 0 be maximal such that kb
1
i
′
for 1 ≤ i ≤ k, and let B = (b1 , . . . , bk ). Let πk = π{b1 ,...,bk }⊥ and M = πk (L). The algorithm then
calls the procedure from Theorem C.1 again with the same s and input πk (t) and M, receiving
√
P
as output x = ni=k+1 ai πk (bi ) where ai ∈ Z, a nun/u -approximate closest vector to πk (t) in M.
Pn
Finally, the algorithm returns y = − i=k+1 ai bi and B′ = (b1 , . . . , bk ).
f′ k ≤ r. It remains to prove that L′ − y − t
The running time is clear, as is the fact that kB
contains all sufficiently short vectors in L − t. If k = n, then L′ = L and y is irrelevant, so we may
n/u > r/un/u . In
e
assume that k < n. Note that, since B is a un/u -HKZ basis, λ1 (M) ≥ kb
k+1 k/u
√
√
particular, λ1 (M) > (1 + n · un/u ) · dist(t, L) ≥ (1 + n · un/u ) · dist(πk (t), M). So, there is a
unique closest vector to πk (t) in M, and by triangle inequality, the next closest vector is at distance
√
greater than n · un/u dist(πk (t), M). Therefore, the call to the subprocedure from Theorem C.1
will output the exact closest vector x ∈ M to πk (t).
Let w ∈ L \ (L′ − y) so that πk (w) 6= πk (−y) = x. We need to show that w − t is relatively
long. Since B is a sn/s -HKZ basis, it follows that
kπk (w) − xk ≥ λ1 (M) > r/un/u .
Applying triangle inequality, we have
kw − tk ≥ kπk (w) − πk (t)k ≥ kπk (w) − xk − kx − πk (t)k > r/un/u − dist(t, L) ,
as needed.
Corollary C.4 ([ADS15, Corollary 4.6]). There is an algorithm that takes as input a lattice L ⊂ Rn
with n ≥ 2, shift t ∈ Rn , M ∈ N (the desired number of output vectors), and parameters u ≥ 2 and
ŝ > 0 and outputs y ∈ L, a (possibly trivial) sublattice L′ ⊆ L, and M vectors from L′ − y − t such
that if
p
ŝ ≥ 10 n log n · u2n/u · dist(t, L) ,

then the output vectors are distributed as M independent samples
from DL′ −y−t,ŝ , and L′ − y − t
√
contains all vectors in L − t of length at most ŝ/(10un/u log n). The algorithm runs in time
poly(n) · 2O(u) + poly(n) · M . (And, if t = 0, then y = 0.)
18

Proof. The algorithm first calls the procedure from Proposition C.3 with input L, t, and
√
10ŝ
r := √
≥ un/u (1 + nun/u ) · dist(t, L) ,
log n
receiving as output y ∈ L and a basis B′ of a sublattice L′ ⊂ L. It then runs the algorithm from
Theorem C.2 M times with input L′ , y + t, and ŝ and outputs the resulting vectors, y, and L′ .
The running time is clear. By Proposition C.3, L′ − y − t contains all vectors of length at most
√
√
e ′ k ≤ r ≤ C ŝ/ log n. So, it follows from
r/un/u − dist(t, L) ≥ ŝ/(10un/u log n) in L − t, and kB
Theorem C.2 that the output has the correct distribution.

D

Finishing the proof
SVP (L)
Input : A lattice L ⊂ Rn
Output : A vector y ∈ L with kyk = λ1 (L)
b with λ1 (L) ≤ λ
b ≤ 2n/2 λ1 (L).
Use the procedure from Thereom A.1 to compute λ
for i = 1, . . . , 200n do
Set L′ ⊆ L and X 1 , . . . , X M ∈ L to be the output of Corollary C.4 on input L, t := 0, u,
b
and si := 1.01−i · λ.
for j = 1, . . . , ℓ do
(X 1 , . . . , X M ′ ) ← Pair and Average(X 1 , . . . , X M )
M ← M′
end
Y i ← arg minX j 6=0 kX j k.
end
Output arg min kY i k.

Procedure 3: The final 2n+o(n) -time SVP algorithm. Here M = 2n+Θ(log
ℓ = Θ(log n).

2

n) ,

u = Θ(n), and

Theorem D.1 (SVP algorithm). For any lattice L ⊂ Rn , the output of Procedure 3 on input L
will be a shortest non-zero vector in L except with probability at most exp(−Ω(n)).
Proof. The running time is clear. Let κ = Θ(n). Let i such that si /2ℓ/2 satisfies the inequality
in Corollary A.8. By Corollary C.4, the (X 1 , . . . , X M ) corresponding to this i will be distributed
exactly as DL′ ,si where L′ ⊆ L contains all vectors of length at most λ1 (L). So, λ1 (L′ ) = λ1 (L),
and it suffices to argue that we will find a shortest vector in L′ . By Corollary B.2, the output
distribution (X1 , . . . , XM ) will be a mixture of independent Gaussians over L′ with parameter
si /2ℓ/2 that dominates the distribution of


ρsi /2(j+1)/2 (L′ )2

ℓ−1
Y



M

M′ = 
 (32κ)ℓ ·
(L′ ) · ρsi /2(j+2)/2 (L′ ) 
ρ


j=0 si /2j/2
19

independent samples from DL′ ,si /2ℓ/2 up to statistical distance exp(−Ω(κ)), where we have applied
Lemma A.5 to show that the coset with maximal mass is the central coset. Noting that this product
is telescoping, we have
&

'

ρsi /√2 (L′ )
ρsi /2ℓ/2 (L′ )
M
M =
·
·
≥ 2n/2 ,
(32κ)ℓ
ρsi (L′ )
ρsi /2(ℓ+1)/2 (L′ )
′

where we √
have applied Lemma A.5. The result then follows from Corollary A.8, together with the
fact that 2 > 1.4.
CVP (L, t)
Input : A lattice L ⊂ Rn and target t ∈ Rn
2
Output : A vector y ∈ L with ky − tk ≤ (1 + 2−n/ log n ) · dist(t, L)
Use the procedure from Thereom A.2 to compute dˆ with dist(L, t) ≤ dˆ ≤ 2n/2 dist(t, L).
for i = 1, . . . , n do
Set L′ ⊆ L, y ∈ L, and X1 , . . . , XM ∈ L′ − y − t to be the output of Corollary C.4 on
ˆ
input L, t, u, and si := 20n2 · 2−i · d.
for j = 1, . . . , ℓ do
(X 1 , . . . , X M ′ ) ← Pair and Average(X 1 , . . . , X M )
M ← M′
end
Y i ← arg minX j kX j k.
end
Output t + arg min kY i k.
Procedure 4: The final 2n+o(n) -time SVP algorithm. Here M = 2n+Θ(n/ log n) , u = Θ(n),
and ℓ = Θ(n/ log2 n).
Theorem D.2 (CVP algorithm). For any lattice L ⊂ Rn and t ∈ Rn , the output of Procedure 4
on input L and t will a vector y ∈ L with ky − tk ≤ (1 + exp(−Ω(n/ log2 n))) · dist(t, L), except
with probability at most exp(−Ω(n)).4
Proof. The running time is clear. Let κ = Θ(n). Let i such that
p

p

10 n log n · u2n/u · dist(t, L) ≤ si ≤ 20 n log n · u2n/u · dist(t, L) .
By Corollary C.4, the (X 1 , . . . , X M ) corresponding to this i will be distributed exactly as DL′ −y−t,si
where L′ − y − t ⊆ L − t contains all vectors of length at most dist(t, L). So, it suffices to argue
2
that we will find a (1 + 2−n/ log n )-approximate shortest vector in L′ − y − t. By Corollary B.2, the
output distribution (X1 , . . . , XM ) will be a mixture of independent Gaussians over L′ − y − t with
parameter si /2ℓ/2 that dominates the distribution of


4



ℓ−1
Y
ρsi /2(j+1)/2 (L′ − y − t)ρsi /2(j+1)/2 (L)
M
≥1
M′ = 
·
 (32κ)ℓ
(L′ − y − t) · maxc∈L′ /(2L′ ) ρsi /2j/2 (2L′ + c − y − t) 
ρ


j=0 si /2j/2

It is immediate from the proof that this result can be extended to work for any approximation factor γ with
γ > 1 + exp(−o(n/ log n)), by taking ℓ = o(n/ log n) and M = 2n+o(n) to be slightly larger.

20

independent samples from DL′ −y−t,si /2ℓ/2 up to statistical distance exp(−Ω(κ)), where we have
applied Corollary A.10.
Notice that si /2ℓ/2 < exp(−Ω(n/ log2 n)) dist(t, L). The result then follows from Proposition A.6, which says that, except with probability exp(−Ω(n)) a sample from DL′ −y−t,si /2ℓ/2 will
be a (1 + exp(−Ω(n/ log2 n)))-approximate shortest vector in L′ − y − t.

21

