Module-LWEに対するχ²検定を用いた攻撃

• Item type: SIG Technical Reports(1)
• 公開日: 2023-02-27
• タイトル: Module-LWEに対するχ²検定を用いた攻撃
• タイトル / 言語: en
• タイトル: Attacks on Module-LWE problem by using χ² test
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 耐量子計算機暗号
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 現在，大阪大学工学部
• 著者所属: 現在，大阪大学大学院工学研究科
• 著者所属: 現在，大阪大学大学院工学研究科／現在，北陸先端科学技術大学院大学
• 著者所属(英): en
• 著者所属(英): Presently with Osaka University School of Engineering
• 著者所属(英): en
• 著者所属(英): Presently with Osaka University Graduate School of Engineering
• 著者所属(英): en
• 著者所属(英): Presently with Osaka University Graduate School of Engineering / Presently with Japan Advanced Institute of Science and Technology
• 著者名: 川田, 元; 奥村, 伸也; 宮地, 充子
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Module-LWE 問題の困難性に基づく暗号は NIST で耐量子計算機暗号標準のひとつに選ばれるなど有用性が高いとされている．耐量子計算機暗号といえど，安全性は一様でないため，耐量子計算機暗号に対して攻撃を行うことで，安全性解析が行われている．本研究では Module-LWE 問題に対して攻撃を行う．既存研究で Module-LWE 問題における秘密鍵ベクトルの次元を 1 に限定した Ring-LWE 探索問題に対して Chen らによりフロベニウス写像を用いることで計算量を削減した x2 攻撃が提案されている．それらの計算量削減手法を踏まえて，まず一般の相対次数 f の Module-LWE 問題への攻撃を行える x2 攻撃手法を提案する．次に Module-LWE 問題に対して相対次数が f=2 のときにフロベニウス写像を用いて攻撃を行い，攻撃に必要なサンプル数を削減する手法を提案する．提案する二つの手法について，一般の相対次数への攻撃手法では現実的な時間では解読できなかった問題が，フロベニウス写像を用いる手法では短時間で解読できることが確認された．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Cryptography based on the difficulty of the Module-LWE problem has been selected by NIST as one of the standards for post-quantum computer cryptography, and is considered to be highly useful. Since the security of post-quantum computer cryptography is not uniform, attacks against post-quantum computer cryptography have been conducted to analyze the security of such cryptography. In this study, we attack the Module-LWE problem. In an existing study, Chen et al. proposed a chi-square attack on the Ring-LWE search problem with the dimension of the secret key vector in the Module-LWE problem limited to one by using a Frobenius map to reduce the computational complexity. Based on these reduction methods, we first propose a x2 attack method that can be applied to Module-LWE problem that has general relative degrees f . Next, we propose a method to attack the Module-LWE problem with a Frobenius map when the relative degree is f = 2, thereby reducing the number of samples required for the attack. It is confirmed that the two proposed methods can solve the problem in a short time by using the Frobenius map, while the general attack on the relative degree cannot be solved in a realistic time.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11235941
• 書誌情報: 研究報告コンピュータセキュリティ（CSEC）; 巻 2023-CSEC-100, 号 46, p. 1-6, 発行日 2023-02-27
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8655
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会