講演抄録/キーワード |
講演名 |
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 |