量子コンピュータでも解読できない安全な暗号技術を開発

東京大学大学院情報理工学系研究科と九州大学マス・フォア・インダストリ研究所は、日本電信電話株式会社と共同で、量子コンピュータでも解読できない新たなデジタル署名技術を開発し、既存の方式と比較して約 3 分の 1 まで公開鍵のデータサイズを削減することに成功しました。

今回開発したデジタル署名技術「QR-UOV 署名」は、多変数多項式問題の難しさを安全性の根拠としており、公開鍵および署名のデータサイズが小さいことが特徴です。量子コンピュータの時代においても安全かつ効率的な暗号技術として、個人認証やデータ保護などに利活用が可能となります。

この研究成果は、国際暗号学会主催の国際会議「International Conference on the Theory and Application of Cryptology and Information Security（Asiacrypt 2021）」（2021 年 12 月 6 日‐10 日 オンライン開催）において発表します。

発表のポイント

◆成果：量子コンピュータでも解読できない新しい暗号技術を開発しました。
◆新規性：データサイズが小さい効率的なデジタル署名となります。
◆社会的意義、将来の展望：量子コンピュータの時代にも安全に利用できる効率的な暗号技術として、個人認証やデータ保護などに利活用が可能となります。

【発表内容】

＜研究の背景＞

暗号技術は我々の生活の様々な場面で利用され、情報社会の安全性を支えるコア技術として重要性を増しています。現在普及している暗号方式として RSA 暗号および楕円曲線暗号がありますが、大規模な量子コンピュータが実現した場合に解読されることが知られています。そのため、将来的に量子コンピュータが大規模化した時代でも安全に利用できる暗号技術として、多変数多項式問題の難しさを安全性の根拠とした Rainbow 署名が注目を集めています。Rainbow 署名はデータの不正な書き換えを検出できるデジタル署名技術ですが、その一方で検証の際に使用する公開鍵のデータサイズが大きくなることが問題となっていました。

＜研究内容＞

Rainbow 署名は 1999 年に提案された安全性の高い UOV 署名をマルチ階層構造として拡張することにより効率化していました。一方、今回の提案方式である QR-UOV 署名は、数値の行列で表現されていた UOV 署名の公開鍵を剰余環と言われる代数系の多項式として表現することにより、安全性を低下させることなく公開鍵のデータサイズ削減を実現しました（図１）。

実用的に安全性が十分に高いパラメータにおいて Rainbow 署名と比較したところ、公開鍵のデータサイズを約 66％削減することが可能となりました（表１）。

具体的には、Rainbow 署名では 252.3 KB であった公開鍵のデータサイズを、QR-UOV 署名では約 3 分の 1 となる 85.8 KB まで削減することに成功しました（KB：キロバイト）。

＜社会的意義・今後の予定＞

デジタル署名技術は、個人認証やデータの保護など情報セキュリティの向上を目的として広く利用されています。今回の提案方式は、量子計算コンピュータの時代にも安全となる効率的なデジタル署名であるため、その特徴を活かしたアプリケーションに貢献すると考えられます。特に、長期的な安全性が必要であり通信負荷の低減が求められるセキュリティシステムへの応用が期待できます。

米国標準技術研究所 NIST は量子コンピュータに対して安全な暗号方式の標準化プロジェクトを進めていますが、デジタル署名技術に関しては 2022 年に再公募を行う計画を発表しています。研究グループは効率的なデジタル署名方式である QR-UOV 署名を、NIST の暗号標準化プロジェクトに応募し標準規格への採択を目指します。