• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

A Hybrid Method for Lattice Basis Reduction and Applications

Tian, Zhaofei January 2018 (has links)
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. / Thesis / Doctor of Philosophy (PhD) / 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. 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. We have also investigated two potential applications in MIMO systems and cryptosystems.

Page generated in 0.016 seconds