{"id":{"repo_id":"mcmaster","oai_identifier":"oai:macsphere.mcmaster.ca:11375/20476"},"canonical_url":"https://search.ndltd.org/etd/mcmaster/oai:macsphere.mcmaster.ca:11375/20476","repository":{"repo_id":"mcmaster","name":"McMaster University","base_url":"https://macsphere.mcmaster.ca/server/oai/request"},"display":{"title":"Lattice Basis Reduction Algorithms and the Subset Sum Problem","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Bo, Yang"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Computing and Software","school":null,"contributors":[],"advisors":["Qiao, Sanzheng"],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016","date_published":"2016","updated_at":"2026-11-18T19:36:15Z","subjects":[],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.71548/16086"],"render_values":[{"text":"https://doi.org/10.71548/16086","href":"https://doi.org/10.71548/16086","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11375/20476","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"http://hdl.handle.net/11375/20476","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://macsphere.mcmaster.ca/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Amacsphere.mcmaster.ca%3A11375%2F20476","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Qiao, Sanzheng"]},{"key":"dc:contributor.department","label":"Department","values":["Computing and Software"]},{"key":"dc:creator","label":"Author","values":["Bo, Yang"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2016-09-23T19:33:39Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2016-09-23T19:33:39Z"]},{"key":"dc:date.issued","label":"Date","values":["2016"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11375/20476","https://doi.org/10.71548/16086"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science (MSc)"]},{"key":"dc:title","label":"Title","values":["Lattice Basis Reduction Algorithms and the Subset Sum Problem"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"dc:contributor.advisor":["Qiao, Sanzheng"],"dc:contributor.department":["Computing and Software"],"dc:creator":["Bo, Yang"],"dc:date.accessioned":["2016-09-23T19:33:39Z"],"dc:date.available":["2016-09-23T19:33:39Z"],"dc:date.issued":["2016"],"dc:description.abstract":["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."],"dc:description.degree":["Master of Science (MSc)"],"dc:identifier.uri":["http://hdl.handle.net/11375/20476","https://doi.org/10.71548/16086"],"dc:language.iso":["en_US"],"dc:title":["Lattice Basis Reduction Algorithms and the Subset Sum Problem"],"dc:type":["Thesis"],"others:access_status":["open.access"]},"updated_at":"2026-11-18T19:36:15Z"}