池上 輝
近年, 量子計算機の発展により既存の公開伴暗号の安全性が脅かされる懸念から, 耐量子計算機暗号の有力候補である格子暗号がその安全性を根拠とする Ring-Learning with Errors (Ring-LWE) 問題の安全性評価は重要な課題である. Ring-LWE 問題には,ランダムサンプルと Ring-LWE サンプルの判別を行う識別問題と秘密伴を復元する探索問題の 2 種類が存在する. LWE 探索問題の解読手法である Blum-Kalai-Wasserman (BKW) アルゴリズムは, サンプルの次元を削減する Sample-reduction ステップ, 次元削減されたサンプルから秘密伴成分を推定する Hypothesis-testing ステップ,および残りの成分を決定する Back-substitution ステップの 3 つで構成される. BKW アルゴリズムを用いた秘密伴復元において, 最終的な復元性能は Sample-reduction ステップで確保されるサンプル数と蓄積されるエラーの大きさに大きく依存する. Ring-LWE 問題に対しては, 環構造を利用して BKW アルゴリズムを拡張した Ring-BKW アルゴリズムが提案されている. 廣瀬らの研究では, ブロックサイズの動的な決定によりサンプル数の確保に成功しているが, 後続の秘密伴の特定や, エラーの増大を踏まえた成功確率の評価には至っていない. また, 従来の Ring-LWE 問題に対する Hypothesis-testing ステップは標準的な LWE 問題のアルゴリズムを流用するにとどまっており, 多項式環としての代数的構造を十分に活用できているとは言い難い. 本研究では, 動的ブロックサイズを導入した Ring-BKW アルゴリズムの Sample-reduction ステップで得られたサンプルを用い, 秘密伴復元まで実施する. 具体的には, 動的ブロックサイズ制御により生成されたサンプルに対し, Ring-LWE の環構造を考慮し, 多次元 FFT を用いた複数係数利用型の Hypothesis-testing ステップを適用し, 秘密伴復元を試みる. 復元成功率の評価を通じて, 秘密伴復元に適したパラメータを明らかにし, ブロックサイズの選択が復元性能に与える影響を考察する.
