Grant: Discovery Grants Program - Individual
McMaster University
$26,000.00
Algorithms for Lattice Basis Reduction and Applications
FY 2015-16
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2014-04252
Name nom
Qiao, Sanzheng
Department département
Computing and Software
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2014
Award amount
26000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
804
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Communication systems and services (planning, organization, services)
Area of application fr
Systèmes et services de communications (planification, organisation et services)
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Partie
2
Nb partie
5
Application title
Algorithms for Lattice Basis Reduction and Applications
Keyword
NSERC
Application summary
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.