{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00237212","sets":["1164:3925:11477:11663"]},"path":["11663"],"owner":"44499","recid":"237212","title":["シンドローム復号問題に対する量子ISDアルゴリズムの一般化"],"pubdate":{"attribute_name":"公開日","attribute_value":"2024-07-15"},"_buckets":{"deposit":"3065ec91-dca2-414e-abfe-5ff3b6967d08"},"_deposit":{"id":"237212","pid":{"type":"depid","value":"237212","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"シンドローム復号問題に対する量子ISDアルゴリズムの一般化","author_link":["648970","648968","648969","648971"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"シンドローム復号問題に対する量子ISDアルゴリズムの一般化"},{"subitem_title":"A generalization of quantum ISD algorithm for Syndrome Decoding Problem","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"ISEC","subitem_subject_scheme":"Other"}]},"item_type_id":"4","publish_date":"2024-07-15","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"EAGLYS株式会社"},{"subitem_text_value":"千葉大学大学院理学研究院"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"EAGLYS Inc, Research and Development","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Science, Chiba University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/237212/files/IPSJ-CSEC24106006.pdf","label":"IPSJ-CSEC24106006.pdf"},"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-CSEC24106006.pdf","filesize":[{"value":"1.0 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"30"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_login","version_id":"5462e3f8-d177-4a8c-b125-03a647ab9fa7","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2024 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG."}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"若杉, 飛鳥"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"多田, 充"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Asuka, Wakasugi","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Mitsuru, Tada","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11235941","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2188-8655","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"多くの符号ベース暗号の安全性の根拠となっているシンドローム復号問題に対して,最もよく知られている解読アルゴリズムとして,Information Set Decoding (ISD) アルゴリズムがある.Prange によって,1962 年に ISD アルゴリズムは提案され,その後,数多くの変種が知られている.また,2010 年には,Bernstein によって,Grover のアルゴリズムと Prange のアルゴリズムを組合せた量子 ISD アルゴリズムが初めて提案された.本稿では,以前に我々が提案した古典 ISD アルゴリズムの一般化の量子版を与えることで,Bernstein や Kachigar らの量子 ISD アルゴリズムの一般化を提案する.更に,Full Distance Decoding と Half Distance Decoding の 2 つの場合で漸近的な時間計算量と空間計算量を算出し,本アルゴリズムと既存の古典並びに量子 ISD アルゴリズムとの計算量を比較する.結果として,本アルゴリズムの計算量は既存の古典並びに量子 ISD アルゴリズムの計算量よりも小さいことが分かった.","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"The Information Set Decoding (ISD) algorithm is the best-known decoding algorithm for the syndrome decoding problem, which is the basis for the security of many code-based cryptosystems. Prange proposed the ISD algorithm in 1962, and many variants are known since then. Also, in 2010, Bernstein first proposed a quantum ISD algorithm combining the Grover’s algorithm and the Prange’s algorithm. In this paper, we propose a generalization of the quantum ISD algorithm of Bernstein and Kachigar et al. by giving a quantum version of the generalization of our previously proposed classical ISD algorithm. Moreover, we estimate the asymptotic time and space computations for the two cases of Full Distance Decoding and Half Distance Decoding, and compare the complexity of our algorithm with that of previous classical and quantum ISD algorithms. As a result, we find that the computational complexity of our algorithm is smaller than that of existing classical and quantum ISD algorithms.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"7","bibliographic_titles":[{"bibliographic_title":"研究報告コンピュータセキュリティ(CSEC)"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2024-07-15","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"6","bibliographicVolumeNumber":"2024-CSEC-106"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":237212,"updated":"2025-01-19T08:57:24.951846+00:00","links":{},"created":"2025-01-19T01:39:42.914363+00:00"}