{"id":83184,"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00083184","sets":["581:6644:6832"]},"path":["6832"],"owner":"11","recid":"83184","title":["Finding a Very Short Lattice Vector in the Extended Search Space"],"pubdate":{"attribute_name":"公開日","attribute_value":"2012-07-15"},"_buckets":{"deposit":"0925aee4-1d2d-4d40-adca-3ae825d09129"},"_deposit":{"id":"83184","pid":{"type":"depid","value":"83184","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"Finding a Very Short Lattice Vector in the Extended Search Space","author_link":["358105","358107","358106","358108"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Finding a Very Short Lattice Vector in the Extended Search Space"},{"subitem_title":"Finding a Very Short Lattice Vector in the Extended Search Space","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[一般論文] lattice, approximate SVP, exhaustive search, enumeration","subitem_subject_scheme":"Other"}]},"item_type_id":"2","publish_date":"2012-07-15","item_2_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Dokkyo University"},{"subitem_text_value":"The University of Tokyo"}]},"item_2_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Dokkyo University","subitem_text_language":"en"},{"subitem_text_value":"The University of Tokyo","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"publish_status":"0","weko_shared_id":11,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/83184/files/IPSJ-JNL707027.pdf","label":"IPSJ-JNL707027"},"date":[{"dateType":"Available","dateValue":"2014-07-15"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-JNL707027.pdf","filesize":[{"value":"387.0 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"8"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"3d384a31-8314-4ab0-8ab5-2a7eb573b060","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2012 by the Information Processing Society of Japan"}]},"item_2_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Masaharu, Fukase"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kazunori, Yamaguchi"}],"nameIdentifiers":[{}]}]},"item_2_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Masaharu, Fukase","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kazunori, Yamaguchi","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_2_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN00116647","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_2_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7764","subitem_source_identifier_type":"ISSN"}]},"item_2_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"The problem of finding a lattice vector approximating a shortest nonzero lattice vector (approximate SVP) is a serious problem that concerns lattices. Finding a lattice vector of the secret key of some lattice-based cryptosystems is equivalent to solving some hard approximate SVP. We call such vectors very short vectors (VSVs). Lattice basis reduction is the main tool for finding VSVs. However, the main lattice basis reduction algorithms cannot find VSVs in lattices in dimensions ～200 or above. Exhaustive search can be considered to be a key technique toward eliminating the limitations with current lattice basis reduction algorithms. However, known methods of carrying out exhaustive searches can only work in relatively low-dimensional lattices. We defined the extended search space (ESS) and experimentally confirmed that exhaustive searches in ESS make it possible to find VSVs in lattices in dimensions ～200 or above with the parameters computed from known VSVs. This paper presents an extension of our earlier work. We demonstrate the practical effectiveness of our technique by presenting a method of choosing the parameters without known VSVs. We also demonstrate the effectiveness of distributed searches.\n\n------------------------------ \nThis is a preprint of an article intended for publication Journal of \nInformation Processing(JIP). This preprint should not be cited. This \narticle should be cited as: Journal of Information Processing Vol.20(2012) No.3 (online) \nDOI　http://dx.doi.org/10.2197/ipsjjip.20.785\n------------------------------ \n","subitem_description_type":"Other"}]},"item_2_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"The problem of finding a lattice vector approximating a shortest nonzero lattice vector (approximate SVP) is a serious problem that concerns lattices. Finding a lattice vector of the secret key of some lattice-based cryptosystems is equivalent to solving some hard approximate SVP. We call such vectors very short vectors (VSVs). Lattice basis reduction is the main tool for finding VSVs. However, the main lattice basis reduction algorithms cannot find VSVs in lattices in dimensions ～200 or above. Exhaustive search can be considered to be a key technique toward eliminating the limitations with current lattice basis reduction algorithms. However, known methods of carrying out exhaustive searches can only work in relatively low-dimensional lattices. We defined the extended search space (ESS) and experimentally confirmed that exhaustive searches in ESS make it possible to find VSVs in lattices in dimensions ～200 or above with the parameters computed from known VSVs. This paper presents an extension of our earlier work. We demonstrate the practical effectiveness of our technique by presenting a method of choosing the parameters without known VSVs. We also demonstrate the effectiveness of distributed searches.\n\n------------------------------ \nThis is a preprint of an article intended for publication Journal of \nInformation Processing(JIP). This preprint should not be cited. This \narticle should be cited as: Journal of Information Processing Vol.20(2012) No.3 (online) \nDOI　http://dx.doi.org/10.2197/ipsjjip.20.785\n------------------------------ \n","subitem_description_type":"Other"}]},"item_2_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌"}],"bibliographicIssueDates":{"bibliographicIssueDate":"2012-07-15","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"7","bibliographicVolumeNumber":"53"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"updated":"2025-01-20T06:50:39.179706+00:00","created":"2025-01-18T23:36:46.067123+00:00","links":{}}