多変数連立方程式の求解困難性を基にした耐量子暗号の安全性評価

基于多元联立方程求解难度的抗量子密码安全性评估

• 批准号: 19K20266
• 负责人: 池松 泰彦
• 金额: $ 2.33万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19K20266/
• 关键词: 耐量子計算機暗号; 多変数多項式暗号; MinRank問題; グレブナー基底; 暗号理論; 多変数多項式公開鍵暗号; 応用数学

今年度は、主に以下の3つ研究を行った。(i) pq法と呼ばれるMPKCの安全性を高める格子論的手法は二次多項式からなる公開鍵に対して適用されている。このことによってグレブナー基底攻撃などに弱い方式の安全性を強化できることが知られている。そこでこのアイデアを用いて、一次多項式からなる単純な暗号方式にその手法を適用した場合のMPKCの安全性について考察を行った。さらに、Ring-LWEのアイデアを使い鍵削減を行い、効率的な暗号方式を構成した。この結果は国際会議ProvSec2022で発表した。(ii) Daniel Smith-ToneによってPQC2022で提案された2F法 (NTRUのmodular switchingのアイデアを使って既存のMPKC方式の安全性を強化する手法)の安全性解析を行った。二次多項式の係数の個数と多項式の個数にギャップがあることに着目し、より小さい次元の格子基底簡約アルゴリズムを使うことができることがわかり、2F法が安全でないことがわかった。また、2F法で得られる128ビット安全性パラメータをもつ暗号方式に対して、標準的なPCで1時間以内で2F法を無力化できることを実験で確かめた。この結果は応用数理学会で発表を行った。(iii) 昨年度に引き続き、MinRank問題に基づいたID方式の安全性解析、署名方式の提案について研究を行った。ID方式については対応するMinRank問題の安全性解析をもとにパラメータ導出を行い、国際会議ISITA2022で発表を行った。

This year, the following three research projects were carried out. (i)The security of MPKC is higher than that of pq method, and the method of lattice theory is applicable to quadratic polynomials. The security of the base attack is enhanced in a weak way. The security of MPKC is investigated in the following cases: In addition, Ring-LWE's missing key is used to reduce the number of lines and rates. The results of the conference were presented at ProvSec2022. (ii)Daniel Smith-Tone developed the PQC2022 proposal for security analysis using the 2F method (NTRU modular switching and enhancement of existing MPKC methods). The number of coefficients of quadratic polynomials and the number of polynomials are the same. The lattice basis of quadratic polynomials is reduced. The 2F method is safe. The 2F method is valid for 128 hours. The security method is valid for 1 hour. The results of this study are presented in the form of a mathematical society. (iii)Last year's research was conducted on the basis of ID security analysis and signature proposal. ID mode is used to resolve MinRank issues, and the International Conference ISITA2022 is used.

项目成果

同種写像パス探索問題に対する中間一致攻撃のハイブリッド手法

均匀映射路径搜索问题的中间匹配攻击混合方法

• 发表时间: 2020
• 作者: 宮島敬明;上野知洋;佐野健太郎;Xiaolan Gu;池松泰彦
• 通讯作者: 池松泰彦

On the First Fall Degrees of Small Field Type MPKCs

论小场型MPKC的首次下降度

• 发表时间: 2020
• 作者: 中村周平;池松泰彦;王亜成
• 通讯作者: 王亜成

Three-Pass Identification Scheme Based on MinRank Problem with Half Cheating Probability

基于半作弊概率MinRank问题的三遍识别方案

• 发表时间: 2022
• 期刊: International Symposium on Information Theory and Its Applications (ISITA) 2022
• 作者: Bagus Santoso;Yasuhiko Ikematsu;Shuhei Nakamura;Takanori Yasuda
• 通讯作者: Takanori Yasuda

A study of the Kipnis-Shamir approach against the Rainbow signature scheme

针对彩虹签名方案的 Kipnis-Shamir 方法的研究

• 发表时间: 2022
• 作者: Yuki Horie;Do Thi Thu Hien;Kien Nguyen;Hiroo Sekiya;池松泰彦
• 通讯作者: 池松泰彦

A Vulnerability on an Efficient Signature Generation Using Precomputation for UOV

UOV预计算高效签名生成的漏洞

• 发表时间: 2020
• 作者: Kien Nguyen;Hiroo Sekiya;池松 泰彦
• 通讯作者: 池松 泰彦