米国標準化コンペ第2ラウンド 日本発のデジタル署名方式公開
――「QR-UOV」方式の仕様を公開、量子コンピュータ時代にも安全に利用可能――

発表のポイント

QR-UOV方式はUOV方式に比べ、データサイズは半分以下に収まり、署名の効率性は同程度である。

概要

東京大学大学院情報理工学系研究科、日本電信電話株式会社、九州大学マス・フォア・インダストリ研究所、長崎県立大学からなる共同研究チームは、デジタル署名（注1）方式「QR-UOV」を改良し、コンパクトさと効率性を両立する新たな仕様を公開します。現在、米国の国立標準技術研究所（以下「NIST」）では、量子計算機（注2）でも解読できない新たなデジタル署名方式の標準化コンペを実施しており、今回の仕様公開は、QR-UOVの標準化コンペ第2ラウンド進出に合わせて行ったものです。QR-UOVは、多変数多項式問題（注3）の難しさを安全性の根拠としており、公開鍵および署名のデータサイズが小さいことが特徴です。量子計算機の時代においても安全かつ効率的なデジタル署名方式として、個人認証やデータ保護などに活用が可能となります。本署名方式が標準規格として採用された場合、世界中で広く利用されることが見込まれます。
　なお、この新たな仕様に基づくQR-UOVについては、2025年1月28～31日に開催される2025年暗号と情報セキュリティシンポジウムSCIS2025、更には2025年9月24～26日に開催予定の第6回NIST PQC標準化会議で発表予定です。

図1: QR-UOVの特徴

発表内容

暗号技術は我々の生活の様々な場面で利用され、情報社会の安全性を支えるコア技術として重要性を増しています。一方で、将来大規模な量子計算機が実現すると、暗号技術のうち公開鍵暗号・鍵共有やデジタル署名において、現在普及している方式が簡単に解読されてしまうとも言われています。大規模な量子計算機の実用化を見据え量子計算機を用いても解読できないような暗号技術（耐量子計算機暗号, Post-Quantum Cryptography, PQC）の研究・開発が進んでおり、世界の暗号標準に強い影響力を持つ米国のNISTは、2016年から耐量子計算機安全性を持つ公開鍵暗号・鍵共有方式ならびにデジタル署名方式の標準化を進めています。NIST標準化のプロセスはラウンド制で進められ、段階的な絞り込みにより採用方式を決定しています。2017年12月に69方式が受理されましたが、現在は4方式のみが標準化方式として採択されています。デジタル署名方式に関しては、2022年9月に追加公募のアナウンスがなされ、2023年7月に40方式が受理されました。そして、2024年10月に40方式中14方式が第2ラウンドの選考候補として選定され、新しい仕様書が2025年2月にNISTのホームページで公開される予定です。
　将来的に量子計算機が大規模化した時代でも安全に利用できるデジタル署名方式として、多変数多項式問題の難しさを根拠とした署名方式「UOV」が注目を集めています。UOVは1999年に提案されたデジタル署名であり、20年以上にわたり本質的な解読法が報告されていない安全な方式とされています。また、NISTが追加公募の際に出した要件として『短い署名と高速な検証を行う方式』であることを挙げており、UOVは双方を満たす方式としても注目されています。その一方で検証の際に使用する公開鍵のデータサイズが大きくなることがUOVの課題となっていました。

デジタル署名方式QR-UOVは、数値の行列で表現されていたUOVの公開鍵を剰余環（QR）（注4）と言われる代数系の多項式として表現することにより、安全性を低下させることなく公開鍵のデータサイズ削減を実現しています（図2）。QR-UOVはUOVと同様に短い署名と高速な検証を実現する方式でかつ、UOVの課題となっている公開鍵サイズを大幅に削減する方式として優位性を持っています。NIST標準化第1ラウンドの結論が2024年10月に発表され、欧米を中心とした研究機関などから候補方式14件が進出し、日本発の方式としてQR-UOVが唯一選ばれました。
　NISTは今後数年で標準化方式を選定するとしています。本研究チームは引き続き、QR-UOVの標準化採択に向けて、量子計算機の時代にも安心・安全なセキュリティを維持する技術の研究開発を進めていきます。

図2: 数値の行列を剰余環（QR）により圧縮した多項式を公開鍵とする

○関連情報：

「プレスリリース①量子コンピュータでも解読できない安全な暗号技術を開発 ～ データサイズが小さく効率的なデジタル署名 -QR-UOV- ～」（2021/11/24）
https://www.i.u-tokyo.ac.jp/news/press/2021/202111241931.shtml

発表者・研究者等情報

東京大学大学院情報理工学系研究科

論文情報

タイトル：QR-UOV
著者：Hiroki Furue, Yasuhiko Ikematsu, Fumitaka Hoshino, Tsuyoshi Takagi, Haruhisa Kosuge, Kimihiro Yamakoshi, Rika Akiyama, Satoshi Nakamura, Shingo Orihara, Koha Kinjo
会議名：NIST Post-Quantum Cryptography: Round 2 Additional Signatures
https://csrc.nist.gov/Projects/pqc-dig-sig/round-2-additional-signatures

^※上記の仕様書の概要については以下のシンポジウムで発表予定
タイトル：NIST PQC Additional Signatures Second Round Candidate: QR-UOV
著者：上記の仕様書と同じ
会議名：暗号と情報セキュリティシンポジウム（SCIS2025）
https://www.iwsec.org/scis/2025/

研究助成

本研究は科学技術振興機構（JST）戦略的創造研究推進事業 CREST「数学・数理科学と情報科学の連携・融合による情報活用基盤の創出と社会課題解決に向けた展開」研究領域（研究総括：上田 修功）における研究課題 JPMJCR2113「ポスト量子社会が求める高機能暗号の数理基盤創出と展開」の支援により実施されました。また、本研究はJSPS 科研費 JP22K17889, JP24K02939の助成を受けたものです。

用語解説

^（注1）デジタル署名：電子データに対する署名機能を実現する暗号技術で、データの改ざんやなりすまし防止の用途で電子契約書などに用いられています。

^（注2）量子計算機：量子力学の原理を計算に用いた計算機で、従来の計算機で解くには膨大な時間を要する問題を効率的に解くことができます。特に暗号分野では、現在普及している暗号技術が帰着する数学的問題を効率的に解く量子アルゴリズムが発見されていることから、耐量子計算機暗号への移行に向けた取り組みが活発になっています。

^（注3）多変数多項式問題：多変数多項式からなる連立方程式を解く問題で、パラメータの選び方により求解が困難となることが知られています。

^（注4）剰余環（QR）：足し算と掛け算が可能な代数系を特定の部分集合で割ることにより得られる、新しい足し算や掛け算が可能となる代数系を指します。今回の場合、多項式の割り算から得られる余りを計算することにより、新しい足し算や掛け算が可能となる代数系を得ることができます。