シンドローム復号問題に対する量子ISDアルゴリズムの一般化

• Item type: SIG Technical Reports(1)
• 公開日: 2024-07-15
• タイトル: シンドローム復号問題に対する量子ISDアルゴリズムの一般化
• タイトル / 言語: en
• タイトル: A generalization of quantum ISD algorithm for Syndrome Decoding Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: ISEC
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: EAGLYS株式会社
• 著者所属: 千葉大学大学院理学研究院
• 著者所属(英): en
• 著者所属(英): EAGLYS Inc, Research and Development
• 著者所属(英): en
• 著者所属(英): Graduate School of Science, Chiba University
• 著者名: 若杉, 飛鳥; 多田, 充
• 著者名(英): Asuka, Wakasugi; Mitsuru, Tada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 多くの符号ベース暗号の安全性の根拠となっているシンドローム復号問題に対して，最もよく知られている解読アルゴリズムとして，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 アルゴリズムの計算量よりも小さいことが分かった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11235941
• 書誌情報: 研究報告コンピュータセキュリティ（CSEC）; 巻 2024-CSEC-106, 号 6, p. 1-7, 発行日 2024-07-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8655
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会