東大など、量子コンピュータでも解読不能なデジタル署名技術「QR-UOV」を開発

東京大学、九州大学(九大)、科学技術振興機構の3者は11月24日、量子コンピュータでも解読できない新たなデジタル署名技術を開発し、既存の方式と比較して約3分の1まで公開鍵のデータサイズを削減することに成功したと発表した。

同成果は、東大大学院情報理工学系研究科数理情報学専攻の高木剛教授、同・古江弘樹大学院生、九州大学マス・フォア・インダストリ研究所の池松泰彦助教、NTT社会情報研究所の清村優太郎研究員らの共同研究チームによるもの。詳細は、2021年12月6日から10日にかけてオンライン開催される国際暗号学会主催の国際会議「International Conference on the Theory and Application of Cryptology and Information Security(Asiacrypt 2021)」にて12月6日に発表される予定だという。

暗号技術は現在の情報社会の安全性を支える重要なコア技術だが、本格的な量子コンピュータが実現されれば、現在のRSA暗号や楕円曲線暗号などは容易に解読させてしまう危険性があるとされており、新たな量子コンピュータでも解読できない暗号技術が求められている。そうした次世代暗号技術の実用化に向けて世界中で開発が進められており、中でも多変数多項式問題の難しさを安全性の根拠とした「Rainbow署名」が注目を集めている。

ただしRainbow署名は、安全性の高い「UOV署名」(1999年提案)をマルチ階層構造として拡張することにより効率化したものだが、検証の際に使用する公開鍵のデータサイズが大きくなるという点が課題となっていた。

それに対し、研究チームが今回開発した「QR-UOV署名」は、数値の行列で表現されていたUOV署名の公開鍵を「剰余環」といわれる代数系の多項式として表現することにより、安全性を低下させることなく公開鍵のデータサイズを削減することに成功したとする。

具体的には、実用的に安全性が十分に高いパラメータにおいてRainbow署名と比較したところ、公開鍵のデータサイズを約Rainbow署名の252.3KBであった公開鍵のデータサイズを85.8KBまで削減することができたという。

提案方式の剰余環による公開鍵データサイズの削減 (出所:共同プレスリリースPDF)

デジタル署名技術は、個人認証やデータの保護など情報セキュリティの向上を目的として広く利用されており、今回の技術についても、長期的な安全性が必要であり通信負荷の低減が求められるセキュリティシステムへの応用が期待できると研究チームでは説明している。また、米国標準技術研究所NISTは量子コンピュータに対して安全な暗号方式の標準化プロジェクトを現在進めており、デジタル署名技術に関しても2022年に再公募を行う計画を発表していることから、研究チームでは、QR-UOV署名を、NISTの暗号標準化プロジェクトに応募し、標準規格への採択を目指すとしている。