多変数多項式暗号の安全性評価と効率的な実装方法の確立

本研究は耐量子計算機公開鍵暗号である多変数多項式暗号の安全性評価、新しい多変数多項式暗号の構築と連立多変数多項式方程式の効率的な解法に関する研究に取り組んでいた。1.安全性評価においては前年度にMinrank問題の効率的な解法について研究に取り組み、既存手法であるKipnis-Shamir法とMinors法のハイブリッド手法を提案した。しかし、その計算量解析は完全に行なっておらず、既存の多変数多項式方式の安全性評価に適用することができなかった。今年度ではその課題を解決ができ、研究成果をまとめて国際会議WISA2020に投稿し、採択された。2.連立多変数多項式方程式の効率的な解法において、Weil降下法を考えた。その手法は拡大体上の多変数多項式系を部分体の新たな多変数多項式系に変形し、部分体の変数の自明な関係式を付け加えてから多項式系を解く手法である。この手法において計算量はまだ完全に研究されていない。本研究はまずWeil降下法から得られる多項式系はSemi-regularではないことを証明した。また、その多項式系の正則性次数を上界である正則性指数と下界である初降次数で見積もることができる。本研究は主にWeil降下法から得られる多項式系の初降次数を調べて、その見積もり方を明らかにした。この結果を国内会議CSS2020に論文発表を行い、国際会議CECC2021に論文投稿をした。3.新しい暗号方式の構築に関して、東京大学の殷昌澤氏と共同研究を行い、新しい署名方式Simple Matrixを提案した。この署名方式は暗号方式ABCと署名方式UOVから閃きを得て提案した。この二つの方式の欠点を補うために、融合して新しい署名方式Simple Matrixを考えた。この署名方式は全ての既存攻撃に耐性を持ち、公開鍵長もUOVより短い。この結果を国際会議IWSEC2021に投稿した。

本研究は耐量子計算機公開鍵暗号である多変数多項式暗号の安全性評価、新しい多変数多項式暗号の構築と連立多変数多項式方程式の効率的な解法に関する研究に取り組んでいた。1.安全性評価においては前年度にMinrank問題の効率的な解法について研究に取り組み、既存手法であるKipnis-Shamir法とMinors法のハイブリッド手法を提案した。しかし、その計算量解析は完全に行なっておらず、既存の多変数多項式方式の安全性評価に適用することができなかった。今年度ではその課題を解決ができ、研究成果をまとめて国際会議WISA2020に投稿し、採択された。2.連立多変数多項式方程式の効率的な解法において、Weil降下法を考えた。その手法は拡大体上の多変数多項式系を部分体の新たな多変数多項式系に変形し、部分体の変数の自明な関係式を付け加えてから多項式系を解く手法である。この手法において計算量はまだ完全に研究されていない。本研究はまずWeil降下法から得られる多項式系はSemi-regularではないことを証明した。また、その多項式系の正則性次数を上界である正則性指数と下界である初降次数で見積もることができる。本研究は主にWeil降下法から得られる多項式系の初降次数を調べて、その見積もり方を明らかにした。この結果を国内会議CSS2020に論文発表を行い、国際会議CECC2021に論文投稿をした。3.新しい暗号方式の構築に関して、東京大学の殷昌澤氏と共同研究を行い、新しい署名方式Simple Matrixを提案した。この署名方式は暗号方式ABCと署名方式UOVから閃きを得て提案した。この二つの方式の欠点を補うために、融合して新しい署名方式Simple Matrixを考えた。この署名方式は全ての既存攻撃に耐性を持ち、公開鍵長もUOVより短い。この結果を国際会議IWSEC2021に投稿した。