講演抄録/キーワード |
講演名 |
2023-05-17 14:45
Module-LWE問題に対する格子の回転構造を利用したBDD列挙法 ○櫻井徳吾・高安 敦(東大) ISEC2023-10 |
抄録 |
(和) |
Module-LWE問題はLWE問題に代数構造を入れた派生形である.2022年7月にはModule-LWE問題をベースとした2つの暗号方式がポスト量子暗号の標準方式として選定されており,近年その解析が活発に行われている重要な問題となっている.Module-LWE問題に対しては,LWE問題と同様に格子のBDD問題に帰着して列挙法を用いて解くという手法があるが,埋め込み法などに比べて非効率であることがわかっている.本稿では,Module-LWE問題に特有の格子の回転構造を利用することによって,列挙法をより効率的に行う手法を提案する.提案手法は,あるパラメータでは既存の列挙法を700倍程度高速化することが推定される.また,計算機実験によって,既存の埋め込み法では500秒の実行時間で20回の試行のうち1回も成功しなかったModule-LWE問題のパラメータに対し,提案手法では同程度の実行時間で20回の試行のうち70%以上で成功することを確認する.つまり,我々の高速化により,Module-LWE問題に対する列挙法は埋め込み法より効率的であるという従来の認識を覆す結果を得る. |
(英) |
Module-LWE is the analog of LWE that includes algebraic structures. In July 2022, two cryptographic schemes based on Module-LWE were selected as standard post-quantum cryptographic algorithms, making it an important problem that has been actively analyzed in recent years. Similar to LWE, one approach for solving Module-LWE is to reduce Module-LWE to BDD on lattice and solve it using enumeration algorithm. In this paper, we propose a more efficient method for enumeration algorithm by using lattice rotation structure specific to Module-LWE. For a certain parameter, it is estimated that our algorithm can speed up the existing enumeration algorithm by about 700 times. Furthermore, we show that our proposed method achieves a success rate of over 70% in 20 trials within about 500 second, while the existing method fails to succeed even once in 20 trials within almost same execution time for a parameter of Module-LWE. That is, our results reverse the conventional understanding that the enumeration method for Module-LWE is less efficient than the embedding method. |
キーワード |
(和) |
Module-LWE問題 / ベクトル回転操作 / BKZ基底簡約アルゴリズム / BDD問題 / 列挙アルゴリズム / / / |
(英) |
Module-LWE / vector rotation / BKZ / BDD / enumeration algorithm / / / |
文献情報 |
信学技報, vol. 123, no. 26, ISEC2023-10, pp. 54-61, 2023年5月. |
資料番号 |
ISEC2023-10 |
発行日 |
2023-05-10 (ISEC) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
ISEC2023-10 |