| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2020-05-20 10:45 メモリ制限下における量子Information Set Decodingアルゴリズムの高速化 ○木村直人（東大）・高安 敦（NICT）・高木 剛（東大）  ISEC2020-3 |
|
| 抄録 | （和） | 耐量子暗号のひとつである符号暗号方式の安全性は，シンドローム復号問題の困難性と関連がある．シンドローム復号問題を解く代表的なアルゴリズムとして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 / / / / | |
| 文献情報 | 信学技報, vol. 120, no. 28, ISEC2020-3, pp. 15-22, 2020年5月. | |
| 資料番号 | ISEC2020-3 | |
| 発行日 | 2020-05-13 (ISEC) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2020-3 |
|
| 研究会情報 | |
| 研究会 | ISEC |
| 開催期間 | 2020-05-20 - 2020-05-20 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2020-05-ISEC |
| 本文の言語 | 日本語 |
| タイトル（和） | メモリ制限下における量子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 |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第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) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2020-05-20 10:45:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | ISEC2020-3 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | no.28 |
| ページ範囲 | pp.15-22 |
| ページ数 | 8 |
| 発行日 | 2020-05-13 (ISEC) |
[研究会発表申込システムのトップページに戻る]