The Lenstra-Lenstra-Lovász (LLL) algorithm is a popular lattice reduction algorithm in communications. In this paper, variants of the LLL algorithm with either reduced or fixed complexity are proposed and analyzed. Specifically, the use of effective LLL reduction for lattice decoding is presented, where size reduction is only performed for pairs of consecutive basis vectors. Its average complexity (measured by the number of floating-point operations and averaged over i.i.d. standard normal lattice bases) is shown to be O(n3log n), where n is the lattice dimension. This average complexity is an order lower than previously thought. To address the issue of variable complexity of the LLL algorithm, two fixed-complexity approximations are proposed. One is fixed-complexity effective LLL, for which the first vector of the basis is proven to be bounded in length; the other is fixed-complexity LLL with deep insertion, which is shown to be closely related to the well known V-BLAST algorithm. Such fixed-complexity structures are much desirable in hardware implementation since they allow straightforward constant-throughput implementation.

The use of Lenstra-Lenstra-Lovasz (LLL) lattice reduction significantly improves the performance of zero-forcing (ZF) and successive interference cancellation (SIC) decoders in multi-input multi-output (MIMO) communications. Capitalizing on the observation that the decision region of SIC is determined by the Gram-Schmidt vectors rather than the basis itself, we propose the use of effective LLL reduction in SIC decoding, where size reduction is only performed for pairs of consecutive basis vectors. We establish the theoretic upper bound O(n3log n) on the average complexity of effective LLL reduction for the i.i.d. Gaussian model of MIMO fading channels, which is an order lower than previously thought. Moreover, an effectively LLL-reduced basis can easily be transformed into the standard LLL-reduced basis for the purpose of ZF decoding.

We re-examine Paillier's cryptosystem, and show that by choosing a particular discrete log base g, and by introducing an alternative decryption procedure, we can extend the scheme to allow an arbitrary exponent e instead of N. The use of low exponents substantially increases the efficiency of the scheme. The semantic security is now based on a new decisional assumption, namely the hardness of deciding whether an element is a "small" e-th residue modulo N2.We also show how to use Paillier's original cryptosystem to build a trapdoor commitment scheme. This new scheme is information-theoretically private, and computationally binding (this property holds under the assumption that the RSA function with exponent N is hard to invert). A novel property of this new commitment scheme is that most of the work can be done offline before knowing the message one wants to commit to. Once the message is known only two multiplications are required. This is the first trapdoor commitment scheme with this online-offline efficiency property which is also length-preserving.