Boosted KZ and LLL Algorithms

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-Lovasz (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 multi-input multi-output (MIMO) communications. Our simulations confirm their rate and complexity advantages.

MATLAB codes are available in: https://codeocean.com/2017/06/22/boosted-korkine-zolotarev-lpar-kz-rpar-and-lenstra-ndash-lenstra-ndash-lov%C3%A1sz-lpar-lll-rpar-algorithms/code

Cited by in corpus (9)

• Bounds on quantum evolution complexity via lattice cryptography
• On Low-complexity Lattice Reduction Algorithms for Large-scale MIMO Detection: the Blessing of Sequential Reduction
• Lattice Reduction over Imaginary Quadratic Fields
• A Relax-and-Round Approach to Complex Lattice Basis Reduction
• Ring Compute-and-Forward over Block-Fading Channels
• Improved Upper Bounds on the Hermite and KZ Constants
• An Efficient Optimal Algorithm for the Successive Minima Problem
• On the Success Probability of Three Detectors for the Box-Constrained Integer Linear Model
• Markov chain Monte Carlo Methods For Lattice Gaussian Sampling: Lattice Reduction and Decoding Optimization