On the Lattice Distortion Problem
Huck Bennett∗

Daniel Dadush†

Noah Stephens-Davidowitz∗‡

arXiv:1605.03613v3 [] 30 Oct 2016

January 1, 2018

Abstract
We introduce and study the Lattice Distortion Problem (LDP). LDP asks how “similar” two
lattices are. I.e., what is the minimal distortion of a linear bijection between the two lattices?
LDP generalizes the Lattice Isomorphism Problem (the lattice analogue of Graph Isomorphism),
which simply asks whether the minimal distortion is one.
As our first contribution, we show that the distortion between any two lattices is approximated up to a nO(log n) factor by a simple function of their successive minima. Our
methods are constructive, allowing us to compute low-distortion mappings that are within a
2O(n log log n/ log n) factor of optimal in polynomial time and within a nO(log n) factor of optimal
in singly exponential time. Our algorithms rely on a notion of basis reduction introduced by
Seysen (Combinatorica 1993), which we show is intimately related to lattice distortion. Lastly,
we show that LDP is NP-hard to approximate to within any constant factor (under randomized
reductions), by a reduction from the Shortest Vector Problem.

1

Introduction

An n-dimensional lattice L ⊂ Rn is the set of all integer linear combinations of linearly independent
n
vectors
Pn B = [b1 , . . . , bn ] with bi ∈ R . We write the lattice generated by basis B as L(B) =
{ i=1 ai bi : ai ∈ Z}.
Lattices are very well-studied classical mathematical objects (e.g., [Min10, CS98]), and over
the past few decades, computational problems on lattices have found a remarkably large number
of applications in computer science. Algorithms for lattice problems have proven to be quite
useful, and they have therefore been studied extensively (e.g., [LLL82, Kan87, AKS01, MV13]).
And, over the past twenty years, many strong cryptographic primitives have been constructed
with their security based on the (worst-case) hardness of various computational lattice problems
(e.g., [Ajt96, MR07, GPV08, Gen09, Reg09, BV14]).
In this paper, we address a natural question: how “similar” are two lattices? I.e., given lattices
L1 , L2 , does there exist a linear bijective mapping T : L1 → L2 that does not change the distances
between points by much? If we insist that T exactly preserves distances, then this is the Lattice
∗

Department of Computer Science, Courant Institute of Mathematical Sciences, New York University. Email:
hbennett@cs.nyu.edu, noahsd@gmail.com.
†
Centrum Wiskunde & Informatica, Amsterdam. Email: dadush@cwi.nl. Supported by the NWO Veni grant
639.071.510.
‡
This material is based upon work partially supported by the National Science Foundation under Grant No. CCF1320188. 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 National Science Foundation.

1

Isomorphism Problem (LIP), which was studied in [PS97, SSV09, HR14, LS14]. We extend this to
the Lattice Distortion Problem (LDP), which asks how well such a mapping T can approximately
preserve distances between points.
Given two lattices L1 , L2 , we define the distortion between them as
D(L1 , L2 ) = min{kT kkT −1 k : T (L1 ) = L2 } ,
where kT k = supkxk=1 kT xk is the operator norm. The quantity κ(T ) = kT k·kT −1 k is the condition
number of T , which measures how much T “distorts distances” (up to a fixed scaling). It is easy
to check that D(L1 , L2 ) bounds the ratio between most natural geometric parameters of L1 and
L2 (up to scaling), and hence D(L1 , L2 ) is a strong measure of “similarity” between lattices. In
particular, D(L1 , L2 ) = 1 if and only if L1 , L2 are isomorphic (i.e., if and only if they are related
by a scaled orthogonal transformation).
The Lattice Distortion Problem (LDP) is then defined in the natural way as follows. The input
is two n-dimensional lattices L1 , L2 (each represented by a basis), and the goal is to compute a
bijective linear transformation T mapping L1 to L2 such that κ(T ) = D(L1 , L2 ). In this work, we
study the approximate search and decisional versions of this problem, defined in the usual way.
We refer to them as γ-LDP and γ-GapLDP respectively, where γ = γ(n) ≥ 1 is the approximation
factor. (See Section 2.4 for precise definitions.)

1.1

Our Contribution

As our first main contribution, we show that the distortion between any two lattices can be approximated by a natural function of geometric lattice parameters. Indeed, our proof techniques are
constructive, leading to our second main contribution: an algorithm that computes low-distortion
mappings, with a trade-off between the running time and the approximation factor. Finally, we
show hardness of approximating lattice distortion.
To derive useful bounds on the distortion between two lattices, it is intuitively clear that one
should study the “different scales over which the two lattices live.” A natural notion of this is given
by the successive minima, which are defined as follows. The ith successive minimum, λi (L), of L is
the minimum radius r > 0 such that L contains i linearly independent vectors of norm at most r.
For example, a lattice generated by a basis of orthogonal vectors of lengths 0 < a1 ≤ · · · ≤ an has
successive minima λi (L) = ai . Since low-distortion mappings approximately preserve distances,
it is intuitively clear that two lattices can only be related by a low-distortion mapping if their
successive minima are close to each other (up to a fixed scaling).
Concretely, for two n-dimensional lattices L1 , L2 , we define
M (L1 , L2 ) = max
i∈[n]

λi (L2 )
,
λi (L1 )

(1)

which measures how much we need to scale up L1 so that its successive minima are at least as large
as those of L2 . For any linear map T from L1 to L2 , it is easy to see that λi (L2 ) ≤ kT kλi (L1 ).
Thus, by definition M (L1 , L2 ) ≤ kT k. Applying the same reasoning for T −1 , we derive the following
simple lower bound on distortion.
D(L1 , L2 ) ≥ M (L1 , L2 ) · M (L2 , L1 ) .

(2)

We note that this lower bound is tight when L1 , L2 are each generated by bases of orthogonal
vectors. But, it is a priori unclear if any comparable upper bound should hold for general lattices,
2

since the successive minima are a very “coarse” characterization of the geometry of the lattice.
Nevertheless, we show a corresponding upper bound.
Theorem 1.1. Let L1 , L2 be n-dimensional lattices. Then,
M (L1 , L2 ) · M (L2 , L1 ) ≤ D(L1 , L2 ) ≤ nO(log n) · M (L1 , L2 ) · M (L2 , L1 ) .
In particular, Theorem 1.1, together with standard transference theorems (e.g., [Ban93]), implies
that nO(log n) -GapLDP is in NP∩coNP. While the factor on the right-hand side of the theorem might
√
be far from optimal, we show in Section 5.1 that it cannot be improved below Ω( n). Intuitively,
this is because there exist lattices that are much more dense than Zn over large scales but still have
λi (L) = Θ(1) for all i. I.e., there exist very dense lattice sphere packings (see, e.g., [Sie45]).
To prove the above theorem, we make use of the intuition that a low-distortion mapping T from
L1 to L2 should map a “short” basis B1 of L1 to a “short” basis B2 of L2 . (Note that the condition
T B1 = B2 completely determines T = B2 B1−1 .) The difficulty here is that standard notions of
“short” fail for the purpose of capturing low-distortion mappings. In particular, in Section 5.2,
we show that Hermite-Korkine-Zolotarev (HKZ) reduced bases, one of the strongest notions of
“shortest possible” lattice bases, do not suffice by themselves for building low-distortion mappings.
(See Section 2.6 for the definition of HKZ-reduced bases.) In particular, we give a simple example
of a lattice L where an HKZ-reduced basis of L misses the optimal distortion D(Zn , L) by an
exponential factor.
Fortunately, we show that a suitable notion of shortness does exist for building low-distortion
mappings by making a novel connection between low-distortion mappings and a notion of basis
reduction introduced by Seysen [Sey93]. In particular, for a basis B = [b1 , . . . , bn ] and dual basis
B ∗ = B −T = [b∗1 , . . . , b∗n ], Seysen’s condition number is defined as
S(B) = max kbi kkb∗i k .
i∈[n]

Note that we always have hbi , b∗i i = 1, so this parameter measures how tight the Cauchy-Schwarz
inequality is over all primal-dual basis-vector pairs. We extend this notion and define S(L) as
the minimum of S(B) over all bases B of L. Using this notion, we give an effective version of
Theorem 1.1 as follows.
Theorem 1.2. Let L1 , L2 be n-dimensional lattices. Let B1 , B2 ∈ Rn×n be bases of L1 , L2 whose
columns are sorted in non-decreasing order of length. Then, we have that
M (L1 , L2 )M (L2 , L1 ) ≤ κ(B2 B1−1 ) ≤ n2 S(B1 )2 S(B2 )2 · M (L1 , L2 )M (L2 , L1 ) .
In particular, we have that
M (L1 , L2 )M (L2 , L1 ) ≤ D(L1 , L2 ) ≤ n2 S(L1 )2 S(L2 )2 · M (L1 , L2 )M (L2 , L1 ) .
From here, the bound in Theorem 1.1 follows directly from the following (surprising) theorem
of Seysen.
Theorem 1.3 (Seysen [Sey93]). For any L ⊂ Rn , S(L) ≤ nO(log n) .

3

This immediately yields an algorithm for approximating the distortion between two lattices, by
using standard lattice algorithms to approximate M (L1 , L2 ) and M (L2 , L1 ). But, Seysen’s proof
of the above theorem is actually constructive! In particular, he shows how to efficiently convert any
suitably reduced lattice basis into a basis with a low Seysen condition number. (See Section 2.6.2
for details.) Using this methodology, combined with standard basis reduction techniques, we derive
the following time-approximation trade-off for γ-LDP.
Theorem 1.4 (Algorithm for LDP). For any log n ≤ k ≤ n, there is an algorithm solving
kO(n/k+log n) -LDP in time 2O(k) .
In other words, using the bounds in Theorem 1.1 together with known algorithms, we are able
to approximate the distortion between two lattices. But, with a bit more work, we are able to solve
search LDP by explicitly computing a low-distortion mapping between the input lattices.
We also prove the following lower bound for LDP.
Theorem 1.5 (Hardness of LDP). γ-GapLDP is NP-hard under randomized polynomial-time reductions for any constant γ ≥ 1.
In particular, we show a reduction from approximating the (decisional) Shortest Vector Problem
(GapSVP) over lattices to γ-GapLDP, where the approximation factor that we obtain for GapSVP
is O(γ). Since hardness of GapSVP is quite well-studied [Ajt98, Mic01, Kho05, HR12], we are
immediately able to import many hardness results to GapLDP. (See Corollary 4.7 and Theorem 4.8
for the precise statements.)

1.2

Comparison to related work

The main related work of which we are aware is that of Haviv and Regev [HR14] on the Lattice
Isomorphism Problem (LIP). In their paper, they give an nO(n) -time algorithm for solving LIP
exactly, which proceeds by cleverly identifying a small candidate set of bases of L1 and L2 that
must be mapped to each other by any isomorphism. One might expect that such an approach
should also work for the purpose of solving LDP either exactly or for approximation factors below
nO(log n) . However, the crucial assumption in LIP, that vectors in one lattice must be mapped to
vectors of the same length in the other, completely breaks down in the current context. We thus
do not know how to extend their techniques to LDP.
Much more generally, we note that LIP is closely related to the Graph Isomorphism Problem
(GI). For example, both problems are in SZK but not known to be in P (although recent work on
algorithms for GI has been quite exciting [Bab16]!), and GI reduces to LIP [SSV09]. Therefore,
LDP is qualitatively similar to the Approximate Graph Isomorphism Problem, which was studied by
Arora, Frieze, and Kaplan [AFK02], who showed an upper bound, and Arvind, Köbler, Kuhnert,
and Vasudev [AKKV12], who proved both upper and lower bounds. In particular, [AKKV12]
showed that various versions of this problem are NP-hard to approximate to within a constant
factor. Qualitatively, these hardness results are similar to our Theorem 1.5.

1.3

Conclusions and Open Problems

In conclusion, we introduce the Lattice Distortion Problem and show a connection between LDP
and the notion of Seysen-reduced bases. We use this connection to derive time-approximation tradeoffs for LDP. We also prove approximation hardness for GapLDP, showing a qualitative difference
with LIP (which is unlikely to be NP-hard under reasonable complexity theoretic assumptions).
4

One major open question is what the correct bound in Theorem 1.3 is. In particular, there are
no known families of lattices for which the Seysen condition number is provably superpolynomial,
and hence it is possible that S(L) = poly(n) for any n-dimensional lattice L. A better bound would
immediately improve our Theorem 1.2 and give a better approximation factor for GapLDP.
We also note that all of our algorithms solve LDP for arguably very large approximation factors
nΩ(log n) . We currently do not even know whether there exists a fixed-dimension polynomial-time
algorithm for γ-LDP for any γ = no(log n) . The main problem here is that we do not have any good
characterization of nearly optimal distortion mappings between lattices.

Organization
In Section 2, we present necessary background material. In Section 3, we give our approximations
for lattice distortion, proving Theorems 1.2 and 1.4. In Section 4, we give the hardness for lattice
distortion, proving Theorem 1.5. In Section 5, we give some illustrative example instances of lattice
distortion.

Acknowledgements
We thank Oded Regev for pointing us to Seysen’s paper and for many helpful conversations. The
concise proof of Lemma ?? using the Transference Theorem is due to Michael Walter. We thank
Paul Kirchner for telling us about Proposition 2.13, and for identifying a minor bug in an earlier
version of this paper.

2

Preliminaries

For x ∈ Rn , we write kxk for the Euclidean norm of x. We omit any mention of the bit length in
the running time of our algorithms. In particular, all of our algorithms take as input vectors in Qn
and run in time f (n) · poly(m) for some f , where m is the maximal bit length of an input vector.
We therefore suppress the factor of poly(m).

2.1

Lattices

The ith successive minimum of a lattice L is defined as λi (L) = inf{r > 0 : dim(span(rB2n ∩ L)) ≥ i}.
That is, the first successive minimum is the length of the shortest non-zero lattice vector, the second
successive minimum is the length of the shortest lattice vector which is linearly independent of a
vector achieving the first, and so on. When L is clear from context, we simply write λi .
The dual lattice of L is defined as L∗ = {x ∈ Rn : ∀y ∈ L hx, yi ∈ Z}. If L = L(B) then
∗
L = L(B ∗ ) where B ∗ = B −T , the inverse transpose of B. We call B ∗ = [b∗1 , . . . , b∗n ] the dual basis
of B, and write λ∗i = λi (L∗ ). We will repeatedly use Banaszczyk’s Transference Theorem, which
relates the successive minima of a lattice to those of its dual.
Theorem 2.1 (Banaszczyk’s Transference Theorem [Ban93]). For every rank n lattice L and every
i ∈ [n], 1 ≤ λi (L)λn−i+1 (L∗ ) ≤ n.
Given a lattice L, we define the determinant of L as det(L) := | det(B)|, where B is a basis
with L(B) = L. Since two bases B, B ′ of L differ by a unimodular transformation, we have that
| det(B)| = | det(B ′ )| so that det(L) is well-defined.
5

We sometimes work with lattices that do not have full rank—i.e., lattices generated by d linearly
independent vectors L = L(b1 , . . . , bd ) with d < n. In this case, we simply identify span(b1 , . . . , bd )
with Rd and consider the lattice to be embedded in this space.

2.2

Linear mappings between lattices

We next characterize linear mappings between lattices in terms of bases.
Lemma 2.2. Let L1 , L2 be full-rank lattices. Then a mapping T : L1 → L2 is bijective and linear
if and only if T = BA−1 for some bases A, B of L1 , L2 respectively. In particular, for any basis A
of L1 , T (A) is a basis of L2 .

Proof. We first show that such a mapping is a bijection from L1 to L2 . Let T = BA−1 where
A = [a1 , . . . , an ] and B = [b1 , . . . , bn ] are bases of L1 , L2 respectively. Because T has full rank,
it is injective as a mapping from Rn to RnP
, and it is therefore injective as P
a mapping from L1 to
n
n
L2 . We have
that
for
every
w
∈
L
,
w
=
c
b
with
c
∈
Z.
Let
v
=
2
i
i=1 i i
i=1 ci ai ∈ L1 . Then,
Pn
Pn
T (v) = T ( i=1 ci ai ) = i=1 ci bi = w. Therefore, T is a bijection from L1 to L2 .
We next show that any linear map T with T (L1 ) = L2 must have this form. Let A = [a1 , . . . , an ]
be a basis of L1 , and let B = T (A). We claim that B = [b1 , . . . , bn ] is a basis of L2 .
Let w ∈ L2 . Because T is a bijection between L1 and L2 , there exists v ∈ L1 such that T v = w.
Using the definition of a basis and the linearity of T ,
w = Tv = T

n
X
i=1

n
 X
ci bi ,
ci ai =
i=1

for some c1 , . . . , cn ∈ Z. Because w was picked arbitrarily, it follows that B is a basis of L2 .

2.3

Seysen’s condition number S(B)

Seysen shows how to take any basis with relatively low multiplicative drop in its Gram-Schmidt
vectors and convert it into a basis with relatively low S(B) = maxi kbi kkb∗i k [Sey93]. By combining
this with Gama and Nguyen’s slide reduction technique [GN08], we obtain the following result.
Theorem 2.3. For every log n ≤ k ≤ n there exists an algorithm that takes a lattice L as input
and computes a basis B of L with S(B) ≤ k O(n/k+log k) in time 2O(k) .
In particular, applying Seysen’s procedure to slide-reduced bases suffices. We include a proof
of Theorem 2.3 and a high-level description of Seysen’s procedure in Section 2.6.

2.4

The Lattice Distortion Problem

Definition 2.4. For any γ = γ(n) ≥ 1, the γ-Lattice Distortion Problem (γ-LDP) is the search
problem defined as follows. The input consists of two lattices L1 , L2 (represented by bases B1 , B2 ∈
Qn×n ). The goal is to output a matrix T ∈ Rn×n such that T (L1 ) = L2 and κ(T ) ≤ γ · D(L1 , L2 ).
Definition 2.5. For any γ = γ(n) ≥ 1, the γ-GapLDP is the promise problem defined as follows.
The input consists of two lattices L1 , L2 (represented by bases B1 , B2 ∈ Qn×n ) and a number c ≥ 1.
The goal is to decide between a ‘YES’ instance where D(L1 , L2 ) ≤ c and a ‘NO’ instance where
D(L1 , L2 ) > γ · c.
6

2.5

Complexity of LDP

We show some basic facts about the complexity of GapLDP. First, we show that the Lattice
Isomorphism Problem (LIP) corresponds to the special case of GapLDP where c = 1. LIP takes
bases of L1 , L2 as input and asks if there exists an orthogonal linear transformation O such that
O(L1 ) = L2 . Haviv and Regev [HR14] show that there exists an nO(n) -time algorithm for LIP, and
that LIP is in the complexity class SZK.
Lemma 2.6. There is a polynomial-time reduction from LIP to 1-GapLDP.
Proof. Let L1 , L2 be an LIP instance. First check that det(L1 ) = det(L2 ). If not, then output a
trivial ‘NO’ instance of 1-GapLDP. Otherwise, map the LIP instance to the 1-GapLDP instance
with the same input bases and c = 1. For any T : L1 → L2 , we must have det(T ) = 1, and therefore
κ(T ) = 1 if and only if kT k = kT −1 k = 1. So, this is a ‘YES’ instance of GapLDP if and only if
L1 , L2 are isomorphic.
Lemma 2.7. 1-GapLDP is in NP.
Proof. Let I = (L1 , L2 , c) be an instance of GapLDP, and let s be the length of I. We will show
that for a ‘YES’ instance, there are bases A, B of L1 , L2 respectively such that T = BA−1 requires
at most poly(s) bits to specify and κ(T ) ≤ c. Assume without loss of generality that L1 , L2 ⊆ Zn .
Otherwise, scale the input lattices to achieve this at the expense of a factor s blow-up in input size.
To satisfy kT kkT −1 k ≤ c, we must have that |tij | ≤ kT k ≤ c · det(L2 )/ det(L1 ) ≤ c · det(L2 ) for
each entry tij of T . By Cramer’s rule, each entry of A−1 and hence T will be an integer multiple
of det1L1 , so we can assume without loss of generality that the denominator of each entry of T is
det L1 .
Combining these bounds and applying Hadamard’s inequality, we get that |tij | takes at most
n
n

 Y
Y
kai k kbi k
log(c · det(L1 ) det(L2 )) ≤ log c ·
i=1

i=1

bits to specify. Accounting for the sign of each tij , it follows that T takes at most n2 · log(2c ·
Q
n
2
i=1 kai kkbi k) ≤ n · (s + 1) bits to specify.

We remark that we can replace c with the quantity nO(log n) M (L1 , L2 )M (L2 , L1 ) (as given by
the upper bound in Theorem 1.1) in the preceding argument to obtain an upper bound on the
distortion of an optimal mapping T that does not depend on c.

2.6

Basis reduction

In this section, we define various notions of basis reductions and show how to use them to prove
Theorem 2.3.
(B)
For a basis B = [b1 , . . . , bn ], we write πi := π{b1 ,...,bi−1 }⊥ to represent projection onto the
e1 , . . . , b
en )
subspace {b1 , . . . , bi−1 }⊥ . We then define the Gram-Schmidt orthogonalization of B, (b
(B)
e i = π (bi ). By construction the vectors b
e1, . . . , b
e n are orthogonal, and each bi is a linear
as b
i

e1 , . . . , b
ei . We define µij =
combination of b

ej i
hbi ,b
e j ,b
ej i .
hb

7

We define the QR-decomposition of a full-rank matrix B as B = QR where Q has orthonormal
columns, and R is upper triangular. The QR-decomposition of a matrix is unique, and can be
computed efficiently by applying Gram-Schmidt orthogonalization to the columns of B.
Unimodular matrices, denoted GL(n, Z), form the multiplicative group of n × n matrices with
integer entries and determinant ±1.
Fact 2.8. L(B) = L(B ′ ) if and only if there exists U ∈ GL(n, Z) such that B ′ = B · U .
Based on this, a useful way to view basis reduction is as right-multiplication by unimodular
matrices.
2.6.1

Slide-reduced bases

A very strong notion of basis reduction introduced by Korkine and Zolotareff [KZ73] gives one way
of formalizing what it means to be a “shortest-possible” lattice basis.
Definition 2.9 ([KZ73], Definition 1 in [Sey93]). Let B be a basis of L. B = [b1 , . . . , bn ] is HKZ
(Hermite-Korkine-Zolotareff) reduced if
1. ∀j < i, |µij | ≤ 12 ;
2. kb1 k = λ1 (L(B)); and
(B)

(B)

(B)

3. if n > 1, then [π2 (b2 ), . . . , π2 (bn )] is an HKZ basis of π2 (L).
By definition, the first vector b1 in an HKZ basis is a shortest vector in the lattice. Furthermore,
computing an HKZ basis can be achieved by making n calls to an SVP oracle. So, the two problems
have the same time complexity up to a factor of n. In particular, computing HKZ bases is NP-hard.
Gama and Nguyen (building on the work of Schnorr [Sch87]) introduced the notion of slidereduced bases [GN08], which can be thought of as a relaxed notion of HKZ bases that can be
computed more efficiently.
Definition 2.10 ([GN08, Definition 1]). Let B be a basis of L ⊂ Qn and ε > 0. We say that B is εDSVP (dual SVP) reduced if its corresponding dual basis [b∗1 , . . . , b∗n ] satisfies kb∗n k ≤ (1+ε)·λ1 (L∗ ).
Then, for k ≥ 2 an integer dividing n, we say that B = [b1 , . . . , bn ] is (ε, k)-slide reduced if
1. ∀j < i, |µij | ≤ 21 ;
(B)

(B)

2. ∀0 ≤ i ≤ n/k − 1, the “projected truncated basis” [πik+1 (bik+1 ), . . . , πik+1 (bik+k )] is HKZ
reduced; and
(B)

(B)

3. ∀0 ≤ i ≤ n/k − 2, the “shifted projected truncated basis” [πik+2 (bik+2 ), . . . , πik+2 (bik+k+1 )]
is ε-DSVP reduced.
Theorem 2.11 ([GN08]). There is an algorithm that takes as input a lattice L ⊂ Qn , ε > 0, and
integer k ≥ log n dividing n and outputs a (k, ε)-slide-reduced basis of L in time poly(1/ε) · 2O(k) .

8

We will be particularly concerned with the ratios between the length of the Gram-Schmidt
vectors of a given basis. We prefer bases whose Gram-Schmidt vectors do not “decay too quickly,”
and we measure this decay by
eik
kb
.
η(B) = max
ej k
i≤j kb
Previous work bounded η(B) for HKZ-reduced bases as follows.

Theorem 2.12 ([LLS90, Proposition 4.2]). For any HKZ-reduced basis B over Qn , η(B) ≤
nO(log n) .
We now use Theorem 2.12 and some of the results in [GN08] to bound η(B) of slide-reduced
bases.
Proposition 2.13. For any integer k ≥ 2 dividing n, if B is an (1/n, k)-slide-reduced basis for a
lattice L ⊂ Qn , then η(B) ≤ kO(n/k+log k) .
Proof. We collect three simple inequalities that will together imply the result. First, from [GN08,
e 1 k ≤ kO(n/k) · kb
e jk+1 k for all 0 ≤ j ≤ n/k − 1. Noting that the projection
Eq. (16)], we have kb
[πik+1 (bik+1 ), . . . , πik+1 (bik+k )] of a slide-reduced basis is also slide reduced, we see that
e ik+1 k ≤ kO(n/k) · kb
e jk+1 k ,
kb

(3)

e ik+ℓ k ≤ kO(log k) · kb
e ik+ℓ′ k ,
kb

(4)

e ik+k k ≤ C · kb
e ik+k+1 k ,
kb

(5)

for all 0 ≤ i ≤ j ≤ n/k − 1. Next, from Theorem 2.12 and the fact that the “projected truncated
bases” are HKZ reduced, we have that

for all 1 ≤ ℓ ≤ ℓ′ ≤ k. Finally, [GN08] observe that1

for all 0 ≤ i ≤ n/k − 2, where C > 0 is some universal constant.
Now, let 0 ≤ i ≤ i′ ≤ n/k − 1 and 1 ≤ ℓ, ℓ′ ≤ k such that ik + ℓ < i′ k + ℓ′ . If i = i′ , then clearly
e ik+ℓ k/kb
e i′ k+ℓ′ k ≤ kO(log k) by Eq. (4). Otherwise, i < i′ and
kb
e ik+ℓ k
e ik+ℓ k
kb
kb
≤ kO(log k) ·
e i′ k+ℓ′ k
e i′ k+1 k
kb
kb
e ik+ℓ k
kb
≤ kO(n/k+log k) ·
e ik+k+1 k
kb
e ik+ℓ k
kb
≤ kO(n/k+log k) ·
e ik+k k
kb
≤ kO(n/k+log k)

(Eq. (4))

(Eq. (3))
(Eq. (5))
(Eq. (4)),

as needed.
Finally, we show how to get rid of the requirement that k divides n.
1

They actually observe that a slide-reduced basis is LLL reduced, which immediately implies Eq. (5).

9

Proposition 2.14. For any log n ≤ k ≤ n, there is an algorithm that takes as input a lattice
L ⊂ Qn and outputs a basis B of L such that η(B) ≤ kO(n/k+log k) . Furthermore, the algorithm
runs in time 2O(k) .
Proof. We assume without loss of generality that k is an integer. Let n′ = ⌈n/k⌉ · k be the smallest
integer greater than or equal to n that is divisible by k. On input a basis B̂ = [b̂1 , . . . , b̂n ] for
2
the lattice L ⊂ Qn , the algorithm behaves as follows. Let r = 2Ω(n ) · maxi kb̂i k. Let L′ :=
′
L(b̂1 , . . . , b̂n , r · en+1 , . . . , r · en′ ) ⊂ Qn be “the lattice obtained by appending n′ − n orthogonal
vectors of length r to L.” The algorithm then computes a basis B ′ = [b1 , . . . , bn′ ] of L′ as in
Theorem 2.11 with ε = 1/n and returns the basis consisting of the first n entries of B ′ , B =
[b1 , . . . , bn ].
It follows immediately from Theorem 2.11 that the running time is as claimed, and from Propo′
sition 2.13 we have that η(B) ≤ η(B ′ ) ≤ kO(n /k+log k) ≤ kO(n/k+log k) . So, we only need to prove
that B is in fact a basis for L (as opposed to some other sublattice of L′ ).
′
e i k ≥ r. We claim that π (B ) (B̂) = 0. If not, then choose j such
Consider the first i such that kb
i
(B ′ )
(B ′ )
that πi (b̂j ) 6= 0. There must be some ak + ℓ ≥ i with 1 ≤ ℓ ≤ k such that πak+ℓ (b̂j ) 6= 0, but
(B ′ )

πak+ℓ (b̂j ) ∈ span(πak+ℓ (bak+ℓ ), . . . , πak+ℓ (bak+k )). It follows from the fact that B ′ is a basis of L′
(B ′ )

that πak+ℓ (b̂j ) ∈ L(πak+ℓ (bak+ℓ ), . . . , πak+ℓ (bak+k )). But, since [πak+ℓ (bak+ℓ ), . . . , πak+ℓ (bak+k )] is
an HKZ basis, it must be the case that
(B ′ )

e ak+ℓ k = kπak+ℓ (bak+ℓ )k ≤ kπ
kb
ak+ℓ (b̂j )k ≤ kb̂j k ≤

r
2Ω(n2 )

<

ei k
kb
,
η(B ′ )

which contradicts the definition of η(B ′ ).
(B ′ )
So, πi (B̂) = 0. It follows that i = n + 1 and L ⊂ span(b1 , . . . , bi−1 ) = span(B). And, since
B ′ is a basis of L′ , it follows that L = L(B), as needed.
2.6.2

Seysen bases

Although slide-reduced bases B consist of short vectors and have bounded η(B), they make only
weak guarantees about the length of vectors in the dual basis B ∗ . Of course, one way to compute
a basis whose dual will contain short dual basis is short is to simply compute B such that B ∗
is a suitably reduced basis of L∗ . Such a basis B is called a dual-reduced basis, and sees use in
applications such as [HR14].
However, we would like to compute a basis such that the vectors in B and B ∗ are both short,
which Seysen addressed in his work [Sey93]. Seysen’s main result finds a basis B such that both
B and B ∗ are short by dividing this problem into two subproblems. The first involves finding a
basis with small η(B), as in Section 2.6.1. The second subproblem, discussed in [Sey93, Section
3], involves conditioning unipotent matrices. Let N (n, R) be the multiplicative group of unipotent
n × n-matrices. That is, a matrix A ∈ N (n, R) if aii = 1 and aij = 0 for i > j (i.e., A is upper
triangular and has ones on the main diagonal). Let N (n, Z) be the subgroup of N (n, R) with
integer entries. Because N (n, Z) is a subset of GL(n, Z), we trivially have that L(B) = L(B · U )
for every U ∈ N (n, Z).

10

Let kBk∞ := maxi,j∈[n] |bij | denote the largest magnitude of an entry in B. We follow Seysen [Sey93] and define S ′ (B) = max{kBk∞ , kB −1 k∞ }. We also let

ζ(n) = sup
inf {S ′ (A · U )} .
A∈N (n,R)

U ∈N (n,Z)

Theorem 2.15 ([Sey93, Prop. 5 and Thm. 6]). There exists an algorithm Seysen that takes as
input A ∈ N (n, R) and outputs A · U where U ∈ N (n, Z) and S ′ (A · U ) ≤ nO(log n) in time O(n3 ).
In particular, ζ(n) ≤ nO(log n) .
Let B = QR be a QR-decomposition of B. We may further decompose R as R = DR′ , where
e i k and
dii = kb

if j < i,
 0
′
rij =
1
if j = i,

µji if j > i.
In particular, note that R′ ∈ N (n, R). It is easy to see that η(B) controls kDkkD −1 k. On the other
hand, using the bound on ζ(n), we can always multiply B on the right by U ∈ N (n, Z) to control
the size of kR′ kkR′−1 k. Roughly speaking, these two facts imply Theorem 2.16.

Theorem 2.16 ([Sey93, Theorem 7]). Let B = Seysen(B ′ ) where B ′ is a matrix. Then S(B) ≤
n · η(B ′ ) · ζ(n)2 .
Proof of Theorem 2.3. Let B = Seysen(B ′ ), where B ′ is a basis as computed in Proposition 2.14.
We then have that
S(B) ≤ n · η(B ′ ) · ζ(n)2

(by Theorem 2.16)

≤ n · kO(n/k+log k) · ζ(n)2
≤n·k

O(n/k+log k)

≤ kO(n/k+log k) .

· (n

(by Proposition 2.14)

O(log n) 2

)

(by Theorem 2.15)

We can compute B ′ in 2O(k) time using Proposition 2.14. Moreover, by Theorem 2.15, Seysen
runs in O(n3 ) time. Therefore the algorithm runs in 2O(k) time.

3

Approximating lattice distortion

In this section, we show how to compute low-distortion mappings between lattices by using bases
with low S(B).

3.1

Basis length bounds in terms of S(B)

Call a basis B = [b1 , . . . , bn ] sorted if kb1 k ≤ · · · ≤ kbn k. Clearly, kbi k/λi ≥ 1 for a sorted basis
B. Note that sorting B does not change S(B), since S(·) is invariant under permutations of the
basis vectors.
A natural way to quantify the “shortness” of a lattice basis is to upper bound kbk k/λk for all
√
k ∈ [n]. For example, [LLS90] shows that kbk k/λk ≤ n when B is an HKZ basis. We give a
characterization of Seysen bases showing that in fact both the primal basis vectors and the dual basis
11

vectors are not much longer than the successive minima. Namely, S(B) is an upper bound on both
kbk k/λk and kb∗k k/λ∗n−k+1 for sorted bases B. Although we only use the fact that S(B) ≥ kbk k/λk
we show both bounds. Seysen [Sey93] gave essentially the same characterization, but we state and
prove it here in a slightly different form.
Lemma 3.1 (Theorem 8 in [Sey93]). Let B be a sorted basis of L. Then for all k ∈ [n],
1. kbk k/λk (L) ≤ S(B).
2. kb∗k k/λ∗n−k+1 (L) ≤ S(B).
Proof. For every k ∈ [n] we have
kbk k/λk ≤ kbk kλ∗n−k+1
≤

kbk k max kb∗i k
i∈{k,...,n}

≤

i∈{k,...,n}

(by the lower bound in Theorem 2.1)
(the b∗i are linearly independent)

max kbi kkb∗i k

(B is sorted)

≤ S(B).
This proves Item 1. Furthermore, for every k ∈ [n] we have
kbk kkb∗k k
kb∗k k
≤
≤ maxkbi kkb∗i k = S(B).
λ∗n−k+1
λk λ∗n−k+1
i∈[n]
The first inequality follows from the assumption that B is sorted, and the second follows from the
lower bound in Theorem 2.1. This proves Item 2.

3.2

Approximating LDP using Seysen bases

In this section, we bound the distortion D(L1 , L2 ) between lattices L1 , L2 . The upper bound is
constructive and depends on S(B1 ), S(B2 ), which naturally leads to Theorem 1.4.
Lemma 3.2. Let A = [a1 , . . . , an ] and B = [b1 , . . . , bn ] be sorted bases of L1 , L2 respectively.
Then,
kBA−1 k ≤ nS(A)S(B)M (L1 , L2 ).

12

Proof.
kBA−1 k =
≤
=

n
X

i=1
n
X

bi (a∗i )T
bi (a∗i )T

(by triangle inequality)

i=1
n
X
i=1

kbi kka∗i k

≤ n maxkbi kka∗i k
i∈[n]

≤ nS(B) max λi (L2 )ka∗i k

(by Item 1 in Lemma 3.1)

i∈[n]

≤ nS(A)S(B) max λi (L2 )/kai k

(by definition of S(A))

i∈[n]

≤ nS(A)S(B) max λi (L2 )/λi (L1 )
i∈[n]

(A is sorted)

= nS(A)S(B)M (L1 , L2 ).
Proof of Theorem 1.2. Note that by definition there always exist bases B1 , B2 of L1 , L2 respectively
achieving S(Bi ) = S(Li ). Therefore, applying Lemma 3.2 twice to bound both kB2 B1−1 k and
kB1 B2−1 k, we get the upper bound.
For the lower bound, let v1 , . . . , vn ∈ L1 be linearly independent vectors such that kvi k = λi (L1 )
for every i. Then, for every i,
λi (L2 ) ≤ maxkT vj k ≤ kT k maxkvj k = kT kλi (L1 ).
j∈[i]

j∈[i]

Rearranging, we get that λi (L2 )/λi (L1 ) ≤ kT k. This holds for arbitrary i, so in particular
maxi∈[n] λi (L2 )/λi (L1 ) = M (L1 , L2 ) ≤ kT k. The same computation with L1 , L2 reversed shows
that M (L2 , L1 ) ≤ kT −1 k. Multiplying these bounds together implies the lower bound in the theorem statement.
We can now prove Theorem 1.4.
Proof of Theorem 1.4. Let (L1 , L2 ) be an instance of LDP. For i = 1, 2, compute a basis Bi of
Li using the algorithm described in Theorem 2.3 with parameter k. We have that S(Bi ) ≤
kO(n/k+log k) . This computation takes 2O(k) time. The algorithm then simply outputs T = B2 B1−1 .
By Lemma 3.2 and the upper bounds on S(Bi ), we get that κ(T ) ≤ kO(n/k+log k) · M (L1 , L2 ) ·
M (L2 , L1 ). This is within a factor of kO(n/k+log k) · nO(log n) = kO(n/k+log k) of D(L1 , L2 ) by
Theorem 1.1. So, the algorithm is correct.

4

Hardness of LDP

In this section, we prove the hardness of γ-GapLDP. (See Theorem 4.8.) Our reduction works in
two steps. First, we show how to use an oracle for GapLDP to solve a variant of GapCVP that
13

we call γ-GapCVPα . (See Definition 4.1 and Theorem 4.3.) Given a CVP instance consisting of a
lattice L and a target vector t, our idea is to compare “L with t appended to it” to “L with an
extra orthogonal vector appended to it.” (See Eq. (6).) We show that, if dist(t, L) is small, then
these lattices will be similar. On the other hand, if (1) dist(kt, L) is large for all non-zero integers
k, and (2) λ1 (L) is not too small; then the two lattices must be quite dissimilar.
We next show that γ-GapCVPα is as hard as GapSVP. (See Theorem 4.6.) This reduction is
a variant of the celebrated reduction of [GMSS99]. It differs from the original in that it “works
in base p” instead of in base two, and it “adds an extra coordinate to t.” We show that this is
sufficient to satisfy the promises required by γ-GapCVPα .
Both reductions are relatively straightforward.

4.1

Reduction from a variant of CVP

Definition 4.1. For any γ = γ(n) ≥ 1 and α = α(n) > 0, γ-GapCVPα is the promise problem
defined as follows. The input is a lattice L ⊂ Qn , a target t ∈ Qn , and a distance d > 0. It is a
‘YES’ instance if dist(t, L) ≤ d and a ‘NO’ instance if dist(kt, L) > γd for all non-zero integers k
and d < α · λ1 (L).
We will need the following characterization of the operator norm of a matrix in terms of its
behavior over a lattice. Intuitively, this says that “a lattice has a point in every direction.”
Fact 4.2. For any matrix A ∈ Rn×n and (full-rank) lattice L ⊂ Rn ,
kAk =

kAyk
.
y∈L\{0} kyk
sup

Proof. It suffices to note that, for any x ∈ Rn with kxk = 1 and any full-rank lattice L ⊂ Rn , there
is a sequence y1 , y2 , . . . of vectors yi ∈ L such that
ym
=x.
m→∞ kym k
lim

Indeed, this follows immediately from the fact that the rationals are dense in the reals.
′

Theorem 4.3. For any γ = γ(n) ≥ 1, there is an efficient reduction from γ ′ -GapCVP1/γ to
γ-GapLDP, where γ ′ = O(γ).
Proof. On input L ⊂ Qn with basis (b1 , . . . , bn ), t ∈ Qn , and d > 0, the reduction behaves
as follows. Let L1 := L(b1 , . . . , bn , r · en+1 ) with r > 0 to be set in the analysis. Let L2 :=
L(b1 , . . . , bn , t + r · en+1 ). I.e.,




B t
B 0
.
(6)
L2 = L
L1 = L
0 r
0 r
(Formally, we must embed the bi and t in Qn+1 under the natural embedding, but we ignore this
for simplicity.) The reduction then calls its γ-GapLDP oracle with input L1 , L2 , and c > 0 to be
set in the analysis and outputs its response.
It is clear that the reduction runs in polynomial time. Suppose that dist(t, L) ≤ d. We note that
L2 does not change if we shift t by a lattice vector. So, we may assume without loss of generality
that 0 is a closest lattice vector to t and therefore ktk ≤ d.
14

Let B1 := [b1 , . . . , bn , r·en+1 ] and B2 := [b1 , . . . , bn , t+r·en+1 ] be the bases from the reduction.
It suffices to show that κ(B2 B1−1 ) is small. Indeed, for any y ∈ L1 , we can write y = (y′ , kr) for
some k ∈ Z and y′ ∈ L. Then, we have
kB2 B1−1 yk = k(y′ + kt, kr)k ≤ k(y′ , kr)k + |k|ktk ≤ (1 + d/r)kyk .
Similarly, kB2 B1−1 yk ≥ kyk − |k|ktk ≥ (1 − d/r)kyk. Therefore, by Fact 4.2, κ(B2 B1−1 ) ≤ (1 +
d/r)/(1 − d/r). So, we take c := (1 + d/r)/(1 − d/r), and the oracle will therefore output ‘YES’.
Now, suppose dist(zt, L) > 10γd for all non-zero integers z, and λ1 (L) > 10γd. (I.e., we take
γ ′ = 10γ = O(γ).) Let A be a linear map with AL1 = L2 . Note that A has determinant one, so
n+1 \ {0}. We have that A(0, r) = (y′ , kr) for some y′ ∈ L + kt
that κ(A) ≥ kAxk
kxk for any x ∈ Q
and k ∈ Z. If k 6= 0, then kA(0, r)k ≥ dist(kt, L) > 10γd. So, κ(A) ≥ kA(0, r)k/r > 10γd/r.
If, on the other hand, k = 0, then y′ ∈ L \ {0} and kA(0, r)k = k(y′ , 0)k ≥ λ1 (L) > 10γd, so
that we again have κ(A) ≥ kA(0, r)k/r > 10γd/r. Taking r = 2γd gives κ(A) > γ · c, so that the
oracle will output ‘NO’, as needed.

4.2

Hardness of This Variant of GapCVP

We recall the definition of (the decision version of) γ-GapSVP.
Definition 4.4. For any γ = γ(n) ≥ 1, γ-GapSVP is the promise problem defined as follows: The
input is a lattice L ⊂ Qn , and a distance d > 0. It is a ‘YES’ instance if λ1 (L) ≤ d and a ‘NO’
instance if λ1 (L) > γd.
Haviv and Regev (building on work of Ajtai, Micciancio, and Khot [Ajt98, Mic01, Kho05])
proved the following strong hardness result for γ-GapSVP [HR12].
Theorem 4.5 ([HR12, Theorem 1.1]).
1. γ-GapSVP is NP-hard under randomized polynomial-time reductions for any constant γ ≥ 1.
I.e., there is no randomized polynomial-time algorithm for γ-GapSVP unless NP ⊆ RP.
1−ε

2. 2log n -GapSVP is NP-hard under randomized quasipolynomial-time reductions for any con1−ε
stant ε > 0. I.e., there is no randomized polynomial-time algorithm for 2log n -GapSVP
unless NP ⊆ RTIME(2polylog(n) ).
3. nc/ log log n -GapSVP is NP-hard under randomized subexponential-time reductions for some
universal constant c > 0. I.e., there isTno randomized polynomial-time algorithm for nc/ log log n δ
GapSVP unless NP ⊆ RSUBEXP := δ>0 RTIME(2n ).
In particular, to prove Theorem 1.5, it suffices to reduce γ ′ -GapSVP to γ-CVP1/γ for γ ′ = O(γ).

Theorem 4.6. For any 1 ≤ γ = γ(n) ≤ poly(n), there is an efficient reduction from γ ′ -GapSVP
to γ-GapCVP1/γ , where γ ′ = γ · (1 + o(1)).
Proof. Let p be a prime with 10γn ≤ p ≤ 20γn ≤ poly(n). We take γ ′ = γ · (1 + o(1)) so that
γ=p

γ′
1 − γ ′2 /(p − 1)2
15

.

On input a basis B := [b1 , . . . , bn ] for a lattice L ⊂ Qn , and d > 0, the reduction behaves as
follows. For i = 1, . . . , n, let Li := L(b1 , . . . , pbi , . . . , bn ) be “L with its ith basis vector multiplied
by p.” And, for all i and 1 ≤ j < p, let ti,j := jbi + ren+1 , with r > 0 to be set in√the analysis. For
each i, j, the reduction calls its γ-GapCVP1/γ oracle on input Li , ti,j , and d′ := d2 + r 2 . Finally,
it outputs ‘YES’ if the oracle answered ‘YES’ for any query. Otherwise, it outputs ‘NO’.
It is clear that the algorithm is efficient. Note that
( n
)
X
dist(jbi , Li ) = min
aℓ bℓ : aℓ ∈ Z, ai ≡ j mod p .
ℓ=1

In particular, λ1 (L) = mini,j dist(jbi , Li ).
So, suppose λ1 (L) ≤ d. Then, there must be some i, j such that dist(ti,j , Li )2 ≤ r 2 + λ1 (L)2 ≤
2
r + d2 = d′2 . So, the oracle answers ‘YES’ at least once.
Now, suppose λ1 (L) > γ ′ d. Since Li ⊂ L, we have λ1 (Li ) ≥ λ1 (L) > γ ′ d, and therefore
d < λ1 (Li )/γ ′ < λ1 (Li )/γ, as needed. And, by the above observation, we have dist(jbi , Li ) ≥
λ1 (L) > γ ′ d for all 1 ≤ i ≤ n and 1 ≤ j < p. Furthermore, for any integer 1 ≤ z < p, we have
dist(zjbi , Li ) = dist((zj mod p) · bi , Li ) > γ ′ d, where we have used the fact that p is prime so that
zj 6≡ 0 mod p. It follows that dist(zti,j , Li ) > dist(zjbi , Li ) > γ ′ d. And, for z ≥ p, it is trivially
the case that dist(zti,j , Li ) ≥ zr ≥ pr. Taking r := γ ′ d/(p − 1), we have that in both cases
dist(zti,j , Li ) > γ ′ d = √
So, the oracle will always answer ‘NO’.

γ ′ d′
γ ′ d′
= γd .
=p
1 − r2
1 − γ ′2 /(p − 1)2

Corollary 4.7. For any 1 ≤ γ = γ(n) ≤ poly(n), there is an efficient reduction from γ ′ -GapSVP
to γ-GapLDP, where γ ′ = O(γ).
Proof. Combine Theorems 4.3 and 4.6.
With this, the proof of our main hardness result is immediate.
Theorem 4.8. The three hardness results in Theorem 4.5 hold with GapLDP in place of GapSVP.
Proof. Combine Theorem 4.5 with Corollary 4.7.

5
5.1

Some illustrative examples
Separating distortion from the successive minima

√
We now show that, for every n, there exists a L such that D(L, Zn ) ≥ Ω( n) · M (L, Zn ) · M (Zn , L).
Indeed, it suffices to take any lattice with det(L)1/n ≤ O(n−1/2 ) but λi (L) = Θ(1). (This is true
for almost all lattices in a certain precise sense. See, e.g., [Sie45].)
Lemma 5.1. For any n ≥ 1, there is a lattice L ⊂ Qn such that det(L)1/n ≤ O(n−1/2 ) and
λi (L) = Θ(1) for all i.
Proposition 5.2. For any n ≥ 1, there exists a lattice L ⊂ Qn such that
√
D(L, Zn ) ≥ Ω( n) · M (L, Zn ) · M (Zn , L) .
16

Proof. Let L ⊂ Qn be any lattice as in Lemma 5.1. In particular, M (L, Zn ) · M (Zn , L) = O(1).
However, for any linear map T with T (L) = Zn , we of course have
√
kT k ≥ | det(T )|1/n = det(Zn )1/n / det(L)1/n ≥ Ω( n) .

Q
(To see the first inequality, it suffices to recall that | det(T )| =
σi and kT k = max σi , where
the σi are the singular values of T .) And, T −1 e1 must be a non-zero lattice vector, so kT −1 k ≥
√
kT −1 e1 k ≥ λ1 (L) ≥ Ω(1). Therefore, κ(T ) = kT kkT −1 k ≥ Ω( n), as needed.

5.2

Non-optimality of HKZ bases for distortion

We show an example demonstrating that mappings between lattices built using HKZ bases are nonoptimal in terms of their distortion. Let Bn be the n × n upper-triangular matrix with diagonal
entries equal to 1 and upper triangular off-diagonal entries equal to − 21 . I.e., Bn has entries

 0 if j < i,
bij =
1 if j = i,
 1
− 2 if j > i.

Luk and Tracy [LT08] introduced the family {Bn } as an example of bases that are well-reduced
but poorly conditioned. Indeed it is not hard to show that {Bn } are HKZ bases that nevertheless
have κ(Bn ) = Ω(1.5n ). We use these bases to show the necessity of using Seysen reduction even on
HKZ bases.

Theorem 5.3. For every n ≥ 1, there exists an n × n HKZ basis B such that D(Zn , L(B)) ≤
nO(log n) , but κ(B) ≥ Ω(1.5n ).
Proof. Let B ′ = Bn be an HKZ basis in the family described above, and take In as the basis of Zn .
Then κ(B ′ · In ) = Ω(1.5n ).
On the other hand, let B = Seysen(B ′ ). Then, because η(B ′ ) = 1, S(B) = nO(log n) by
√
Theorem 2.16. Clearly, λi (Zn ) = 1 for all i ∈ [n]. On the other hand, 1 ≤ λi (L(B)) ≤ n
e i k = 1, and the upper bound comes from
for all i ∈ [n]. The lower bound holds because minkb
√
′
the fact that kbi k ≤ n for all i ∈ [n] and the linear independence of the b′i .2 It follows that
√
M (Zn , L(B)) ≤ n and M (L(B), Zn ) ≤ 1. Applying Lemma 3.2 to B and B −1 , we then get that
κ(B · In ) ≤ nO(log n) .

References
[AFK02]

Sanjeev Arora, Alan Frieze, and Haim Kaplan. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. Mathematical
Programming, 2002.

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

2

In fact, λn (L(B)) = O(1).

17

[AKKV12] Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Yadu Vasudev. Approximate Graph Isomorphism. In Mathematical Foundations of Computer Science, 2012.
[AKS01]

Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the Shortest Lattice
Vector Problem. In STOC, pages 601–610, 2001.

[Bab16]

L.
Babai.
Graph
Isomorphism
http://arxiv.org/abs/1512.03547.

[Ban93]

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

[BV14]

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

[CS98]

J. Conway and N.J.A. Sloane. Sphere Packings, Lattices and Groups. Springer New
York, 1998.

[Gen09]

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

in

quasipolynomial

time,

2016.

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

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

[HR14]

Ishay Haviv and Oded Regev. On the Lattice Isomorphism Problem. In SODA, 2014.

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

[KZ73]

A. Korkine and G. Zolotareff. Sur les formes quadratiques. Mathematische Annalen,
6(3):366–389, 1873.

[LLL82]

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

[LLS90]

J. C. Lagarias, Hendrik W. Lenstra Jr., and Claus-Peter Schnorr. Korkin-Zolotarev
bases and successive minima of a lattice and its reciprocal lattice. Combinatorica,
10(4):333–348, 1990.
18

[LS14]

Hendrik W. Lenstra Jr. and Alice Silverberg.
http://arxiv.org/abs/1501.00178.

[LT08]

Franklin T. Luk and Daniel M. Tracy. An improved lll algorithm. Linear Algebra and
its Applications, 428(2):441 – 452, 2008.

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

[Min10]

H. Minkowski. Geometrie der Zahlen. Number v. 1 in Geometrie der Zahlen. B.G.
Teubner, 1910.

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

[MV13]

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

[PS97]

W. Plesken and B. Souvignier. Computing isometries of lattices. J. Symbolic Comput.,
24(3-4):327–334, 1997. Computational algebra and number theory (London, 1993).

[Reg09]

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

[Sch87]

C.P. Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science, 1987.

[Sey93]

Martin Seysen. Simultaneous reduction of a lattice basis and its reciprocal basis. Combinatorica, 13(3):363–376, 1993.

[Sie45]

Carl Ludwig Siegel. A mean value theorem in geometry of numbers. Annals of Mathematics, 46(2):pp. 340–347, 1945.

[SSV09]

Mathieu Dutour Sikiric, Achill Schürmann, and Frank Vallentin. Complexity and algorithms for computing Voronoi cells of lattices. Math. Comput., 78(267):1713–1731,
2009.

19

Lattices with symmetry, 2014.

