Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/23465
Title: | A Hybrid Method for Lattice Basis Reduction and Applications |
Authors: | Tian, Zhaofei |
Advisor: | Qiao, Sanzheng |
Department: | Computing and Software |
Keywords: | Lattice;Lattice reduction;LLL algorithm;Jacobi method;MIMO;Cryptography;BKZ 2.0 |
Publication Date: | 2018 |
Abstract: | Lattice reduction aided techniques have been successfully applied to a wide range of applications. Efficient and robust lattice basis reduction algorithms are valuable. In this thesis, we present an O(n^4 logB) hybrid Jacobi method for lattice basis reduction, where n is the dimension of the lattice and B is the maximum length of the input lattice basis vectors. Building upon a generic Jacobi method for lattice basis reduction, we integrate the size reduction into the algorithm to improve its performance. To ensure the convergence and the efficiency of the algorithm, we introduce a parameter to the Lagrange reduction. To improve the quality of the computed bases, we impose a condition on the size reduction, delay the structure restoration, and include a postprocessing in the hybrid method. Our experiments on random matrices show that the proposed algorithm produces better reduced bases than the well-known LLL algorithm and BKZ 2.0 algorithm, measured by both the orthogonality defect and the condition number of the basis matrix. Moreover, our hybrid method consistently runs faster than the LLL algorithm, although they have the same theoretical complexity. We have also investigated two potential applications of the hybrid method. The application simulations show that the hybrid method can improve the stability of the communication channels for Multi-Input Multi-Output systems, and can partially discover the plain text when attacking the GGH cryptosystem. |
URI: | http://hdl.handle.net/11375/23465 |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Tian_Zhaofei_ZT_201712_PhD.pdf | Computer Science Ph.D. thesis | 916.6 kB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.