多変数多項式問題に基づく耐量子暗号の構成と安全性評価

2022年度は、多変数多項式問題に基づく耐量子暗号に関して以下の研究を行った。UOV署名方式に対する秘密鍵に発生したフォルトを利用した攻撃についての研究を、NTT社会情報研究所の清村優太郎氏、東京大学の長澤達也氏、高木剛氏と共に行った。研究成果は、国際会議PQCrypto 2022にて発表された。Unbalanced Oil and Vinegar (UOV)署名方式は、多変数多項式問題に基づいて構成された署名方式であり、その高い安全性から耐量子暗号の有力な候補のひとつであると考えられている。多変数多項式暗号の安全性を評価する上では、公開鍵を入力として署名の偽造や秘密鍵の解読を目的とする代数的な攻撃手法だけでなく、物理的手法を用いた攻撃も考慮する必要がある。フォルト攻撃は、そのような物理攻撃の一種であり、プロトコル内での計算にフォルトを発生させることで秘密情報を抜き出す攻撃手法である。UOV署名方式に対する既存のフォルト攻撃としては、署名生成で用いるランダムな変数を固定する手法や、UOV署名方式の変種に対する秘密鍵に発生したフォルトを利用した攻撃が提案されていた。それに対して本研究では、UOV署名方式に対して、初めて秘密鍵に発生したフォルトを利用したフォルト攻撃を提案することに成功した。本攻撃は、既存のフォルト攻撃のテクニックと新たに提案した代数的な鍵の変形手法の組み合わせによって構成されている。本成果は今後UOV署名方式の社会実装を考える上で大きく影響を与えるものである。

2022年度は、多変数多項式問題に基づく耐量子暗号に関して以下の研究を行った。UOV署名方式に対する秘密鍵に発生したフォルトを利用した攻撃についての研究を、NTT社会情報研究所の清村優太郎氏、東京大学の長澤達也氏、高木剛氏と共に行った。研究成果は、国際会議PQCrypto 2022にて発表された。Unbalanced Oil and Vinegar (UOV)署名方式は、多変数多項式問題に基づいて構成された署名方式であり、その高い安全性から耐量子暗号の有力な候補のひとつであると考えられている。多変数多項式暗号の安全性を評価する上では、公開鍵を入力として署名の偽造や秘密鍵の解読を目的とする代数的な攻撃手法だけでなく、物理的手法を用いた攻撃も考慮する必要がある。フォルト攻撃は、そのような物理攻撃の一種であり、プロトコル内での計算にフォルトを発生させることで秘密情報を抜き出す攻撃手法である。UOV署名方式に対する既存のフォルト攻撃としては、署名生成で用いるランダムな変数を固定する手法や、UOV署名方式の変種に対する秘密鍵に発生したフォルトを利用した攻撃が提案されていた。それに対して本研究では、UOV署名方式に対して、初めて秘密鍵に発生したフォルトを利用したフォルト攻撃を提案することに成功した。本攻撃は、既存のフォルト攻撃のテクニックと新たに提案した代数的な鍵の変形手法の組み合わせによって構成されている。本成果は今後UOV署名方式の社会実装を考える上で大きく影響を与えるものである。