| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2024-07-22 13:50 シンドローム復号問題に対する量子ISDアルゴリズムの一般化 ○若杉飛鳥（EAGLYS）・多田 充（千葉大）  ISEC2024-10 SITE2024-7 BioX2024-20 HWS2024-10 ICSS2024-14 EMM2024-16 |
|
| 抄録 | （和） | 多くの符号ベース暗号の安全性の根拠となっているシンドローム復号問題に対して，最もよく知られている解読アルゴリズムとして，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 アルゴリズムの計算量よりも小さいことが分かった． |
| （英） | 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. |
|
| キーワード | （和） | 符号ベース暗号 / シンドローム復号問題 / ISDアルゴリズム / Amplitude Amplification / / / / |
| （英） | Code-based cryptography / Syndrome Decoding Problem / ISD algorithm / Amplitude Amplification / / / / | |
| 文献情報 | 信学技報, vol. 124, no. 120, ISEC2024-10, pp. 16-22, 2024年7月. | |
| 資料番号 | ISEC2024-10 | |
| 発行日 | 2024-07-15 (ISEC, SITE, BioX, HWS, ICSS, EMM) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2024-10 SITE2024-7 BioX2024-20 HWS2024-10 ICSS2024-14 EMM2024-16 |
|
| 研究会情報 | |
| 研究会 | EMM BioX ISEC SITE ICSS HWS IPSJ-CSEC IPSJ-SPT |
| 開催期間 | 2024-07-22 - 2024-07-23 |
| 開催地（和） | 札幌コンベンションセンター |
| 開催地（英） | Sapporo Convention Center |
| テーマ（和） | セキュリティ、一般 （セキュリティサマーサミット2024） |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2024-07-EMM-BioX-ISEC-SITE-ICSS-HWS-CSEC-SPT |
| 本文の言語 | 日本語 |
| タイトル（和） | シンドローム復号問題に対する量子ISDアルゴリズムの一般化 |
| サブタイトル（和） | |
| タイトル（英） | A generalization of quantum ISD algorithm for Syndrome Decoding Problem |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 符号ベース暗号 / Code-based cryptography |
| キーワード(2)（和/英） | シンドローム復号問題 / Syndrome Decoding Problem |
| キーワード(3)（和/英） | ISDアルゴリズム / ISD algorithm |
| キーワード(4)（和/英） | Amplitude Amplification / Amplitude Amplification |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 若杉 飛鳥 / Asuka Wakasugi / ワカスギ アスカ |
| 第1著者 所属（和/英） | EAGLYS株式会社 (略称： EAGLYS) EAGLYS Inc, (略称： EAGLYS) |
| 第2著者 氏名（和/英/ヨミ） | 多田 充 / Mitsuru Tada / |
| 第2著者 所属（和/英） | 千葉大学 (略称： 千葉大) Chiba University (略称： Chiba Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2024-07-22 13:50:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | ISEC2024-10, SITE2024-7, BioX2024-20, HWS2024-10, ICSS2024-14, EMM2024-16 |
| 巻番号（vol） | vol.124 |
| 号番号（no） | no.120(ISEC), no.121(SITE), no.122(BioX), no.123(HWS), no.124(ICSS), no.125(EMM) |
| ページ範囲 | pp.16-22 |
| ページ数 | 7 |
| 発行日 | 2024-07-15 (ISEC, SITE, BioX, HWS, ICSS, EMM) |
[研究会発表申込システムのトップページに戻る]