Pump and Jump BKZアルゴリズムにおけるジャンプパラメータと簡約基底の質の関係について

• Item type: SIG Technical Reports(1)
• 公開日: 2024-07-15
• タイトル: Pump and Jump BKZアルゴリズムにおけるジャンプパラメータと簡約基底の質の関係について
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: IPSJ-CSEC
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学
• 著者所属: 国立情報学研究所／東京大学
• 著者名: 小谷, 健太朗; 佐藤, 周行
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 基底簡約アルゴリズムは与えられた基底を各基底ベクトルの長さがより均一でより直交する基底に変換する．特に耐量子暗号として有力な LWE 暗号や NTRU 暗号といった格子暗号の解読に用いられ，その性能評価が格子暗号のセキュリティ評価に直結する．現在のセキュリティ評価では BKZ 簡約アルゴリズムが用いられ，特に Pump and Jump BKZ（pnj-BKZ）が LWE 問題の求解チャレンジで記録を更新していることからも最良のものと考えられている．pnj-BKZ においてはジャンプパラメータを増加させることでサブルーチンの Sieving の実行回数を減らして高速化することが可能であり，実際 LWE 問題の求解チャレンジでも利用されているが，jump パラメータの増加が出力基底の質を悪化させることも実験データから指摘されている．本研究ではこの関係について，ジャンプによる Sievging による基底の更新頻度の低下に起因するとして，BKZ シミュレータを用いてその影響を計算し基底の質の悪化を予測した．これを実際の q-ary 格子や LWE 埋め込み格子の簡約の結果と比較したところ，ジャンプパラメータの小さい領域ではおおむね良好な結果となった一方でジャンプパラメータの大きい領域での急激な質の悪化は捉えられなかった．また予測に基づいてジャンプパラメータを最適化すると，実行時間は低下したが先行研究には及ばなかった．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12628305
• 書誌情報: 研究報告セキュリティ心理学とトラスト（SPT）; 巻 2024-SPT-56, 号 19, p. 1-8, 発行日 2024-07-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8671
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会