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

今年度は、主に以下の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で発表を行った。

今年度は、主に以下の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で発表を行った。