We propose a method for MIMO decoding when channel state information (CSI) is unknown to both the transmitter and receiver. The proposed method requires some structure in the transmitted signal for the decoding to be effective, in particular that the underlying sources are drawn from a hypercubic space. Our proposed technique fits a minimum volume parallelepiped to the received samples. This problem can be expressed as a non-convex optimization problem that can be solved with high probability by gradient descent. Our blind decoding algorithm can be used when communicating over unknown MIMO wireless channels using either BPSK or MPAM modulation. We apply our technique to jointly estimate MIMO channel gain matrices and decode the underlying transmissions with only knowledge of the transmitted constellation and without the use of pilot symbols. Our results provide theoretical guarantees that the proposed algorithm is correct when applied to small MIMO systems. Empirical results show small sample size requirements, making this algorithm suitable for block-fading channels with coherence times typically seen in practice. Our approach has a loss of less than 3dB compared to zero-forcing with perfect CSI, imposing a similar performance penalty as space-time coding techniques without the loss of rate incurred by those techniques.
Lattice-based signature schemes following the Goldreich–Goldwasser–Halevi (GGH) design have the unusual property that each signature leaks information on the signer’s secret key, but this does not necessarily imply that such schemes are insecure. At Eurocrypt ’03, Szydlo proposed a potential attack by showing that the leakage reduces the key-recovery problem to that of distinguishing integral quadratic forms. He proposed a heuristic method to solve the latter problem, but it was unclear whether his method could attack real-life parameters of GGH and NTRUSign. Here, we propose an alternative method to attack signature schemes a la GGH by studying the following learning problem: given many random points uniformly distributed over an unknown n-dimensional parallelepiped, recover the parallelepiped or an approximation thereof. We transform this problem into a multivariate optimization problem that can provably be solved by a gradient descent. Our approach is very effective in practice: we present the first successful key-recovery experiments on NTRUSign-251 without perturbation, as proposed in half of the parameter choices in NTRU standards under consideration by IEEE P1363.1. Experimentally, 400 signatures are sufficient to recover the NTRUSign-251 secret key, thanks to symmetries in NTRU lattices. We are also able to recover the secret key in the signature analogue of all the GGH encryption challenges. The relationship between the blind digital co-channel communications problem and the problem of finding a separating hyperplane in IR sup d is explored. A simple model for the blind digital co-channel communications problem is X=AS, where X is a known IR sup d spl times N matrix. A is an unknown full-rank IR sup d spl times d matrix, and S is an unknown full-rank d spl times N matrix with elements drawn from a multiple-amplitude-shift-keying (M-ASK) alphabet S. An algorithm with proof is given that solves for A and S up to a simple matrix factor. The algorithm is extended to the complex quadrature-amplitude modulation (QAM) alphabet. The key step in this algorithm involves finding a separating hyperplane parallel to one of the hyperplanes defining the received signal vectors. The geometric interpretation of this relationship is discussed. Examples with noisy data are presented and refinements to the algorithm are discussed.