三分木を用いたMeet-LWE攻撃の改良

• Item type: Symposium(1)
• 公開日: 2024-10-15
• タイトル / 言語: ja
• タイトル: 三分木を用いたMeet-LWE攻撃の改良
• タイトル / 言語: en
• タイトル: Revisiting the Meet-LWE Attack
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 電気通信大学
• 著者所属: 誠信女子大学校
• 著者所属: 誠信女子大学校
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Sungshin Women's University
• 著者所属(英): en
• 著者所属(英): Sungshin Women's University
• 著者名: 王, イントウ; 李, 恩岷; 李, 珠姬
• 著者名(英): Yuntao, Wang; Eunmin, Lee; Joohee, Lee
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Learning with Errors （LWE） 問題およびその変種は，構造化格子上で効率的な耐量子計算機暗号システムに広く採用されている．CRYPTO 2021にてMayはMeet-LWE攻撃を提案し，三進秘密鍵のLWEに対するMeet-in-the-Middleアプローチを用いたLWEの解析において重要な進展を示した．本研究では，三分木を導入することによりMeet-LWE攻撃を拡張し，秘密ベクトルのより多様な表現が可能となる．具体的には，秘密ベクトルを同次元で三分木に分割し展開することで，表現の増加を利用し，攻撃の複雑性全体を漸近的にS0.25からS0.21まで抑えられる(Sは探索スペースとなる)．また，いくつか耐量子計算機暗号に対し，我々の攻撃による実行時間・メモリコストの非漸近的な評価でMeet-LWE攻撃より 29.9%までセキュリティのビット数が削減された．さらに，韓国における耐量子計算機暗号標準化プロジェクトのラウンド2においた候補の推奨パラメータに対してセキュリティを評価し，攻撃複雑性が主張されたものよりも低いことを報告する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The Learning with Errors (LWE) problem with its variants over structured lattices has been widely exploited in efficient post-quantum cryptosystems. In CRYPTO 2021, May proposed the Meet-LWE attack, which poses a significant advancement in the line of work on the Meet-in-the-Middle approach to analyze LWE with ternary secrets. In this work, we improve Meet-LWE by introducing ternary trees, which result in diverse representations of the secrets. More precisely, we split the secrets into three pieces with the same dimension and expanded them into a ternary tree to leverage the increased representations to improve the overall attack complexity. With asymptotic and non-asymptotic comparisons, our attack provides significantly improved estimations for all parameter settings, including those of the practical post-quantum schemes, compared to the Meet-LWE attack.
• 書誌情報: コンピュータセキュリティシンポジウム2024論文集; p. 891-898, 発行日 2024-10-15
• 出版者 / 言語: ja
• 出版者: 情報処理学会