1

Boosted KZ and LLL Algorithms

arXiv:1703.03303v4 [] 10 Oct 2017

Shanxiang Lyu and Cong Ling, Member, IEEE

Abstract—There exist two issues among popular lattice reduction (LR) algorithms that should cause our concern. The first one
is Korkine-Zolotarev (KZ) and Lenstra–Lenstra–Lovász (LLL)
algorithms may increase the lengths of basis vectors. The other is
KZ reduction suffers much worse performance than Minkowski
reduction in terms of providing short basis vectors, despite its
superior theoretical upper bounds. To address these limitations,
we improve the size reduction steps in KZ and LLL to set up two
new efficient algorithms, referred to as boosted KZ and LLL,
for solving the shortest basis problem (SBP) with exponential
and polynomial complexity, respectively. Both of them offer
better actual performance than their classic counterparts, and
the performance bounds for KZ are also improved. We apply
them to designing integer-forcing (IF) linear receivers for multiinput multi-output (MIMO) communications. Our simulations
confirm their rate and complexity advantages.
Index Terms—lattice reduction, KZ, LLL, shortest basis problem, integer-forcing

I. I NTRODUCTION

L

ATTICE reduction (LR) is a process that, given a
lattice basis as input, to ascertain another basis with
short and nearly orthogonal vectors [1]. Their applications
in signal processing include global positioning system (GPS)
[2], color space estimation in JPEG images [3], and data detection/precoding in wireless communications [4], [5]. Recent
advances in LR algorithms are mostly made in wireless communications and cryptography [6], [7]. Popular LR algorithms
with exponential complexity include Korkine-Zolotarev (KZ)
[8], [9] and Minkowski reductions [10], which have set the
benchmarks for the best possible performance in LR aided
successive interference cancellation (SIC) and zero-forcing
(ZF) detectors for multi-input multi-output (MIMO) systems
[10]. In MIMO detection problems, KZ and Minkowski reductions are preferable when the channel coefficients stay
fixed for a long time frame so that their high complexity
can be shared across time. In the part of polynomial or fixed
complexity algorithms, the celebrated Lenstra–Lenstra–Lovász
(LLL) [11] algorithm has been well studied and many new
variants have been proposed. Typical variants of LLL in
wireless communications can be summarized into two types:
either sacrificing the execution of full size reductions [12],
[13], or controlling the implementation order of swaps and size
reductions [14], [15], [16], [17]. The reason to establish the
first type variants is that a full size reduction has little influence
on the performance of LR aided SIC detectors. Variants of the
second type, e.g., fixed complexity LLL [14], [15] and greedy
LLL [16], [17], serve the purpose of enhancing the system
This work was supported in part by the Royal Society and in part by the
China Scholarship Council.
S. Lyu and C. Ling are with the Department of Electrical and Electronic
Engineering, Imperial College London, London SW7 2AZ, United Kingdom
(e-mail: s.lyu14@imperial.ac.uk, cling@ieee.org).

performance especially when the number of LLL iterations
is restrained. It is also noteworthy to introduce the block KZ
(BKZ) reduction [18] as a tradeoff between KZ and LLL. BKZ
is scarcely probed in MIMO but more often in cryptography.
Many records in the shortest vector problem (SVP) challenge
hall of fame [19] are set by using BKZ although no good
upper bound on the complexity of BKZ is known.
In this work, we point out two issues among popular LR
algorithms which were rarely investigated before. The first one
is that KZ and LLL may elongate basis vectors. This issue
was discovered when we applied LLL to Gaussian random
matrices of dimensions higher than 40. The second one is
KZ reduction practically suffers much worse performance than
Minkowski reduction in terms of providing short basis vectors,
while Nguyen and Stehle conjectured in [20, P. 46:7] that KZ
may be stronger than Minkowski in high dimensions because
theoretically all vectors of a KZ reduced basis are known
to be closer to the successive minima than Minkowski’s.
So engineers may be quite confused about the discrepancies
between theory and practice.
The contributions of this work are twofold. First, we propose
improved algorithms to address the above limitations of KZ
and LLL, and they are in essence suitable for any application
that needs to solve the shortest basis problem (SBP). Second,
we show that our algorithms can be applied to the design
of integer forcing (IF) linear MIMO receivers [21] to obtain
some gains in rates.
The first algorithm is referred to as boosted KZ. It harnesses
the strongest length reduction every time after the shortest
vector in a projected lattice basis has been found, and such
an operation is proved to be valid. We improve analysis on
the best known bounds for the lengths of basis vectors and
Gram-Schmidt vectors via boosted KZ. After choosing sphere
decoding as subroutines, the total complexity of boosted KZ
is shown to be closed to that of conventional KZ.
In the second algorithm called boosted LLL, it also dumps
conventional size reduction conditions in LR while deploying a
flexible effort to perform length reduction. In order to maintain
the Siegel condition [22], two criteria for doing length reductions before/after testing the necessity of swaps are proposed,
which guarantee the basis potential is decreasing after swaps
and the lengths of vectors shrink at the largest extent. With
our scheme, bounds on basis lengths and orthogonal defects
can also be obtained. An optimal principle of choosing Lovász
constants is proposed as well. The complexity of this algorithm
is of O(Ln4+c ln n) if the condition number of the input basis
is of O(ln n), where L is the number of routes in boosted LLL
and c > 1 is a constant.
IF is a new MIMO receiver architecture that attempts to
decode an integer combination of lattice codes [21]. It can
be thought of as a special case of compute and forward

2

[23] because this design has full cooperation among receive
antennas. We apply our algorithms to IF because it represents
the kind of applications that need to find multiple short lattice
vectors, as opposed to LR aided SIC receivers [24], lattice
Gaussian samplers [25], and those searching the shortest or
closest vectors [26], [27]. This receiver is more general than
LR aided minimum mean square error (MMSE) receiver in that
it allows concise evaluation on rates, owning to lattice coding
and dithering. In [21], the performance of IF receiver is shown
to outperform conventional ZF and MMSE receivers, and the
optimality in diversity-multiplexing gain tradeoff (DMT) is
also proved. We will elaborate on the IF architecture and
the SBP interface where boosted KZ and LLL turn out to
be beneficial. Simulations will verify the advantages of our
algorithms in terms of rates and complexity.
The rest of this paper is organized as follows. Backgrounds
about lattices and lattice reduction algorithms are reviewed
in Section II. After that, we provide a motivating example to
indicate the drawback of KZ and LLL. The boosted KZ and
LLL algorithms are subsequently constructed and analyzed
in Sections III and IV, respectively. After introducing the
IF framework, exemplary simulation results are then shown
in Section V to emphasize that the proposed algorithms can
deliver higher rates. We mention some open questions Section
VI.
Notation: Matrices and column vectors are denoted by
uppercase and lowercase boldface letters. For a matrix D,
Di:j,i:j denotes the submatrix of D formed by rows and
columns i, i+1, . . . , j. When referring to the (i, j)th element
of D, we simply write di,j . In and 0n denote the n×n identity
matrix and n × 1 zero vector, and the operation (·)⊤ denotes
transposition. For an index set Γi = {1, . . . , i − 1}, DΓi
denotes the columns of D indexed by Γi . span(DΓi ) denotes
the vector space spanned by vectors in DΓi . πDΓi (x) and
⊥
πD
(x) denote the projection of x onto span(DΓi ) and the
Γi
orthogonal complement of span(DΓi ). ⌊x⌉ denotes rounding
x to the nearest integer, |x| denotes getting the absolute value
of x, and kxk denote the Euclidean norm of vector x. The
set of all n × n matrices with determinant ±1 and integer
coefficients will be denoted by GLn (Z).
II. P RELIMINARIES
A. Lattices
A full rank n-dimensional lattice L is a discrete additive
subgroup in Rn . The lattice generated by a basis D =
[d1 , . . . , dn ] ∈ Rn×n can be written as




X
c i di ; c i ∈ Z ;
L(D) = v | v =


i∈[n]

its dual lattice L(D̃) has a basis D̃ = D−⊤ . If the lattice basis
is clear from the context, we omit D and simply write L.

Definition 1. SBP is, given a lattice basis D0 of rank n, find
min

D, L(D)=L(D0 )

l(D)

where l(D) = maxi kdi k, D ranges over all possible bases
of L(D0 ), and l(D) is referred to as basis length.

The Gram-Schmidt orthogonalization (GSO) vectors of a
⊥
basis D can be found by: d∗1 = d1 , d∗i = πD
(di ) =
Γi
Pi−1
∗
µ
d
,
for
i
=
2,
.
.
.
,
n,
where
µ
=
di −
i,j
j=1 i,j j
∗
∗ 2
hdi , dj i/ dj . In matrix notations, GSO vectors can be
written as D = [d∗1 , . . . , d∗n ][µi,j ]⊤ , where [µi,j ] is a lowertriangular matrix with unit diagonal elements. In relation to the
QR decomposition, let Λ be a diagonal matrix with diagonal
entries kd∗1 k , . . . , kd∗n k, then we have [d∗1 , . . . , d∗n ]Λ−1 = Q
and Λ[µi,j ]⊤ = R whose diagonal elements reflect the lengths
of GSO vectors.
The ith successive minimum of an n dimensional lattice
L(D) is the smallest real number r such that L contains i
linearly independent vectors of length at most r:
λi = inf {r | dim(span((L ∩ B(0, r))) ≥ i} ,
in which B(t, r) denotes a ball centered at t with radius r.
We also write λi as λi (D) to distinguish different lattices.
Hermite’s constant γn is defined by
γn =

λ1 (D)2
.
|det(D)|2/n

sup
D∈Rn×n

Exact values for γn are known for n ≤ 8 and n = 24.
With Minkowski’s convex body theorem, we can obtain
γn ≤ π4 Γ(1 + n/2)2/n , which yields γn ≤ 2n
3 for n ≥ 2
[28]. It also follows from the work of Blichfeldt [29] that
n
.
γn ≤ π2 Γ(2 + n/2)2/n , whose asymptotic value is πe
The open Voronoi cell of lattice L with center v is the set
Vv (D) = {x ∈ Rn | kx − vk < kx − v − v′ k , ∀v′ ∈ L} ,

in which the outer radius of the Voronoi cell centered at
the origin is denoted as “covering radius”, i.e., ρ(D) =
maxt∈span(L) dist(t, L).
The orthogonality defect (OD), ξ(D), can alternatively
quantify the goodness of a basis:
Qn
kdi k
ξ(D) = p i=1
.
(1)
det(D⊤ D)

It has a lower bound ξ(D) ≥ 1 in accordance with Hadamard’s
inequality.
B. Lattice reduction algorithms
In this subsection, we review three popular LR metrics where the lengths of basis vectors can be upper
bounded by scaled versions of the successive minima. Operations/transforms to reach these metrics are referred to as
the corresponding algorithms. Let R be the R matrix of a QR
decomposition on D, with elements ri,j ’s.

Definition 2. A basis D is called LLL reduced if the following
two conditions hold [11]:
1. |ri,j /ri,i | ≤ 21 , 1 ≤ i ≤ n, j > i. (Size reduction
conditions)
2

⊥
2. δ πD
(di )
≤
Γi
(Lovász conditions)

⊥
πD
(di+1 )
Γ
i

2

, 1 ≤ i ≤ n − 1.

In the definition, δ ∈ (1/4, 1] is called the Lovász constant.
If D is LLL reduced, it has [11]
kdi k ≤

β n−1 λi (D), 1 ≤ i ≤ n,

(2)

3

p
√
in which β = 1/ δ − 1/4 ∈ (2/ 3, ∞).

Definition 3. A basis D is called KZ reduced if it satisfies the
⊥
size reduction conditions, and πD
(di ) is the shortest vector
Γi
⊥
of the projected lattice πDΓ ([di , . . . , dn ]) for 1 ≤ i ≤ n [28].
i
(Projection conditions)
For a KZ reduced basis, it satisfies [28]
√
i+3
kdi k ≤
λi (D), 1 ≤ i ≤ n.
(3)
2
Definition 4. A lattice basis D is called Minkowski reduced
if for any integers c1 , ..., cn such that ci , ..., cn are altogether
coprime, it has kd1 c1 + · · · + dn cn k ≥ kdi k for 1 ≤ i ≤ n
[10].
For a Minkowski reduced basis, it satisfies [10]
o
n
kdi k ≤ max 1, (5/4)(i−4)/2 λi (D), 1 ≤ i ≤ n.

(4)

When n ≤ 4, Minkowski reduction is optimal as it reaches
all the successive minima. Its bounds on lengths are however
exponential for n > 4.
III. B OOSTED KZ
In this section, we propose to improve KZ by abandoning
its size reduction conditions, as well as employing the exact
closest vector problem (CVP) oracles to reduce di with
L(DΓi ) after the projection condition has been met at each
time i. Better theoretical results can be obtained via boosted
KZ, and the implication is using CVP for LR can be better than
solely relying on SVP. This should not be a surprise because
CVP is generally believed to be harder than SVP [1].
A. Replacing size reduction with CVP
We first show that imposing size reduction conditions in KZ
and LLL may lengthen basis vectors, and thus enlarging OD’s.
Proposition 1. There always exist real value bases of rank
n, n ≥ 3, such that KZ and LLL algorithms lengthen basis
vectors. 1
Proof: We prove this by constructing examples in dimension n = 3 because bases of higher ranks can be built by
concatenating another identity matrix in the diagonal direction.
Consider the following matrix


1 c1 0
R =  0 1 c2  ,
(5)
0 0 1

where |c1 | < 1/2, |c2 | > 1/2. Since |r1,2 /r1,1 | < 1/2 and
|r2,3 /r2,2 | > 1/2, it follows from the definition of KZ or LLL
that r1 and r2 will remain unchanged, while size reducing r3
by r2 yields a new vector r′3 = [−c1 ⌊c2 ⌉, c2 − ⌊c2 ⌉, 1]⊤ . If
⌊c2 ⌉ = ±1, then r′3 cannot be further reduced by r1 . So we
2
2
can assume kr′3 k > kr3 k and
 solve this inequality about
c2 , which yields |c2 | < 1 + c21 /2. Therefore, there exist at
least matrices
like (5) with |c1 | < 1/2 and 1/2 < |c2 | <

1 + c21 /2 such that KZ/LLL lengthens basis vectors.
1 This

proposition is inspired by [20, Lem. 2.2.3].

To avoid such problems in KZ, we shall review the process
of the KZ reduction algorithm [10]. In the beginning, the
projection conditions are met by finding the shortest lattice
vectors of the projected lattices and carrying them to the
lattice basis. The size reduction conditions are subsequently
addressed by using Babai points v’s in L(DΓi ) to reduce di
by di ← di − v for all i. Concerning the above procedure,
what we try to ameliorate are the size reduction operations.
The “di ← di − v” step is redefined as length reduction, in
which the optimal update needs to solve a CVP.
Definition 5. CVP is a problem that, given a vector y ∈ Rn
and a lattice basis D of rank n, find a vector v ∈ L(D) such
2
2
that ky − vk ≤ ky − wk , ∀ w ∈ L(D).
An algorithm solving CVP, which quantizes any input to a
lattice point, is denoted as v = QL(D) (y). It is evident that
QL(DΓi ) (πDΓi (di )) = QL(DΓi ) (di ) . To obtain explicit properties from the length reductions, we first establish Proposition
2 to show
di − QL(DΓi ) (πDΓi (di )) < kdi k
if QL(DΓi ) (πDΓi (di )) 6= 0 for all i. The proof is given in
Appendix A.
Proposition 2. If πDΓi (di ) lies outside the Voronoi region
V0 (DΓi ), i.e., v , QL(DΓi ) (πDΓi (di )) 6= 0, then we can
replace di with di − v because kdi − vk < kdi k.
Together with the case of QL(DΓi ) (πDΓi (di )) = 0, we
conclude that
di − QL(DΓi ) (πDΓi (di )) ≤ kdi k

(6)

for all i, which means, during the length reductions, all
solutions provided by CVP can be treated as effective updates.
We call them effective because each di is the shortest vector
that can be extended to a basis for L([DΓi , di ]), and the length
reductions never increase the lengths of di ’s.
After executing these length reduction operations as di ←
di − QL(DΓi ) (πDΓi (di )), all πDΓi (di )’s must lie inside the
Voronoi regions V0 (DΓi )’s, so that
2

⊥
kdi k ≤ πD
(di )
Γi

2

+ ρ(DΓi )2

(7)

for all i, where ρ(DΓi ) is the covering radius of L(DΓi ).
B. Algorithm description
The concrete steps of boosted KZ are presented in Algorithm 1. This algorithm can be briefly explained as follows. In
line 4, the Schnorr and Euchner (SE) enumeration algorithm
[18] is applied to solve SVP over L(Ri:n,i:n ), in that if Ri:n,i
⊥
is the shortest vector of L(Ri:n,i:n ), then πD
(di ) is the
Γi
⊥
shortest vector of the projected lattice πDΓ ([di , . . . , dn ]).
i
Lines 5 to 7 are designed to plug new vectors found into the
lattice basis, and the basis expansion method in [10] can do
this efficiently. Other basis expansion methods include using
LLL reduction [30] or employing the Hermite normal form
of the coefficient matrix [1, Lem. 7.1], but both of them have
higher complexity than the one in [10]. Lines 8 to 10 restore

4

the upper triangular property of R, and these be alternatively
implemented by performing another QR decomposition. Line
11 is the unique new design of boosted KZ, i.e., to reduce
R1:n,i by using its closest vector in L(R1:n,1:i−1 ).2

A direct application of the above proposition also shows a
boosted KZ reduced basis has length
√
n+2
l(D) ≤
λn (D).
(10)
2

Algorithm 1: The boosted KZ algorithm.
Input: original lattice basis D ∈ Rn×n , Lovász constant
δ.
Output: reduced basis D, unimodular matrix T
1 [Q, R] = qr(D);
⊲ The QR decomposition of D;
2 T = I;
3 for i = 1 : n do
4
find the shortest vector Ri:n,i:n c1 in L(Ri:n,i:n ) by
LLL aided SE enumeration; ⊲ SVP subroutine;
5
construct a (n − i + 1) × (n − i + 1) unimodular
matrix U whose first column is c1 ;
6
R1:n,i:n ← R1:n,i:n U;
7
T1:n,i:n ← T1:n,i:n U;
8
define G as a unitary matrix that can restore the
upper triangular property of R;
9
R ← GR;
10
Q ← QG⊤ ;
11
find the closest vector R1:n,1:i−1 c2 in L(R1:n,1:i−1 )
to R1:n,i with SE enumeration; ⊲ CVP subroutine;
12
R1:n,i ← R1:n,i − R1:n,1:i−1 c2 ;
13
T1:n,i ← T1:n,i − T1:n,1:i−1 c2 ;

Remark 1. Our results of (8), (9) and (10) are better than
those of KZ and Minkowski reductions. If we assume all
the successive minima are available, then there exists a
polynomial time√transformation that generates a basis with
l(D) ≤ max {1, n/2} λn (D) [1, Lem. 7.1].

14

D ← QR.

Proposition 4. Suppose a basis D is boosted KZ reduced,
then this basis satisfies
λ1 (D)2 ≤

8i
2
(i − 1)ln(i−1)/2 ri,i
,
9



2i
2
2
kdi k ≤ 1 + (i − 1)1+ln(i−1)/2 ri,i
9

(11)

(12)

for 1 ≤ i ≤ n.

C. Properties of boosted KZ
Based on Algorithm 1, a lattice basis D is called boosted
⊥
KZ reduced if πD
(di ) is the shortest vector of the projected
Γi
⊥
lattice πDΓ ([di , . . . , dn ]), and πDΓi (di ) ∈ V0 (DΓi ) for all
i
i.
In boosted KZ, all length reductions are the strongest, and
they can help us to deliver better bounds for the lengths of
basis vectors, as given in Proposition 3. The
is given
n proof
√ o
n
in Appendix B. We have kdn k ≤ max 1, 2 λn (D),
√

outperforming the kdn k ≤ n+3
2 λn (D) bound in [28, Thm.
2.1] which was conjectured not tight in their work.
Proposition 3. Suppose a basis D is boosted KZ reduced,
then this basis satisfies
)
( √ )
(√
i+3
i
λi (DΓi+1 )
λi (D), max 1,
kdi k ≤ min
2
2
(8)
for 1 ≤ i < n, and
 √ 
n
kdn k ≤ max 1,
λn (D).
(9)
2
2 Since

The lengths of GSO vectors in this new algorithm remains
the same as those of KZ reduction, so readily we can claim that
2
2
λ1 (D)2 ≤ i1+ln(i) ri,i
and kdi k2 ≤ i2+ln(i) ri,i
as given in [28,
Prop. 4.2], where ri,i denotes the (i, i)th entry of the R matrix
of a QR decomposition on D. As another contribution, now
we show these two bounds can be improved in Proposition 4,
whose proof is given in Appendix C.

we only modify the size reduction steps in KZ, one may employ
any improved KZ implementation, e.g., [9], to make the boosted KZ faster.
We adhere to the current version for making a fair complexity comparison
with Minkowski’s reduction which employs similar subroutines [10].

The relaxed versions of (11) and (12) can be read as
2
2
2
λ1 (D)2 ≤ i1+ln(i)/2 ri,i
and kdi k ≤ i2+ln(i)/2 ri,i
. Proposition 4 can be either applied to bound the complexity of boosted
KZ, or to achieve the best explicit bounds for the proximity
factors of lattice reduction aided decoding, i.e., updating Eqs.
(41) and (45) of [24]. Moreover, (12) leads to an alternative
bound for OD,
ξ(D) ≤

n
Y

i=1

i1+ln(i)/4 ≤ nn+ln(n!)/4 .

A better bound on ξ(D) comes after applying Minkowski’s
second theorem [31, P. 202] to (8) and (9),
√
n
ξ(D) ≤
2

n−1
Y
i=1

! 
√
n/2
2
i+3
n
.
2
3

(13)

Remark 2. The properties of |ri,j /ri,i | ≤ 12 for 1 ≤ i ≤ n,
j > i, are no longer guaranteed in boosted KZ. Of independent
interests, we have another attribute in Proposition 5 that each
pair (d1 , di ) of the boosted KZ reduced basis is Lagrange
reduced [7, P. 41] for all i, which may not hold in the
conventional KZ. The proof can be found in Appendix D.
Proposition 5. Suppose a basis D is boosted KZ reduced, then
this basis satisfies |r1,i /r1,1 | ≤ 12 , and kd1 k, kdi k reaches the
first and second successive minima of L([d1 , di ]) for 2 ≤ i ≤
n.

5

D. Implementation and complexity
The complexity of boosted KZ is dominated by its SVP
and CVP subroutines, in which the SE enumeration algorithm
[18] will be adopted for our implementations and complexity
analysis. The total complexity is assessed by counting the
number of floating-point operations (flops).
1) Complexity of CVP subroutines: It suffices to discuss the
complexity of the most time-consuming nth round of reducing
R1:n,n , which represents an n − 1 dimensional CVP problem.
First of all, the complexity of SE is directly proportional to
the number of nodes in the search tree. In the kth layer of the
enumeration, the number of nodes is
n
Nk (s) = |xk:n−1 | | xk:n−1 ∈ Zn−k ,
o
kRk:n−1,n − Rk:n−1,k:n−1 xk:n−1 k2 ≤ s2

where s refers to the radius of a specified sphere and R1:n−1,n
is the projection of R1:n,n onto span(R1:n−1,1:n−1 ). From
Vn−k (1)sn−k
[32], Nk (s) can be estimated by Nk (s) ≈ |rk,k
|···|rn−1,n−1 |
n/2 1
π n/2
√
∼ 2eπ
where Vn (1) = Γ(1+n/2)
stands
for the
n
πn
volume of an n dimensional unit ball. Since limn→∞ Vn (1) =
0, we can cancel this term in the asymptotic analysis. By
summing the nodes from layer 1 to n − 1, the total number of
nodes in the n − 1 dimensional CVP can be given as
NCVP,n−1 (s) =

n−1
X
k=1

Vn−k (1)sn−k
.
|rk,k | · · · |rn−1,n−1 |

≤

n−1
X
k=1

n−1
X

Vn−k (1)s

Qn−1
j=k

j 1/2+ln(j)/4 (2k + 7)

λ1 (D)n−k

, (14)

in which Proposition 4 has been used to get the inequality.
Then we present a general strategy to choose s. It starts
from s = |r1,1 |/2 which equals to the packing
radius because
qP
k
1
2
λ1 (R1:n,1:k−1 ) = |r1,1 |, and improves s to 2
j=1 rj,j with
k = 2, . . . , n−1 gradually until at least one node can be found
inside the searching sphere. For a random basis, one may
expect s = |r1,1 |/2 to work well with high probability,
qP though
n−1 2
1
we can also use the worst case criterion of s = 2
j=1 rj,j
(i.e., larger
than the covering radius). In the worst case, let
√
n−1λn (D)
C1 = 2λ1 (D) . Since Vn (1)(2n+7) also vanishes for large
n, then (14) can be written as
FCVP,n−1 (C1 λ1 (D)) ≤ nC1n nn/2+ln(n!)/4

k=1

λ1 (D)n−k+1

. (16)

A practical principle for choosing s is to set s = kR1:n,1 k,
which is no smaller than λ1 (D). It follows from an LLL
reduced basis property of kR1:n,1 k ≤ β n−1 λ1 (D) that (16)
becomes
FSVP,n (β n−1 λ1 (D)) ≤ nβ n(n−1) β n(n−1)/2 = nβ 3n(n−1)/2 .
(17)
3) Total complexity in flops: The complexity of other operations in Algorithm 1 can be counted as well. In the ith round,
Lines 5 to 10 being implemented by the method described in
[10, Fig. 3] costs O(n(n−i)). The total complexity of boosted
KZ is therefore upper bounded as

FboostKZ ≤ (n−1) FCVP,n−1 (C1 λ1 (D))+FSVP,n (β n−1 λ1 (D))
 4
+ O(n2 − n) + n3 + (2n − 1)n2 . (18)
3
By plugging (15) and (17) inside (18), we can explicitly obtain
2

Nk (s)(2k + 7)

k=1
n−k

FSVP,n (s) ≤
n
X
Vn−k+1 (1)sn−k+1 β (n+k−2)(n−k+1)/2 (2k + 7)

2

FboostKZ ≤ C1n nn/2+ln(n!)/4+O(ln n) + β 3n(n−1)/2+O(ln n) .

For the visit of each node, the operations of updating the
residual and outer radius etc. cost around 2k + 7 flops in layer
k, so the complexity of the n − 1 dimensional CVP problem,
FCVP,n−1 (s), can be accessed:

FCVP,n−1 (s) =

β (n+k−2)(n−k+1)/2 /λ1 (D)n−k+1 , so the number of flops
spent by the first round SVP subroutine can be similarly
bounded as

(15)

2) Complexity of SVP subroutines: Among the SVP subroutines of boosted KZ, its first round of finding λ1 (D) is
the most difficult one. By invoking the SiegelQcondition of
n
|ri−1,i−1 | ≤ β|ri,i | due to LLL [22], we have 1/ j=k |rj,j | ≤

A few comments are made regarding the above analysis.
Firstly, it provides a worst case analysis for strong lattice
reductions like KZ and boosted KZ, which is broad enough
to include many applications. A byproduct of our analysis is
that we can replace the term FCVP,n−1 (C1 λ1 (D)) in (18)
with O(n3 ) to get the worst case complexity of KZ, i.e.,
2
FKZ ≤ β 3n(n−1)/2+O(ln n) . This compensates the expected
complexity analysis in [10, Sec. III.C] which hinges on
Gaussian lattice bases. Secondly, we can observe from (18)
that how much harder the boosted KZ has become by using
CVP. If
√ λ1 (D) is of the same order as λn (D), we can put
into (18) to conclude that boosted KZ is not much
C1 ≈ n−1
2
more complicated than KZ. Actually, if the lattices are random
(see [33, Sec. 2] for more details about random lattices), then
the Gaussian heuristic implies λ1 (D) ≈ · · · ≈ λn (D) [34]. In
the application to IF, our claim that boosted KZ is not much
harder than KZ will be supported by simulations in Section V.
IV. B OOSTED LLL
In the same spirit of extending size reductions to length
reductions, we will revamp LLL towards better performance
in this section. In a nutshell, the boosted LLL algorithm implements its length reduction via the parallel nearest plane (PNP)
algorithm [35, Sec. 4] and rejection. PNP can be regarded as
a compromise between Babai’s nearest plane algorithm and
the CVP oracle. If PNP has a route number L = 1, then
it becomes equivalent to Babai’s algorithm, while setting L
infinitely large solves CVP. The complexity of boosted LLL
is about L times as large as the that of LLL. In our algorithm,
setting L = 1 means only imposing a rejection operation.

6

A. Replacing size reduction with PNP and rejection
First of all, the classic LLL algorithm consists of two
sequential phases, i.e., size reductions by using Babai points,
and swaps based on testing the Lovász conditions. To reduce
di with DΓi , the sharpest reduction should utilize the closest
vector of πDΓi (di ) in L(DΓi ) as shown in Proposition 2. In
order to devote flexible efforts to these length reductions, we
shall investigate the success probability of a Babai point being
optimum. Generally, assume πDΓi (di ) is uniformly distributed
over L(DΓi ), then the probability of a Babai point being the
closest vector is
R

I(x ∈ P(D∗Γi ))dx

|V0 (DΓi ) ∩ P(D∗Γi )|
,
|V0 (DΓi )|
|V0 (DΓi )|
o(19)
nP
i−1
∗
∗
is
in which P(DΓi ) =
k=1 ck dk | − 1/2 ≤ ck ≤ 1/2
 ∗
∗
the parallelepiped of GSO vectors d1 , . . . , di−1 , and I(·)
denotes an indicator function. One evident observation from
Eq. (19) is, by updating d∗1 ← p1 d∗1 , . . . , d∗i−1 ← pi−1 d∗i−1 ,
the probability in Eq. (19) rises if we choose some constants
p1 > 1, . . . , pi−1 > 1. Another implication from Eq. (19) is, if
πDΓi (di ) belongs to both the external of P(D∗Γi ) and internal
of V0 (DΓi ), then a Babai point should be rejected; otherwise
it elongates di . An example of i = 3 is shown in Fig. 1.
x∈V0 (DΓi )

=

total number of routes it consists of, and (pi−1 , . . . , p1 ) ∈
(Z+ )i−1 . Then each route of PNP can be marked by a label
(qi−1 , . . . , q1 ) where (qi−1 , . . . , q1 ) ∈ {1, . . . , pi−1 } × · · · ×
{1, . . . , p1 }. From layer i−1 of each route, let ci−1,(qi−1 ,...,q1 )
be the qi−1 th closest integer to ⌊ri−1,i /ri−1,i−1 ⌉, and
ri,(qi−1 ,...,q1 ) = ri , we set ri,(qi−1 ,...,q1 ) ← ri,(qi−1 ,...,q1 ) −
ci−1,(qi−1 ,...,q1 ) ri−1 and repeat this process down to
layer 1, resulting in L pairs of coefficient vectors
c(qi−1 ,...,q1 ) = [−c1,(qi−1 ,...,q1 ) , . . . , −ci−1,(qi−1 ,...,q1 ) , 1] and
residuals ri,(qi−1 ,...,q1 ) = RΓi+1 c(qi−1 ,...,q1 ) . We also mark the
old ri by ri,(0,··· ,0) = ri , and c(0,··· ,0) = [0, . . . , 0, 1]. At this
stage, it can choose the shortest vector among all the L + 1
∗
candidates as the reduced version of ri , i.e., ri = ri,(zi−1
,...,z1∗ )
where

∗
(zi−1
, ..., z1∗ ) = arg min
ri,(zi−1 ,...,z1 ) .
(20)
(zi−1 ,...,z1 )

If one also intends to export the unimodular transformation
matrix T, then it can be simultaneously updated inside PNP,
∗
∗
which means ti,(zi−1
,...,z1∗ ) , T1:n,1:i =
,...,z1∗ ) = TΓi+1 c(zi−1
∗
∗
ti,(zi−1
.
,...,z1 )
Since |rk,i /rk,k | < 1/2 for k < i is no longer guaranteed,
together with the Lovász condition they may destroy the Siegel
2
2
for 2 ≤ i ≤ n with some
condition [22] ri−1,i−1
≤ ( 43 + ε)ri,i
small ε > 0. For this reason, we should relax the Lovász
condition to the diagonal reduction (DR) condition [13].
Definition 6 (DR condition [13]). An upper triangular lattice
basis R satisfies the DR condition with parameter δ (1/2 <
δ < 1) if it has
2
2
δri−1,i−1
≤ ri,i
+ (ri−1,i − ⌊ri−1,i /ri−1,i−1 ⌉ri−1,i−1 )2 (21)

for all 2 ≤ i ≤ n, where δ is still referred to as the Lovász
constant.
If (21) holds, the Siegel condition must be true, so we let
i ← i + 1 and safely go to the next iteration. However, if (21)
fails, one should also investigate whether a swap can tweak
such cases. Consider the sublattice L(RΓi+1 ) generated by the
first i vectors and define the potential of basis R [11] as
n
n
Y
Y
2(n−i+1)
.
(22)
ri,i
det(L(RΓi+1 ))2 =
Pot(R) =
i=1

i=1

Fig. 1. The rejected region (orange dots) of the possible projections
πDΓ (d3 ) in L(DΓ3 ) with respect to V0 (DΓ3 ) (red hexagon) and
3
P(d∗1 , d∗2 ) (black rectangle), where the size reduction of LLL elongates d3 .
The four blue triangles are the region whose Babai point is the origin and
size reductions cannot alter a suboptimal d3 .

With the above demonstrations, we propose to amplify the
success probabilities of Babai points with minimal efforts
and to reject operations that elongate current basis vectors.
Either using lattice Gaussian sampling [25] or PNP suffices
the first objective, but we shall adhere to PNP because it is
deterministic and this feature will be employed by (27). We
detail the length reductions in boosted LLL as follows.
Assume we are working on the R matrix of a QR decomposition and trying to reduce ri by Q
ri−1 , . . . , r1 . Let PNP
i−1
be abstracted by a parameter L = k=1 pk indicating the

⊥
If the DR condition fails in πR
(R1:n,i−1:i ) and we swap
Γi
ri−1 and ri , then the potential of the basis should be decreasing for the sake of bounding the number of iterations. After
the swap, Ri−1:i,i−1:i becomes


ri−1,i ri−1,i−1
.
(23)
ri,i
0

Let G be a 2 × 2 unitary matrix


√ 2ri−1,i2
√ 2 ri,i 2
ri,i +ri−1,i
ri,i +ri−1,i

;
r
√ 2ri−1,i2
− √ 2 i,i 2
ri,i +ri−1,i

(24)

ri,i +ri−1,i

clearly, GRi−1:i,1:n can restore the upper triangular property
of (23), which transforms to

 q
ri−1,i ri−1,i−1
2 + r2
√
ri,i
2 +r 2
i−1,i
ri,i
.

i−1,i
(25)
r r
0
− √i,i2 i−1,i−1
2
ri,i +ri−1,i

7

From (22) and (25), one can obtain the potential ratio between
two consecutive bases R′ and R as
2(n−i+1)
2(n−i+2) 
q
ri,i ri−1,i−1
2 + r2
√
ri,i
′
2
2
i−1,i
ri,i +ri−1,i
Pot(R )
=
2(n−i+2) 2(n−i+1)
Pot(R)
ri−1,i−1 ri,i
≤

2
2
δ(ri,i
+ ri−1,i
)
,
2 + (r
2
−
⌊r
/r
ri,i
i−1,i
i−1,i i−1,i−1 ⌉ri−1,i−1 )

(26)

where′ the last inequality comes from (21). Based on (26),
Pot(R )
Pot(R) ≤ δ if and only if ⌊ri−1,i /ri−1,i−1 ⌉ = 0. As
∗
∗
a result, preparing the pairs ti,(zi−1
,...,z1∗ ) and ri,(zi−1
,...,z1∗ )
based on (20) is only suitable for reductions before checking
the DR conditions. In case that this condition fails, we
should also prepare ti,(z′ ,...,z′ ) and ri,(z′ ,...,z′ ) that make
1
1
i−1
i−1
⌊ri−1,i /ri−1,i−1 ⌉ = 0:
′

′

(zi−1 , ..., z1 ) = arg

min

(zi−1 ,...,z1 )

n

ri,(zi−1 ,...,z1) ,

o
s.t. ⌊ri−1,i,(zi−1 ,...,z1 ) /ri−1,i−1 ⌉ = 0 , (27)

in which ri−1,i,(zi−1 ,...,z1) denotes the (i − 1)th component
of ri,(zi−1 ,...,z1 ) . In such a manner, if a vector is swapped to
the front, it is not only a short vector, but also the one that
decreases the basis potential so that this kind of swaps cannot
happen too many times.

and the rejection operation marking r3 is r3,(0,0) =
[0, 0.52, 1]⊤ . Eq. (20) would choose the shortest among the
above four routes. Let it be r3,(2,1) (or r3,(0,0) ), which is
employed by Line 5. Eq. (27) can only choose from r3,(1,1) .
Then we test the DR condition and it succeeds, so the while
loop stops.
Algorithm 2: The boosted LLL algorithm.
Input: original lattice basis D ∈ Rn×n , Lovász constant
δ, list number L.
Output: reduced basis D, unimodular matrix T
1 [Q, R] = qr(D);
⊲ The QR decomposition of D;
2 i = 2, T = I;
3 while i ≤ n do
∗
∗
4
use (20) to get [ri,(zi−1
,...,z1∗ ) , ti,(zi−1
,...,z1∗ ) ] and use
(27) to get [ri,(z′ ,...,z′ ) , ti,(z′ ,...,z′ ) ];
1
1
i−1
i−1
∗
∗
5
R1:n,i = ri,(zi−1
,...,z1∗ ) ,T1:n,i = ti,(zi−1
,...,z1∗ ) ;
6
if condition (21) fails then
7
R1:n,i = ri,(z′ ,...,z′ ) ,T1:n,i = ti,(z′ ,...,z′ ) ;
1
1
i−1
i−1
8
define G as in (24);
9
swap R1:n,i and R1:n,i−1 , T1:n,i and T1:n,i−1 ;
10
Ri−1:i,1:n ← GRi−1:i,1:n ;
11
Q1:n,i−1:i ← Q1:n,i−1:i G⊤ ;
12
i ← max(i − 1, 2);
13
14

B. Algorithm description
Combing the length reduction process above, the procedure
of boosted LLL is given in Algorithm 2. Inside the loops, it
employs a fixed structure column traverse strategy rather than
using a parallel traversing [12], [13], such that a theoretical
O(n) factor in bounding the number of loops can be saved. In
line 4, the PNP algorithm and rejection prepare two versions
∗
of reduced vectors. The stronger version ri,(zi−1
,...,z1∗ ) is used
before testing the DR condition (line 6), so that the new ri is
the shortest candidate among the L routes of PNP and the old
ri . If it cannot pass this test, a weaker version ri,(z′ ,...,z′ )
1
i−1
is used in line 7, who has identical value in the first layer as
the Babai point and a variety of pi−2 × · · · × p1 routes in the
remaining layers. Lastly, line 10 restores the upper triangular
feature of R via a lightweight 2×2 Givens rotation matrix and
line 11 balances the unitary matrix. The toy example below
may help to understand our algorithm.
Example 1. Suppose we are

1
R= 0
0

reducing a matrix

0.4
0
1 0.52 
0
1

in round i = 3 and executing from Line 4 of Algorithm 2.
For the PNP algorithm, we set the L = 3 routes as p2 × p1 =
3 × 1. The three nearest integers to r2,3 /r2,2 are 1, 0, 2, so
the corresponding PNP routes are

⊤

r3,(1,1) = [−0.4, −0.48, 1] ,
r3,(2,1) = [0, 0.52, 1]⊤ ,


r3,(3,1) = [−0.8, −1.48, 1]⊤ ,

15

else
i ← i + 1;

D ← QR.

In essence, this algorithm attempts to minimize the basis
length while keeping the Siegel condition, and the PNP
algorithm offers flexible efforts to do so. If we replace lines
4 and 5 by using the Babai point and delete line 7, Algorithm
2 degrades to the classic LLL algorithm [11].
C. Properties of boosted LLL
2
When the boosted LLL algorithm terminates, δri−1,i−1
−
ri−1,i
2 2
2
( ri−1,i−1 −⌊ ri−1,i−1 ⌉) ri−1,i−1 ≤ ri,i holds for all 2 ≤ i ≤ n,
which ensure the Siegel properties hold:
ri−1,i

|ri−1,i−1 | ≤ β|ri,i |.

(28)

Assume the PNP algorithm has parameters (pk−1 , . . . , p1 )
for 2 ≤ k ≤ n, then πRΓi (ri ) is contained in V0 (RΓi ) ∪
P( q1 r∗1 , . . . , qi−1 r∗i−1 ), where r∗1 , . . . , r∗i−1 are the GSO
vectors
of RΓi . Though this region can be much larger than

P( r∗1 , . . . , r∗i−1 ), we have

1X 2
r
(29)
4 j<i j,j


/
if πRΓi (ri ) ∈ P( r∗1 , . . . , r∗i−1 ). If πRΓi (ri ) ∈
P( r∗1 , . . . , r∗i−1 ), we can always find the Babai point
P
2
2
2
2
due to (20)
r′i such that kri k < kr′i k ≤ ri,i
+ 41 j<i rj,j
and (27), so condition (29) always holds in boosted LLL.
With (28) and (29), classical properties of LLL can be
trivially proved:
2

2
kri k ≤ ri,i
+

8

l(D) ≤ β n−1 λn (D),

(30)

ξ(D) ≤ β n(n−1)/2 .

(31)

Since we have devoted much effort to implement the length
reductions, (30) and (31) are the least bounds that we should
expect from boosted LLL. However, moving any step forward
seems difficult because even using CVP as length reduction
still fails to generate a better explicit bound than (29). The
difficulty of improving bounds on lengths exists in all variants
of LLL, including the LLL with deep insertions (LLL-deep)
[18]. In this regard, boosted LLL only serves as an ameliorated
practical algorithm.

D. Implementation and Complexity
The total number of loops K in Algorithm 2 equals to the
number testing condition (21), whose number of positive and
negative tests are denoted as K + and K − , respectively. The
total number of negative test is


1
Pot(D0 )
Pot(D0 )
−
, (32)
=
×ln
K ≤ log1/δ
Pot(DK )
ln(1/δ)
Pot(DK )
where D0 , DK are the initial basis and the basis after K
loops, respectively. In the fixed traversing strategy, we also
have K + ≤ K − + n − 1. We first show how to choose δ
such that the boosted LLL algorithm has the best performance
1
remains to be a polynomial number. After that,
while ln(1/δ)
Pot(D0 )
Pot(DK )

is evaluated to complete our complexity analysis.
1) Optimal δ: Among literature, δ is often chosen arbitrarily close to 1 while explanations are lacking. In Micciancio’s
book [1, Lem. 2.9], it is shown if δ = 1/4 + (3/4)n/(n−1) ,
1
≤ nc for all c > 1. More generally, we can define
then ln(1/δ)
an optimal principle of choosing δ, i.e.,
1
δ(a , n) = ∗ +
a
∗



a∗ − 1
a∗

n/(n−1)

where a∗ = 1−e1 −1 .
With such settings, three distinctive properties exist:
1
c
ln(1/δ) ≤ n for all n; δ is asymptotically close to 1 so that
the algorithm has the best performance; and it is the smallest
value satisfying the previous two attributes (the fastest one
among the class of best performance). Proposition 6 justifies
these claims and the proof is given in Appendix E.
Proposition 6. For arbitrary constants a > 1, c > 1, if
n/(n−1)
δ(a, n) = a1 + a−1
, then for all n,
a
1
≤ nc .
ln(1/δ)

(33)

Let a = limn→∞ arg mina δ(a, n) be defined as the universal good constant, then
1
.
1 − e−1

0)
With reference to [36], we have Ψ(D
ψ(D0 ) ≤ κ(D0 ), where
κ(D0 ) is the condition number of D0 . So if the condition
number of the input basis satisfies ln κ(D0 ) = O(ln n), then
the number of iterations in boosted LLL is K ≤ 2K − +n−1 =
O(nc+2 ln n), where c > 1 is a constant arbitrarily close to
1. By further counting the number of flops inside and outside
the loop of Algorithm 2, the total complexity of boosted LLL
is O(Ln4+c ln n).
Remark 3. The complexity analysis above is quite general.
For instance, if D0 is Gaussian, then it follows from [36] that
E(ln κ(D0 )) ≤ ln n + 2.24. In the application to IF [21], we
can also take a detour to employ this property of Gaussian
matrices. Firstly, the condition number of the input basis D0
would increase if the signal to noise ratio (SNR) rises, so it
suffices to investigate the case for infinite SNR. The target
then becomes the dual of a Gaussian random matrix that has
the same condition number, so E(ln κ(D0 )) ≤ ln n+2.24 also
holds in IF.

V. A PPLICATION

TO INTEGER FORCING

In the context of optimizing the achievable rates of IF, some
results based on LR have been presented in [37], where the
difference between KZ and Minkowski is not obvious because
the system size is small (2 × 2 or 4 × 4). Since we have
improved the classic KZ and LLL, we will verify our boosted
algorithms in IF by showing their performance about ergodic
rates, orthogonal defects (inversely proportional to sum-rates),
and complexity in flops.
A. IF and SBP
In this subsection, the IF transceiver architecture will be
reviewed by using real value representations for simplicity. In
a MIMO system with size n × n, each antenna has a message
wi = [wi (1), wi (2), . . . , wi (k)]⊤ ,

where i ∈ {1, . . . , n}, wi ∈ Fkp , and Fp is a finite field with
size p. As the conversion from message layer to physical layer,
an encoder Ei : Fkp → Rn maps the length-k message wi into
a lattice codeword
xi = [xi (1), xi (2), . . . , xi (T )]⊤ ,

∗

a∗ =

2) Total complexity in flops: Further define ψ(D) =
2
2
mini ri,i
and Ψ(D) = maxi ri,i
. Since our length reduction
does not change ri,i while (25) shows that any swap can
narrow the gap between ri−1,i−1 and ri,i , the number of
negative tests between the initial basis D0 to the final basis
DK is


Pot(D0 )
K − ≤ nc ln
Pot(DK )


Ψ(D0 )
nc+1 (n + 1)
.
(35)
ln
≤
2
ψ(D0 )

(34)

2

where kxi k ≤ T P , T stands for code length and P stands for
SNR. All encoders operate at the same lattice with the same
rate:
k
RTX = log2 p.
T

9

Let xi (j) be the jth symbol of xi , we may write the
transmitted vector across all antennas in time j as x[j] =
[x1 (j), . . . , xn (j)]⊤ . An observation y[j] ∈ Rn can be subsequently written as
y[j] = Hx[j] + z[j]

(36)

in which H ∈ Rn×n denotes the MIMO channel matrix and
z[j] is the additive white Gaussian noise (AWGN) with zi [j] ∼
N (0, 1). Let Y, X, and Z be the concatenated y[j], x[j] and
z[j] from time slots 1 to T . In a linear receiver architecture, the
receiver will project Y with a matrix B = [b1 , . . . , bn ]⊤ ∈
Rn×n to get the useful information AX for further decoding,
BY =

AX
|{z}

useful information

+ (BH − A)X + BZ.
|
{z
}

(37)

effective noise

⊤

We choose A = [a1 , . . . , an ] ∈ Zn×n because these lattice
codewords are closed under integer combinations. A should
also be full rank to avoid losing information.
For a preprocessing matrix B, the following computation
rate can be obtained in the ith effective channel if the coding
lattices satisfy goodnesses for channel coding and quantization
[21]
!
P
1
+
, (38)
R(H, ai , bi ) = log2
2
2
2
kbi k + P kH⊤ bi − ai k
where log+
2 (x) = max {log2 (x), 0}.
The
first
step towards maximizing
the rates is to set
o
n
2
2
/∂bi = 0 for a fixed IF co∂ kbi k + P H⊤ bi − ai
efficient matrix A, which leads to
1
bi = (HH⊤ + I)−1 Hai .
P
Plug this into (38) and use Woodbury matrix identity for the
inverse of a matrix, we have
!
1
P
+
R(H, ai ) =
log2
,
(39)
2
2
kDai k
1

where D = Λ− 2 V⊤ and VΛV⊤ = H⊤ H + 1/P I is the
eigendecomposition. Achieving the optimum rate is therefore
equivalent to solving SIVP on lattice L(D):
arg

min

A∈Zn×n , rank(A)=n

2

max kDai k ,
i

(40)

2

in which minA∈Zn×n , rank(A)=n maxi kDai k = λn (D).
Now we explain how to obtain the estimations of messages.
Upon quantizing BY to the fine lattice and modulo the coarse
lattice in a row-wise manner [23], a converter Di : Rn → Fkp
then maps the physical layer codeword to a message under
finite field representations, i.e., ûi = [W⊤ ai ] mod p, W =
[w1 , . . . , wn ]⊤ . These combinations are then collected, so as
to decode the messages as
⊤
[ŵ1 , . . . , ŵn ]⊤ = A−1
p [û1 , . . . , ûn ] ,

where Ap is a full rank matrix over Zp and A−1
p is taken over
the same field.
With the above demonstrations in mind, there should be at
least two reasons for us to restrain SIVP to SBP

arg

min

2

A∈GLn (Z)

max kDai k .
i

(41)

The first reason is about flexibility. With SBP, we can choose
among lattice reduction algorithms from polynomial to exponential complexity with guaranteed properties, and these
algorithms are still efficient when SNR is high. The second
reason is about complexity, where the inverse of A over finite
fields is much easier to calculate when A ∈ GLn (Z), and
algorithms for SIVP or the successive minima problem (SMP)
are generally more complicated than those of SBP [37], [38].
For instance, we can observe that for the enumeration routines
of SMP, Minkowski reduction and boosted KZ reduction, one
needs to verify the linear independence of a new vector with
previous lattice vectors for SMP, while Minkowski reduction
only needs to check the greatest common divisor of the
enumerated coefficients [10] and boosted KZ does not require
such inspections.
B. Simulation results
This subsection examines the rates and complexity performance when applying the proposed boosted KZ and boosted
LLL algorithms for IF receivers. We show the achievable rates
rather than the bit error rates of IF MIMO receivers, since
the latter depend on which capacity-approaching code for the
AWGN channel is used at the transmitter. All simulations are
performed on real matrices with random entries drawn from
i.i.d. Gaussian distributions N (0, 1). Results in the figures are
all averaged from 103 Monte Carlo runs.
The boosted LLL algorithm is referred as “b-LLL-L” with L
being the total number of branches in the PNP algorithm, i.e.,
L = pi−1 pi−2 · · · p1 remains unchanged for different columns
i’s. If L = 1, this version means only adding a rejection
operation to the classic LLL algorithm [11]. When L = 3
or L = 9, we expand 3 branches in the first or first two layers
of the PNP algorithm. Regarding other typical variants of LLL,
such as the effective LLL [12] and greedy LLL [17], they all
boil down to the same performance as LLL if we implement
a full size reduction at the end of their algorithms, so we omit
comparing our algorithms with these variants.
The boosted KZ algorithm (“b-KZ”) is implemented as
described in Algorithm 1. To ensure a fair comparison, the
KZ algorithm follows the same routine as Algorithm 1 except replacing the “CVP subroutine” with a size reduction.
Minkowski reduction is also included as our reference with
the label “Minkow”, whose implementation follows [10, Sec.
V].
1) Achievable rate: The actual achievable rate of the IF
receivers can be quantitatively evaluated by the ergodic rate
defined by [37]


RE = E n min R(H, ai ) ,
i

where the expectation is taken over different realizations of
H, and R(H, ai ) was defined in (39).
In Fig. 2, we have plotted the rate performance of different
LR algorithms in a 20 × 20 real-valued MIMO channel, in
which the channel capacity 21 log2 (det(I + P HH⊤ )) serves

10

70

1100
1000

60

900

50

700
LLL
b−LLL−1
b−LLL−3
b−LLL−9
KZ
b−KZ
Minkow
Capacity

40

30

20
0

5

10

OD

Ergodic rate

800

600

LLL
b−LLL−1
b−LLL−3
b−LLL−9
KZ
b−KZ
Minkow

500
400
300
200
100
0

15

5

SNR/dB
Fig. 2. SNR versus ergodic rate for different LR algorithms.

6

10

120
110

4

100

LLL
b−LLL−1
b−LLL−3
b−LLL−9
KZ
b−KZ
Minkow
Capacity

90
80
70
60

10

OD

Ergodic rate

15

Fig. 4. SNR versus OD for different LR algorithms.

130

50
15

10
SNR/dB

LLL
b−LLL−1
b−LLL−3
b−LLL−9
KZ
b−KZ
Minkow

2

10

0

20

25

30

dimension n

10

5

10

15
20
dimension n

25

30

Fig. 3. Dimension versus ergodic rate for different LR algorithms.

Fig. 5. Dimension versus OD for different LR algorithms.

as an upper bound. In the figure, the b-LLL-1 algorithm has
higher rates than KZ and LLL, and the improvements after we
increase the list number to L = 3, 9 can still be spotted in
this crowded figure. The b-KZ method attains almost the same
rates as those of Minkowski reduction. KZ reduction does not
offer better rates than LLL because KZ only guarantees to
yield a basis with the smallest potential, and both of them are
under the curse Proposition 1.
In Fig. 3, we fixed the SNR to be 20dB and study how the
size of the system is affecting their ergodic rates. From this
graph, the differences of rates among different LR methods
amplify as dimension n increases, and their mutual relations
are the same as those of Fig. 2.
2) Orthogonal defect: The ergodic rate RE is only determined by the basis length l(D). To evaluate the sum-rates for
all data streams, OD’s can be employed which are proportional
to the length products of basis vectors. Such a quantity can
reveal the gaps between different algorithms more vividly.
In Figs. 4 (fixed size of 20 × 20) and 5 (fixed SNR of
20dB), we have plotted the SNR versus OD, and dimension

versus OD relations for distinct lattice reduction algorithms.
From these two figures, several phenomenons can be observed.
Boosted KZ cannot surpass Minkowski reduction but remains
close to it. The performance improvements from b-LLL-1,
to b-LLL-3, b-LLL-9 are approximately proportional to the
increment in the list size L. One interesting thing to observe
from Fig. 4 is, the performance gaps between boosted and
non-boosted algorithms are becoming larger as P rises. Since
1
D = Λ− 2 V⊤ and VΛV⊤ = H⊤ H + 1/P I, the increment of
P is, intrinsically, changing the goodness of the corresponding
minimal basis. It also says that the possibility of size reduction
being suboptimal would increase if the lattice bases tend to be
more random. Lastly, Fig. 5 shows an evident “Minkow < bKZ < b-LLL-9 < b-LLL-3 < b-LLL-1 < KZ < LLL” relation
about OD, and their OD values are much better than their
theoretical bounds (see e.g., Eqs. (13) and (31)).
3) Complexity: In addition to our theoretical analysis on
the complexity of the proposed algorithms, we further compare their empirical costs by the expected number of flops,
which are clearly shown in Fig. 6. Not surprisingly, the b-

11

KZ algorithm spends about 1.5 times the efforts of KZ in
the dimensions depicted in Fig. 6, and the b-LLL-1, 3, 9
algorithms costs around 1, 1.5, and 3 times the efforts of
LLL. Both b-KZ and KZ reductions have dramatically lower
number of flops than Minkowski reduction. Moreover, the
boosted LLL algorithms have much smaller complexity than
KZ while reducing the bases more effectively as Figs. 2 to 5
have revealed.
To sum up, concerning the complexity-performance tradeoffs as well as the theoretical bounds, the boosted KZ and
LLL algorithms can be the ideal candidates for reducing lattice
bases in IF with exponential and polynomial complexity,
respectively.
x 10

LLL
b−LLL−1
b−LLL−3
b−LLL−9
KZ
b−KZ
Minkow

complexity in flops

6
5
4

A PPENDIX B
P ROOF OF PROPOSITION 3
Proof: Regarding (9), first recall a fact that we cannot
produce n independent vectors by using a lattice of rank
n − 1, then among λ1 (D), . . . , λn (D), at P
least one of them,
n−1
xi di where
e.g., λi′ (D), corresponds to v = xn dn + i=1
Pn−1
i=1 xi di ∈ L(DΓn ), xn ∈ Z \ 0. With QR decomposition
[Q, R] = qr(D),


i−1
n
X
X
rj,i qj 
xi ri,i qi +
v =

6

7

there are two lattice points (0 and v) inside Vv (DΓi ), which
contradicts the basic property of a Voronoi cell, i.e., there can
be only one lattice point inside a Voronoi region.
We proceed to prove (42). Since πDΓi (di ) is quantized to
v, their difference πDΓi (di ) − v lies inside the Voronoi cell
2
V0 (DΓi ), which yields hπDΓi (di ) − v, wi < kwk /2 for all
w ∈ L(DΓi ) and w 6= 0. As v−πDΓi (di ) ∈ V0 (DΓi ), choose
2
an instance of w = v 6= 0 for hv − πDΓi (di ), wi < kwk /2,
then (42) is obtained.

=

2

n−1
X
i=1

1
0

j=1

i=1

3

5

10
dimension n

15

20

|rn,n |2 ≤

QUESTIONS

We have only demonstrated the theoretical superiority of
boosted KZ over KZ and Minkowski, while Minkowski reduction still yields shorter vectors in our simulations. One
interesting open question is whether there exist better performance bounds for Minkowski reduction. It is also of sufficient
interests to improve the performance analysis on boosted LLL.
A PPENDIX A
P ROOF OF PROPOSITION 2
2

Proof: First of all, the reducible condition kdi − vk <
2
<
kdi k can be reformulated as
πDΓi (di ) − v
2
πDΓi (di ) , which becomes equivalent to
2

kvk2 /2 < hπDΓi (di ), vi.

xi ri,i qi +

i−1
X
j=1



rj,i qj  + xn rn,n qn .

Notice that −v also corresponds to λi′ (D), so we can confine
xn > 0 and consider the following two cases.
1) If xn
> 1, it is  observed that kvk =
Pi−1
Pn−1 
≥ xn |rn,n |
r
q
x
i,i i +
j=1 rj,i qj + xn rn,n qn
i=1 i
because the qi ’s are orthogonal, which yields

Fig. 6. Dimension versus complexity for different LR algorithms.

VI. O PEN



(42)

It is necessary to show hπDΓi (di ), vi > 0 for v 6= 0
so that the inequality we pursuit makes sense. We give a
proof by contradiction. Suppose that θ(πDΓi (di ), v) > π/2,
due to symmetricity of the Voronoi cell Vv (DΓi ), there
exists a symmetric point d′i of πDΓi (di ) on v, such that
θ(d′i , v) > π/2. Define the half-space of v as Hv =
n
{x
convex combination among
 ∈ R | hv, xi > 0}, then the
Vv (DΓi ) ∩ Hv , πDΓi (di ), d′i must include the origin. Then

1
1
λi′ (D)2 ≤ λn (D)2 .
x2n
4

(43)

We then proceed to bound the last term in (7). For 1 ≤ i ≤ n,
the covering radius of lattice L(DΓn ) is
ρ(DΓn ) =
≤

max dist (x, L(DΓn ))
x
v
un−1
uX
2 ,
rk,k
1/2t

(44)

k=1

where the inequality is obtained after choosing x as a “deep
hole” [39, P. 33] and solving this CVP by applying Babai’s
nearest plane algorithm [40]. Since boosted KZ still assures
⊥
|rk,k | = λ1 (πD
([dk , . . . , dn ])), and the projection of the
Γk
kth successive minimum in D onto the orthogonal complement of DΓk must have a least one non-zero coefficient for
[dk , . . . , dn ], we have |rk,k | ≤ λk (D); plug this into (44),
v
un−1
uX
λk (D)2 .
(45)
ρ(DΓn ) ≤ 1/2t
k=1

Put (43) and (45) into (7), then kdn k2 ≤ 14 λn (D)2 +
Pn−1
1
n
2
2
k=1 λk (D) ≤ 4 λn (D) .
4
2) If xn = 1, recall that our length reduction by CVP
(line 11) ensures dn is the shortest vector among the set

12

n
o
Pn−1
dn + i=1 zi di | ∀ zi ∈ Z , so kdn k ≤ λi′ (D) ≤ λn (D)
in such a scenario.
Combining 1) and 2) proves (9). 
As for (8), since all sublattices L(DΓi+1 ) | 1 ≤ i ≤ n
are also boosted KZ
it follows from the proved (9)
n reduced,
√ o
i
that kdi k ≤ max 1, 2 λi (DΓi+1 ). With |ri,i | ≤ λi (D)
and
√ the bound for the covering radius, we also have kdi k ≤
i+3
2 λi (D) for all i. So choosing the minimum among them
yields (8).
A PPENDIX C
P ROOF OF PROPOSITION 4
Proof: Since |ri,i | = λ1 (Ri:n,i:n ), we apply Minkowski’s
second theorem [31, P. 202] to lattices L(Ri:n,i:n ) with
2
1 ≤ i ≤ n − 1, then we have rn−j+1,n−j+1
≤
Q
1/j
j
2
γj
. As those of [28, Prop. 4.2], we
k=1 rn−k+1,n−k+1
cancel duplicated terms in this inequality and use induction
from L(Rn−1:n,n−1:n ) to L(R1:n,1:n ), then
2
rn−j+1,n−j+1

≤ γj

j
Y

1/(k−1)
γk

k=2

2j
3 ,

!

2
rn,n
.

(46)

Qj


2k 1/(k−1)
3

As γj ≤
we define g(j) =
k=2
evaluate this term. Let z = k − 1, it can be shown that
 !

j−1
X
8j
2z + 2 1
g(j) =
exp
ln
9
3
z
z=2
!
j−1
X
(a)
ln(z)
8j
exp
≤
9
z
z=2


Z
j−1
(b)
8j
ln(z)
≤
exp
dz
9
z
1
8j
=
(j − 1)ln(j−1)/2 ,
9

8j
2
(j − 1)ln(j−1)/2 rn,n
,
9

2

≤
≤


i
X
8j
1
2
1 +
(j − 1)ln(j−1)/2  ri,i
4 j=2 9


2i
2
1 + (i − 1)1+ln(i−1)/2 ri,i
9

for 1 ≤ i ≤ n, so (12) is proved.

(48)

All bases can be evaluated via Eq. (48) because either [u, v]
or [u, −v] must be acute. In the boosted KZ algorithm, if we
cannot reduce the length of di with only d1 , then |cd1 |/(d21 +
d22 ) < 1/2. In the other direction, reducing d1 by di is also
impossible because d1 is already the shortest, so |d1 /c| <
1/2. By combining these two non-reducible conditions and
the acute condition of d1 /c ≥ 0, requirements in (48) can be
met.
A PPENDIX E
P ROOF OF PROPOSITION 6
Proof: The proof of (33) follows those in [1, Lem. 2.9].
To prove (33), it suffices to prove
n→∞

and

1 − e(−(1/n) )
a−1
a−1 n/(n−1) ≤ 1,
a −( a )

(49)

where its l.h.s. is an indeterminate form. Replace n by another
variable x as n = x+1
x , then by using L’Hospital’s Rule, the
l.h.s. of (49) becomes
c

c
1
x c−1
−1/(1+1/x)
)
c( x+2
1 − e−1/(1+1/x)
(x+1)2 e
lim a−1
=
lim
=0
a−1 x+1
x+1 ln( a−1 )
x→0
x→0
−( a−1
a −( a )
a )
a

and thus (49) is proved.
n)
n
1 1/(n−1)
= (n−1)a
−
As for (34), let ∂δ(a,
2 (1 − a )
∂a
1
′
a2 = 0, we obtain the stationary point of δ(a, n) as a =
n)
∂δ(a, n)
1
< 0 if a ∈ (1, a′ ) and ∂δ(a,
>
1−(1−1/n)n−1 , where
∂a
∂a

0 if a ∈ (a′ , ∞). Notice that (1 − 1/n)n−1 = e
after using L’Hospital’s Rule again, we have

ln(1−1/n)
1/(n−1)

, then

1
1
1
=
= lim
.
n−1
−1+1/n
n→∞ 1 − e
n→∞ 1 − (1 − 1/n)
1 − e−1
lim

(47)

for 2 ≤ j ≤ n, and this is the condition in boosted KZ that
corresponds to the Siegel condition in LLL. Let j = n and
apply (47) to each of L(R1:n,1:i ) for 2 ≤ i ≤ n, then we obtain
ln(j−1)/2 2
rj,j . By further incorporating (47)
λ1 (D)2 ≤ 8j
9 (j−1)
Pi−1 2
2
2
, it yields
and the relation of kdi k ≤ ri,i
+ 14 k=1 rk,k
kdi k

|v/u| ≥ 1 and 0 ≤ R(v/u) ≤ 1/2.

c

where the relaxation in (a) avoids evaluating Spence’s function
in the integration and Riemann integral has been used in (b).
Plug this back into (46), we have



Proof: It is equivalent to characterize d1 , di by two
numbers √
u, v in the complex plane C, i.e., u = c and
v = d1 + −1d2 . For an “acute basis” [u, v] [7, P. 76] where
R(v/u) ≥ 0, the basis reaches the first and second successive
minima if and only if

lim

2j
3

2
rn−j+1,n−j+1
≤

A PPENDIX D
P ROOF OF PROPOSITION 5

R EFERENCES
[1] D. Micciancio and S. Goldwasser, Complexity of Lattice Problems, pp.
1–228. Boston, MA: Springer US, 2002.
[2] A. Hassibi and S. Boyd, “Integer parameter estimation in linear models
with applications to gps,” IEEE Trans. Signal Process., vol. 46, no. 11,
pp. 2918–2925, 1998.
[3] R. Neelamani, R. Baraniuk, and R. de Queiroz, “Compression color
space estimation of JPEG images using lattice basis reduction,” in 2001
Int. Conf. Image Process., vol. 1. IEEE, 2001, pp. 890–893.
[4] H. Yao and G. Wornell, “Lattice-reduction-aided detectors for MIMO
communication systems,” in 2002 Glob. Telecommun. Conf., vol. 1.
IEEE, 2002, pp. 424–428.
[5] C. Windpassinger, R. F. H. Fischer, and J. B. Huber, “Lattice-reductionaided broadcast precoding,” IEEE Trans. Commun., vol. 52, no. 12, pp.
2057–2060, 2004.
[6] D. Wubben, D. Seethaler, J. Jalden, and G. Matz, “Lattice Reduction,”
IEEE Signal Process. Mag., vol. 28, no. 3, pp. 70–91, may 2011.

13

[7] P. Q. Nguyen and V. Brigitte, The LLL Algorithm, ser. Information
Security and Cryptography, P. Q. Nguyen and B. Vallée, Eds., pp.
1–503. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010.
[8] A. Korkinge and G. Zolotareff, “Sur les formes quadratiques positives,”
Math. Ann., vol. 11, no. 2, pp. 242–292, jun 1877.
[9] J. Wen and X.-W. Chang, “A modified KZ reduction algorithm,”
in 2015 IEEE Int. Symp. Inf. Theory, no. 7. IEEE, jun 2015, pp.
451–455.
[10] W. Zhang, S. Qiao, and Y. Wei, “HKZ and Minkowski Reduction
Algorithms for Lattice-Reduction-Aided MIMO Detection,” IEEE
Trans. Signal Process., vol. 60, no. 11, pp. 5963–5976, nov 2012.
[11] A. K. Lenstra, H. W. Lenstra, and L. Lovász, “Factoring polynomials
with rational coefficients,” Math. Ann., vol. 261, no. 4, pp. 515–534,
1982.
[12] C. Ling, W. H. Mow, and N. Howgrave-Graham, “Reduced and FixedComplexity Variants of the LLL Algorithm for Communications,” IEEE
Trans. Commun., vol. 61, no. 3, pp. 1040–1050, mar 2013.
[13] W. Zhang, S. Qiao, and Y. Wei, “A Diagonal Lattice Reduction
Algorithm for MIMO Detection,” IEEE Signal Process. Lett., vol. 19,
no. 5, pp. 311–314, may 2012.
[14] H. Vetter, V. Ponnampalam, M. Sandell, and P. A. Hoeher, “Fixed
complexity LLL algorithm,” IEEE Trans. Signal Process., vol. 57, no. 4,
pp. 1634–1637, 2009.
[15] Q. Wen, Q. Zhou, and X. Ma, “An enhanced fixed-complexity LLL
algorithm for MIMO detection,” 2014 IEEE Glob. Commun. Conf.
GLOBECOM 2014, pp. 3231–3236, 2014.
[16] X. W. Chang, X. Yang, and T. Zhou, “MLAMBDA: A modified
LAMBDA method for integer least-squares estimation,” J. Geod.,
vol. 79, no. 9, pp. 552–565, 2005.
[17] Q. Wen and X. Ma, “Efficient Greedy LLL Algorithms for Lattice
Decoding,” IEEE Trans. Wirel. Commun., vol. 15, no. 5, pp. 3560–3572,
may 2016.
[18] C. P. Schnorr and M. Euchner, “Lattice basis reduction: Improved
practical algorithms and solving subset sum problems,” Math. Program.,
vol. 66, no. 1-3, pp. 181–199, aug 1994.
[19] M. Schneider and N. Gama, (2010). “SVP Challenge.” [Online].
Available: http://latticechallenge.org/svp-challenge/index.php
[20] P. Q. Nguyen and D. Stehle, “Low-dimensional lattice basis reduction
revisited (extended abstract),” Algorithmic Number Theory - Proc.
ANTS-VI, vol. 5, no. 4, pp. 1–20, 2012.
[21] J. Zhan, B. Nazer, U. Erez, and M. Gastpar, “Integer-Forcing Linear
Receivers,” IEEE Trans. Inf. Theory, vol. 60, no. 12, pp. 7661–7685,
dec 2014.
[22] N. Gama, N. Howgrave-Graham, H. Koy, and P. Q. Nguyen, “Rankin’s
Constant and Blockwise Lattice Reduction,” Crypto, vol. 4117, pp. 112–
130, 2006.
[23] B. Nazer and M. Gastpar, “Compute-and-forward: Harnessing interference through structured codes,” IEEE Trans. Inf. Theory, vol. 57, no. 10,
pp. 6463–6486, 2011.
[24] C. Ling, “On the proximity factors of lattice reduction-aided decoding,”
IEEE Trans. Signal Process., vol. 59, no. 6, pp. 2795–2808, 2011.
[25] S. Liu, C. Ling, and D. Stehlé, “Decoding by sampling: A randomized
lattice algorithm for bounded distance decoding,” IEEE Trans. Inf.
Theory, vol. 57, no. 9, pp. 5933–5945, 2011.
[26] E. Agrell, T. Eriksson, A. Vardy, and K. Zeger, “Closest point search in
lattices,” IEEE Trans. Inf. Theory, vol. 48, no. 8, pp. 2201–2214, 2002.
[27] B. Hassibi and H. Vikalo, “On the sphere-decoding algorithm I.
Expected complexity,” IEEE Trans. Signal Process., vol. 53, no. 8, pp.
2806–2818, aug 2005.
[28] J. C. Lagarias, H. W. Lenstra, and C. P. Schnorr, “Korkin-Zolotarev
bases and successive minima of a lattice and its reciprocal lattice,”
Combinatorica, vol. 10, no. 4, pp. 333–348, 1990.
[29] H. F. Blichfeldt, “A new principle in the geometry of numbers, with
some applications,” Trans. Am. Math. Soc., vol. 15, no. 3, pp. 227–227,
1914.
[30] Y. Chen and P. Q. Nguyen, “{BKZ} 2.0: Better Lattice Security
Estimates,” Asiacrypt, vol. 7073, pp. 1–20, 2011.
[31] J. W. S. Cassels, An Introduction to the Geometry of Numbers, pp.
1–343. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997.
[32] X. W. Chang, J. Wen, and X. Xie, “Effects of the LLL reduction on the
success probability of the babai point and on the complexity of sphere
decoding,” IEEE Trans. Inf. Theory, vol. 59, no. 8, pp. 4915–4926, 2013.
[33] P. Q. Nguyen and D. Stehlé, “LLL on the average,” Algorithmic
Number Theory, vol. 4076, pp. 1–17, 2006.
[34] N. Gama and P. Q. Nguyen, “Predicting Lattice Reduction,” Eurocrypt,
vol. 4965, pp. 31–51, 2008.

[35] R. Lindner and C. Peikert, “Better key sizes (and Attacks) for LWEbased encryption,” Lect. Notes Comput. Sci. (including Subser. Lect.
Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 6558 LNCS, pp.
319–339, 2011.
[36] J. Jalden, D. Seethaler, and G. Matz, “Worst- and average-case
complexity of LLL lattice reduction in MIMO wireless systems,” in
2008 IEEE Int. Conf. Acoust. Speech Signal Process. IEEE, mar
2008, pp. 2685–2688.
[37] A. Sakzad, J. Harshan, and E. Viterbo, “Integer-forcing MIMO linear
receivers based on lattice reduction,” IEEE Trans. Wirel. Commun.,
vol. 12, no. 10, pp. 4905–4915, 2013.
[38] L. Ding, K. Kansanen, Y. Wang, and J. Zhang, “Exact SMP Algorithms
for Integer-Forcing Linear MIMO Receivers,” IEEE Trans. Wirel. Commun., vol. 14, no. 12, pp. 6955–6966, 2015.
[39] J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and
Groups, ser. Grundlehren der mathematischen Wissenschaften, pp.
1–690. New York, NY: Springer New York, 1999, vol. 290.
[40] L. Babai, “On Lovasz lattice reduction and the nearest lattice point
problem,” Combinatorica, vol. 6, no. 1, pp. 1–13, 1986.

