Search

Since most low-complexity suboptimal MIMO detectors could not exploit a full receive diversity gain [68], the LR-based MIMO detectors are developed to provide a full receive diversity gain with low computational complexity [56, 69, 70]. The LR-based MIMO detector is first discussed in [21], then more LR-based MIMO detectors are proposed in [24]. It has been shown that the LR-based MIMO detector using the MMSE-SIC approach, namely the LR-based MMSE-SIC detector, approaches the ML performance. An overview of LR-based detection can be found in [26] and a soft-decision with the detection is discussed in [71].

In MIMO detection, the signals transmitted by multiple antennas can be detected jointly based on the ML principle for optimal performance. However, its complexity is prohibitively high for a large number of transmit antennas and a higher order modulation method. There are suboptimal approaches of low complexity. Unfortunately, they cannot exploit a full receive diversity gain, which results in the performance gap between the ML and suboptimal approaches (e.g., linear MMSE detection). This gap usually increases with SNR. Therefore, it is desirable to find some new detection methods that can provide near ML performance with low complexity which is comparable to that of linear detectors. In this chapter, we introduce two key ingredients: list decoding and lattice (basis) reduction, which can be used to develop different computationally efficient algorithms with reasonably good performance.

The use of the theory of lattices in communications for the construction of codes for the additive white Gaussian channel, is well established. Many elegant constructions, encoding and decoding algorithms, and structural properties of classes of lattices have been found. Lattices have also played an important role in cryptography where they are more often used for showing weaknesses of cryptographic algorithms. However, new public key systems were constructed using lattices based on ground breaking work of Ajtai. It is interesting to note that, in contrast to the situation in communications, the main lattice tool for cryptography is lattice reduction to determine short or close vectors. This note briefly reviews such applications of lattices to cryptography.

Different to the theorems of the previous chapters which were “bad news” for a cryptanalyst, we present some “bad news” for the cryptographer in this chapter. All theorems show weaknesses of special instances of the RSA cryptosystem, namely systems that use either a small encryption or decryption key.

The main results to be presented here deal with representations as a sum of four squares. However, it is useful for purposes of exposition to consider the corresponding theorems for sums of two squares. Since these results are so familiar, and part of elementary courses, it may seem that these propositions are belaboring the obvious. However, there is a slight difference in emphasis from the usual treatment that will be useful in describing the generalization. There are two types of questions to be considered: algorithmic — how can one compute representations of a number as a sum of two or four (or possibly some other number) of squares? — and enumerative — is there a structure on the set of representations that allows their number to be determined in an elementary manner?

Early in 1982, A. Shamir [12] announced a polynomial time attack on the basic Merkle-Hellman knapsack cryptosystem. Since that time, attacks on various other knapsack cryptosystems have been proposed [1,2,4,6,7,11]. One of the most influential of the works in this area has been L. Adleman’s paper [1], which was the first to suggest the use of the Lenstra, Lenstra and Lovasz (L3) lattice basis reduction algorithm [9] in attacks on knapsack cryptosystems. The L3 algorithm is now the most important tool used in such attacks.