Algorithms for Lattice Basis Reduction and Applications

Minkowski创立的格基约简算法已经成功地应用于多输入多输出(MIMO)信号检测、GGH(Goldreich，Goldwasser，Halvevi)密码体制解密、全球定位系统(GPS)和符号计算等领域。在MIMO检测中，虽然问题规模小，但实时系统要求快速响应；另一方面，在密码学中，问题规模大，但可以容忍合理的长计算时间。在任何一种情况下，算法对于小问题都是快速的，并且它们的复杂性不会随着问题大小的增加而快速增长。该程序的重点是高效的格基约简算法，产生高质量的结果及其应用。它们可以通过降低误码率而使加拿大研究人员和工业受益，通过改进密码系统在安全性方面以及通过提供快速多项式因式分解而在符号计算中受益。有不同的格基约简概念，其中Minkowski约简是最强的，换句话说，它定义了由最短向量组成的基。其他概念是Minkowski约化的近似。特别是，著名的和广泛使用的LLL(Lenstra，Lenstra，Lovasz)约化方法是快速的，并且在实践中对小尺寸问题产生了与Minkowski约化方法很好的逼近。所有现有的格基缩减方法，如LLL算法，都是基于减少给定格基的向量长度。最近，我们提出了一种全新的方法：基于改进格上给定基向量之间的正交性的Jacobi型方法。在本程序中，我们将从我们最近开发的通用Jacobi基约简法开始，首先对通用算法进行改进，并分析其收敛和复杂性。众所周知，计算最优约简基是一个非多项式时间问题。我们的目标是开发多项式时间的Jacobi型方法，以计算最优解的良好逼近。在实践中，我们还研究了改善中小型问题运行时间的技术。然后，我们研究了格约简辅助MIMO检测和GGH攻击的应用。此外，Jacobi型方法很有吸引力，因为它们本质上是并行的。通过在GPU上实现这些方法，可以获得高性能。在这个程序中，我们还探索了并行格基缩减算法及其GPU实现。我们力求做到最好。我们方法的效率将通过理论复杂性和实际运行时间来衡量。我们的方法的质量将通过常用的正交性缺陷和计算的约简基的条件数来衡量。挑战在于，被认为是最实用的格基约简算法的著名LLL算法将作为我们的比较基准。该计划的长期目标是开发可靠的软件，并将技术转移到通信、安全和软件行业，为加拿大的无线通信、计算机安全以及Maple和Sage等研究和教育软件做出贡献。

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.