| 講演名 | 2020-05-20 メモリ制限下における量子Information Set Decodingアルゴリズムの高速化 木村 直人(東大), 高安 敦(NICT), 高木 剛(東大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 耐量子暗号のひとつである符号暗号方式の安全性は，シンドローム復号問題の困難性と関連がある．シンドローム復号問題を解く代表的なアルゴリズムとしてPrange によって提案されたInformation Set Decoding (ISD) アルゴリズムが知られている．これまで，指数的に大きなリストを活用することで高速化した様々な改良ISD アルゴリズムが提案されてきた．さらに，Bernstein (PQCrypto 2010) とKachigar-Tillich (PQCrypto 2017) はGrover のアルゴリズムと量子ウォークを既存のISD アルゴリズムに適用することで高速化した量子ISD アルゴリズムを提案した．ただし，これらの量子ISD アルゴリズムは，古典ISD アルゴリズムと同様指数的に大きなリストを用いるうえ，それらを量子状態で保持しておかなければならない．本稿で我々は，Both の古典ISD アルゴリズム(Ph.D. thesis 2018)，Grover のアルゴリズム，Kirshanova の量子ウォーク(PQCrypto 2018) を組み合わせることで新たな量子ISD アルゴリズムを提案する．提案アルゴリズムは，既存の量子ISD アルゴリズムと同様指数的に大きなリストを量子状態で保持するが，リストサイズはずっと小さくなっている．そのため，十分にメモリがあるときには既存アルゴリズムよりも低速だが，メモリが制限されているときには最も高速である．この性質により，実際に量子計算機で実行するときには提案アルゴリズムが最も高速になると考えられる． |
| 抄録(英) | The security of code-based cryptoststems relates to the hardness of the syndrome decoding problem. The best decoding algorithms are known as information set decoding (ISD) algorithms proposed by E. Prange. In this paper, we propose a quantum ISD algorithm based on the L. Both ISD algorithm (PhD thesis, 2018) and the E. Kirshanova quantum walk (PQCrypto 2018). This results in an improvement of time complexity in the condition of low memory compared with existing quantum ISD algorithms. |
| キーワード(和) | シンドローム復号問題 / Information Set Decoding (ISD) アルゴリズム / Grover のアルゴリズム / 量子 ウォーク |
| キーワード(英) | Syndrome Decoding Problem / Information Set Decoding (ISD) Algorithm / Grover Algorithm / Quantum Walk |
| 資料番号 | ISEC2020-3 |
| 発行日 | 2020-05-13 (ISEC) |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2020/5/20(から1日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 委員長氏名（和） | 盛合 志帆(NICT) |
| 委員長氏名（英） | Shiho Moriai(NICT) |
| 副委員長氏名（和） | 廣瀬 勝一(福井大) / 伊豆 哲也(富士通研) |
| 副委員長氏名（英） | Shoichi Hirose(Univ. of Fukui) / Tetsuya Izu(Fujitsu Labs.) |
| 幹事氏名（和） | 江村 恵太(NICT) / 面 和成(筑波大) |
| 幹事氏名（英） | Keita Emura(NICT) / Kazunari Omote(Tsukuba Univ.) |
| 幹事補佐氏名（和） | 山本 大(富士通研) / 須賀 祐治(インターネットイニシアティブ) |
| 幹事補佐氏名（英） | Dai Yamamoto(Fujitsu Labs.) / Yuuji Suga(IIJ) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Security |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | メモリ制限下における量子Information Set Decodingアルゴリズムの高速化 |
| サブタイトル（和） | |
| タイトル（英） | Improved Quantum Information Set Decoding Algorithm with Low Memory |
| サブタイトル（和） | |
| キーワード(1)（和/英） | シンドローム復号問題 / Syndrome Decoding Problem |
| キーワード(2)（和/英） | Information Set Decoding (ISD) アルゴリズム / Information Set Decoding (ISD) Algorithm |
| キーワード(3)（和/英） | Grover のアルゴリズム / Grover Algorithm |
| キーワード(4)（和/英） | 量子 ウォーク / Quantum Walk |
| 第 1 著者 氏名（和/英） | 木村 直人 / Naoto Kimura |
| 第 1 著者 所属（和/英） | 東京大学(略称：東大) The University of Tokyo(略称：Univ. Tokyo) |
| 第 2 著者 氏名（和/英） | 高安 敦 / Atsushi Takayasu |
| 第 2 著者 所属（和/英） | 情報通信研究機構(略称：NICT) National Institute of Information and Communications Technology(略称：NICT) |
| 第 3 著者 氏名（和/英） | 高木 剛 / Tsuyoshi Takagi |
| 第 3 著者 所属（和/英） | 東京大学(略称：東大) The University of Tokyo(略称：Univ. Tokyo) |
| 発表年月日 | 2020-05-20 |
| 資料番号 | ISEC2020-3 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | ISEC-28 |
| ページ範囲 | pp.15-22(ISEC), |
| ページ数 | 8 |
| 発行日 | 2020-05-13 (ISEC) |