Algorithms for Lattice Basis Reduction and Applications

点击翻译按钮获取中文摘要

Lattice basis reduction, founded by Minkowski, has been successfully applied to numerous areas, such as Multi-Input Multi-Output (MIMO) signal detection, the GGH (Goldreich, Goldwasser, Halvevi) cryptosystem decryption, Global Positioning Systems (GPS) and symbolic computation.In MIMO detection, although the problem size is small, the real-time system demands quick response, On the other hand, in cryptography, the problem size is large, but reasonably long computation time can be tolerated. In either case, algorithms that are fast for small problems and their complexity does not grow fast as the problem size increases are necessary. The focus of this program is efficient lattice basis reduction algorithms that produce good quality results and their applications. They can benefit Canadian researchers and industry in communications by reducing bit error rate, in security by improving cryptography systems and in symbolic computation by providing fast polynomial factorizations.There are different notions of lattice basis reduction, among which the Minkowski reduction is the strongest, in other words, it defines a basis consisting of shortest vectors. The other notions are approximations of the Minkowski reduction. In particular, the famous and widely used LLL (Lenstra, Lenstra, Lovasz) reduction method is fast and produces good approximations of the Minkowski reduction in practice for small size problems. All existing lattice basis reduction methods, like the LLL algorithm, are based on reducing the vector lengths of a given basis for a lattice. Recently, we proposed a completely new approach: Jacobi-type methods based on improving the orthogonality between given basis vectors for a lattice. In this program, starting from our recently developed generic Jacobi method for basis reduction, we will first improve the generic algorithm and analyze its convergence and complexity. It is known that computing an optimally reduced basis is a non-polynomial time problem. Our goal is to develop polynomial time Jacobi-type methods that compute good approximations of an optimal solution. Practically, we also investigate techniques to improve running time for small to moderate size problems. We then investigate applications in lattice reduction aided MIMO detection and GGH attacks. Moreover, Jacobi-type methods are attractive, because they are inherently parallel. High performance can be achieved by implementing the methods on GPUs. In this program, we also explore parallel lattices basis reduction algorithms and their GPU implementations. We strive for the best. The efficiency of our methods will be measured by both theoretical complexity and practical running time. The quality of our methods will be measured by the commonly used orthogonality defect and the condition number of the computed reduced bases. The challenge is that the well-known LLL algorithm, which is regarded as the best practical lattice basis reduction algorithm, will be used as our comparison benchmark.The long-term goal of the program is to develop a reliable software and transfer the technology to communication, security, and software industries, contributing to wireless communications, computer security, and softwares like Maple and Sage for research and education in Canada.