On Solving the Shortest Basis Problem Based on Sequential Reduction

Low-complexity lattice reduction algorithms are generally not optimized for solving the shortest basis problem (SBP). We fill this blank by tweaking the recently introduced sequential reduction (SR). In a quest for developing a provable and low-complexity reduction algorithm under the SR framework, we propose to employ successive interference cancellation (SIC) as a subroutine inside SR, and the whole algorithm is referred to as SR-SIC. On the theoretical front, we prove that the upper bound on the basis length of SR-SIC is better than those of major Lenstra, Lenstra, and Lovász (LLL) based variants when the dimension of the lattice basis is no larger than 4. In practice, we show by simulations that SR-SIC yields higher information rate than LLL when designing integer-forcing linear receivers, in which SR-SIC also enjoys lower computational complexity.