Advanced search options

Sorted by: relevance · author · university · date | New search

Language: English ^{❌}

You searched for `+publisher:"McMaster University" +contributor:("Qiao, Sanzheng")`

.
Showing records 1 – 3 of
3 total matches.

▼ Search Limiters

McMaster University

1. Bo, Yang. Lattice Basis Reduction Algorithms and the Subset Sum Problem.

Degree: MSc, 2016, McMaster University

URL: http://hdl.handle.net/11375/20476

It is well-known that the subset sum problem is NP-complete, which is the basis for the subset sum based public-key cryptosystems. Some attacks on such cryptosystems have been developed. Those methods reduce the subset sum problem to the problem of finding a shortest Euclidean-norm nonzero vector in a point lattice. In this thesis, we propose a new hybrid lattice basis reduction algorithm by integrating the recent polynomial time Type-I reduction algorithm by Wen Zhang in 2015 with other techniques. We show that our algorithm is well suited for high dimensional lattices and apply it to the subset sum problem. Our experiments demonstrate that our method can solve certain types of the subset sum problems with higher success rates than the most famous existing methods, the Lagarias-Odlyzko attack and the Radziszowski-Kreher attack.

Thesis

Master of Science (MSc)

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Bo, Y. (2016). Lattice Basis Reduction Algorithms and the Subset Sum Problem. (Masters Thesis). McMaster University. Retrieved from http://hdl.handle.net/11375/20476

Chicago Manual of Style (16^{th} Edition):

Bo, Yang. “Lattice Basis Reduction Algorithms and the Subset Sum Problem.” 2016. Masters Thesis, McMaster University. Accessed July 16, 2019. http://hdl.handle.net/11375/20476.

MLA Handbook (7^{th} Edition):

Bo, Yang. “Lattice Basis Reduction Algorithms and the Subset Sum Problem.” 2016. Web. 16 Jul 2019.

Vancouver:

Bo Y. Lattice Basis Reduction Algorithms and the Subset Sum Problem. [Internet] [Masters thesis]. McMaster University; 2016. [cited 2019 Jul 16]. Available from: http://hdl.handle.net/11375/20476.

Council of Science Editors:

Bo Y. Lattice Basis Reduction Algorithms and the Subset Sum Problem. [Masters Thesis]. McMaster University; 2016. Available from: http://hdl.handle.net/11375/20476

McMaster University

2. Tian, Zhaofei. A Hybrid Method for Lattice Basis Reduction and Applications.

Degree: PhD, 2018, McMaster University

URL: http://hdl.handle.net/11375/23465

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.

Subjects/Keywords: Lattice; Lattice reduction; LLL algorithm; Jacobi method; MIMO; Cryptography; BKZ 2.0

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Tian, Z. (2018). A Hybrid Method for Lattice Basis Reduction and Applications. (Doctoral Dissertation). McMaster University. Retrieved from http://hdl.handle.net/11375/23465

Chicago Manual of Style (16^{th} Edition):

Tian, Zhaofei. “A Hybrid Method for Lattice Basis Reduction and Applications.” 2018. Doctoral Dissertation, McMaster University. Accessed July 16, 2019. http://hdl.handle.net/11375/23465.

MLA Handbook (7^{th} Edition):

Tian, Zhaofei. “A Hybrid Method for Lattice Basis Reduction and Applications.” 2018. Web. 16 Jul 2019.

Vancouver:

Tian Z. A Hybrid Method for Lattice Basis Reduction and Applications. [Internet] [Doctoral dissertation]. McMaster University; 2018. [cited 2019 Jul 16]. Available from: http://hdl.handle.net/11375/23465.

Council of Science Editors:

Tian Z. A Hybrid Method for Lattice Basis Reduction and Applications. [Doctoral Dissertation]. McMaster University; 2018. Available from: http://hdl.handle.net/11375/23465

McMaster University

3. Tian, Zhaofei. GGH Cryptosystem and Lattice Reduction Algorithms.

Degree: MSc, 2011, McMaster University

URL: http://hdl.handle.net/11375/15530

The capability of encrypting top secret information remains as a major research problem in the GGH cryptosystem, which depends on various attacking methods. The early approaches to attacking the GGH cryptosystem mainly relied on special properties of the lattice generated by the vectors of the private key. Consequently, those attacks are not appropriate for general cases. This thesis presents a GGH attacking method for general cases. A lattice basis reduction algorithm is applied to the public key to get a better basis, which is used to decrypt the ciphertext. In the proposed approach, we concentrate on three lattice reduction algorithms: the LLL algorithm, the approximate optimally-reduced algorithm, and the optimally-reduced algorithm. We have implemented a package in MATLAB for the GGH cryptosystem and the three algorithms. We experimented with two groups of experiments and obtained promising results for lattices of low dimensions.

Thesis

Master of Science (MSc)

Subjects/Keywords: encrypting; top secret information; GGH cryptosystem; lattice

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Tian, Z. (2011). GGH Cryptosystem and Lattice Reduction Algorithms. (Masters Thesis). McMaster University. Retrieved from http://hdl.handle.net/11375/15530

Chicago Manual of Style (16^{th} Edition):

Tian, Zhaofei. “GGH Cryptosystem and Lattice Reduction Algorithms.” 2011. Masters Thesis, McMaster University. Accessed July 16, 2019. http://hdl.handle.net/11375/15530.

MLA Handbook (7^{th} Edition):

Tian, Zhaofei. “GGH Cryptosystem and Lattice Reduction Algorithms.” 2011. Web. 16 Jul 2019.

Vancouver:

Tian Z. GGH Cryptosystem and Lattice Reduction Algorithms. [Internet] [Masters thesis]. McMaster University; 2011. [cited 2019 Jul 16]. Available from: http://hdl.handle.net/11375/15530.

Council of Science Editors:

Tian Z. GGH Cryptosystem and Lattice Reduction Algorithms. [Masters Thesis]. McMaster University; 2011. Available from: http://hdl.handle.net/11375/15530