@techreport{oai:ipsj.ixsq.nii.ac.jp:00237212,
 author = {若杉, 飛鳥 and 多田, 充 and Asuka, Wakasugi and Mitsuru, Tada},
 issue = {6},
 month = {Jul},
 note = {多くの符号ベース暗号の安全性の根拠となっているシンドローム復号問題に対して，最もよく知られている解読アルゴリズムとして，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.},
 title = {シンドローム復号問題に対する量子ISDアルゴリズムの一般化},
 year = {2024}
}