多変数多項式暗号に対する理論的安全性解析

多元多项式密码理论安全性分析

• 批准号: 20K19802
• 负责人: 中村 周平
• 金额: $ 2.16万
• 依托单位: Nihon University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K19802/
• 关键词: 多変数多項式暗号; Bi-graded 多項式系; Multi-graded 多項式系; MinRank問題; Kipnis-Shamir手法; 鍵復元攻撃; Rainbow; 直接攻撃; RBS攻撃; Tomae-Wolf algorithm; BIPC問題; Rainbow 暗号; MinRank 問題; 耐量子計算機暗号; グレブナー基底計算; 耐量子暗号

2022年度は, 多変数多項式暗号の安全性に関連して以下の研究を行った. (1) MinRank問題を解くKipnis-Shamir 手法の計算量見積もりを九州大学の池松泰彦 氏, 東芝研究開発センターの王亜成 氏と共に行った. 多変数多項式暗号の中にはMinRank問題に帰着して同値秘密鍵を復元する攻撃があり, MinRank問題を解く効率性がこの攻撃の効率性を左右するため, この問題に対する解析は重要である. 研究結果は学術雑誌IEICE Transactions にて発表された. (2) MinRank問題の困難性を基にした識別方式に関する研究を九州大学の池松泰彦氏, 電気通信大学のバグスサントソ氏, 岡山理科大学の安田貴徳氏と共に行った. 研究結果は国際会議ISITA 2022 にて発表された. (3) 多変数多項式暗号に関する解析はこの数年で大きく進展し, そこで用いられた技術等を統一的に扱う研究を九州大学の池松泰彦氏, 東京大学の高木剛氏と共に行った. 研究結果は学術雑誌IET Information Security にて発表された.

In 2022, the following research was carried out on the security relationship between multiple polynomial codes. (1)MinRank Problem Solution Kipnis-Shamir Method Calculation Quantity See Product The MinRank problem is solved by the attack of the same value secret key in the multi-valued polynomial code. The results of the study are presented in the journal IEICE Transactions. (2)A study on the difficulty of identifying the basis of the MinRank problem was conducted by Yasuhiko Ikematsu of Kyushu University, Takanori Yasuda of Okayama University of Science and Technology. The results of the study were presented at the International Conference ISITA 2022. (3)The analysis of multi-polynomial codes has been progressing for several years, and the use of multi-polynomial codes has been studied by Yasuhiko Ikematsu of Kyushu University and Tsuyoshi Takagi of Tokyo University. The results of the study are academic and IET Information Security Report.

项目成果

Recent Progress in the Security Evaluation of Multivariate Public-Key Cryptography

多元公钥密码安全评估最新进展

• 发表时间: 2023
• 期刊: IET Information Security
• 影响因子: 1.4
• 作者: Y. Ikematsu;S. Nakamura;T. Takagi
• 通讯作者: T. Takagi

多変数多項式暗号における連立代数方程式の求解計算量評価

多元多项式密码学中求解联立代数方程的计算复杂度评估

• 发表时间: 2021
• 作者: Genki Moriya;Kyohei Toyoshima;Chihiro Yukawa;Yuki Nagai;Tomoya Yasunaga;Tetsuya Oda;中村周平
• 通讯作者: 中村周平

暗号における連立代数方程式問題を評価する新しい不変量の検討

密码学中联立代数方程问题的新不变量研究

• 发表时间: 2022
• 作者: 中村周平;横溝恭平
• 通讯作者: 横溝恭平

Improving Thomae-Wolf Algorithm for Solving Underdetermined Multivariate Quadratic Polynomial Problem

• DOI: 10.1007/978-3-030-81293-5_4
• 发表时间: 2021
• 作者: Hiroki Furue;Shuhei Nakamura;T. Takagi

Formal Power Series on Algebraic Cryptanalysis

• 发表时间: 2020-07
• 期刊: ArXiv
• 作者: Shuhei Nakamura