Algorithms for Lattice Basis Reduction and Applications

格基约简算法及应用

• 批准号: RGPIN-2014-04252
• 负责人: Qiao, Sanzheng
• 金额: $ 1.89万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=587694
• 关键词: Algorithms; Lattice; Basis; Reduction; 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.

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