Back to search

McMaster University

A Hybrid Method for Lattice Basis Reduction and Applications

Abstract

dc:description.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.

Degree

thesis:*
Department dc:contributor.department
Computing and Software
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Tian, Zhaofei
Advisor dc:contributor.advisor
  • Qiao, Sanzheng

Subjects

dc:subject × 7

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Tian, Zhaofei. A Hybrid Method for Lattice Basis Reduction and Applications. 2018. http://hdl.handle.net/11375/23465