東京大学は11月24日、量子コンピューターでも解読できない多変数公開鍵暗号のデジタル署名技術「QR-UOV署名」を開発し、公開鍵のデータサイズを既存方式と比較して約1/3まで削減することに成功したと発表した。「多変数多項式問題の難しさ」を安全性の根拠にしているとのこと。多変数多項式問題とは、n個の変数を持つm個の2次多項式の共通解を計算する問題で、nとmを同程度の大きさで増加させた場合に計算が困難となることが知られている。
これは、東京大学大学院情報理工学系研究科の高木剛教授と古江弘樹氏、九州大学マス・フォア・インダストリ研究所、日本電信電話（NTT）の共同研究によるもの。現代の情報社会では、暗号技術はきわめて重要な存在だが、現在多く使われているRSA暗号（素因数分解の難しさを安全性の根拠とする暗号方式）と楕円曲線暗号（楕円曲線といわれる幾何的な構造を利用した暗号方式。ECDSAなど）という2つの技術は、大規模な量子コンピューターが実現すると解読されてしまうことがわかっている。そこで、量子コンピューターでも解読できない多変数多項式問題の難しさを安全性の根拠としたRainbow署名という方式が開発されたが、検証に利用する公開鍵のサイズが大きくなるという課題があった。
Rainbow署名は、多変数多項式問題を基にし、20年以上も本質的な解読法が報告されていない安全な方式とされるUOV署名を拡張したものだが、今回開発されたのは、数値の行列で表現されていたUOV署名の公開鍵を剰余環といわれる代数系の多項式で表現しデータサイズを削減した「QR-UOV署名」というもの。Rainbow署名と比較して、公開鍵のデータサイズは約66％削減できた。
QR-UOV署名は、大規模な量子コンピューターが普及した社会でも、安全で効率的なデジタル署名方式として利用でき、特に「長期的な安全性が必要であり通信負荷の低減が求められるセキュリティーシステムへの応用」が期待されるという。
研究グループは、安全な暗号方式の標準化プロジェクトを進める米国標準技術研究所（NIST）が2022年に行う予定のデジタル署名技術の公募に応募し、標準規格への採択を目指すとのことだ。
