グレブナー基底理論を用いた耐量子計算機暗号の安全性解析と開発

点击翻译按钮获取中文摘要

今年度は、耐量子計算機暗号(PQC)の一種である多変数多項式暗号(MPKC)に関する研究を行った。具体的には、MPKCの公開鍵や安全性解析に現れる二次多項式系が生成するイデアルのヒルベルト級数に関する次の二つの研究を行った。(i)UOV方式は安全性の高い署名方式として知られているが、その代数的な性質は十分わかっていない。そこで、UOVの公開鍵に現れる二次多項式系が生成するイデアルのヒルベルト級数に関して、計算機代数ソフトMagmaによる実験を行い、vinegar変数の個数、oil変数の個数、多項式の個数を用いて予測公式を導出した。また、その予測公式を用いてUOVやその変種の安全性解析について考察を行った。これらの結果に関しては、国内シンポジウムCSS2022にて発表を行った。(ii)UOV署名方式の公開鍵が大きいことから、その変種としてQR-UOV署名方式が提案されている。このQR-UOVに対して、BeullensがRainbow方式に関して提案したrectangular attackが適用可能であることを証明した。また、その計算量を見積もるために、攻撃が生成するイデアルのヒルベルト級数を理論的に評価し、実験によりその正しさを検証した。これらの結果は、国内シンポジウムSCIS2023にて発表を行った。以上二つの結果(i)(ii)は論文にまとめて国際会議やジャーナルに投稿する予定である。