事業成果

高木剛東京大学大学院情報理工学系研究科教授らの研究グループは、次世代計算機の登場を見据えた新しいデジタル署名方式「QR-UOV」の技術仕様を公開した。デジタル署名方式とは、インターネット上でやり取りされる文書やデータに対して作成者やその内容に保証を与える仕組みである。

QR-UOVは耐量子計算機暗号の1つである。耐量子計算機暗号とは、従来の計算機よりも飛躍的に処理速度が向上した量子計算機が実用化された場合でも、解読が極めて困難な暗号方式である。次世代の情報セキュリティ基盤として研究や標準化が進められている。

今回公開されたQR-UOVは、安全性が高く、公開鍵と署名データ^※1のサイズが小さいという利点があり、安全性と効率性の両立を可能にした。本方式は米国国立標準技術研究所が進める耐量子計算機暗号の標準化コンペにおいて、日本発の方式として唯一第2ラウンドへ進出した。

図1 QR-UOV方式の特徴 安全性が高く、必要なデータ量が従来の半分以下である。

※1　公開鍵と署名データ
公開鍵とは、データやデジタル署名が本当にその作成者本人によって作られたものかを確認するためのデータであり、なりすましを防ぐ役割を持つ。署名データとは、公開鍵と組み合わせることで、本人がそのデータを作成したことと、内容が改ざんされていないことを確認するためのデータである。

デジタル署名は、電子契約やソフトウェア、個人認証などに広く用いられ、情報社会の信頼性を支える基盤技術である。現在主流のデジタル署名は、素因数分解や離散対数問題の難しさに基づいて安全性が保証されているが、大規模な量子計算機が実現した場合、これらの問題を容易に解けるようになり、暗号が破られて悪用される可能性が指摘されている。

このため、量子計算機を用いても安全性が保たれる暗号技術、いわゆる耐量子計算機暗号の研究開発が世界的に進められている。米国国立標準技術研究所は2016年から耐量子計算機暗号の標準化を進めており、段階的な選考を通して国際標準となる方式の選定を行っている。

QR-UOVは、1999年に提案されたデジタル署名方式UOVを基礎とし、その課題であった公開鍵のデータサイズの大きさを改良した方式である。従来のUOVでは、公開鍵を数値が縦と横に並んだ行列として表現していた（図2）。行列は計算機上で数値計算を行う際によく用いられる表現形式であるが、データサイズが大きくなりやすいという欠点があった。

一方、QR-UOVは公開鍵を剰余環^※2と呼ばれる代数的な枠組みの中の多項式として表現している。剰余環とは、ある数で割った余りだけを考えるという規則の下で計算を行う枠組みであり、計算結果が際限なく大きくなることを防ぐことができる。この方式により、安全性の高さは維持しながらも、公開鍵のデータサイズを大幅に削減した。

図2 QR-UOV方式のイメージ

※2　剰余環
通常の計算では、足し算や掛け算を繰り返すことで計算結果の桁数が大きくなっていく。一方、剰余環はある数で割った余りだけを扱うという規則で計算を行う。例えば、5で割った余りを考える場合、6は1、7は2として扱われる。このように計算結果のデータ量を一定の範囲に収める仕組みである。

新仕様であるQR-UOVは、従来のUOV方式が抱えていた公開鍵サイズの課題を踏まえ、暗号構造の表現方法および計算手法を見直した方式である。本成果により、米国国立標準技術研究所の標準化コンペで求められる性能要件を満たし、かつ実際のシステムへの組み込みを想定した現実的な設計が可能となった。

米国国立標準技術研究所は、今後数年をかけて耐量子計算機暗号の標準方式を選定するとしている。QR-UOVが標準規格として採用されれば、量子計算機時代においても安全に利用できるデジタル署名方式として、世界中で広く使われることが見込まれる。研究グループは、今後もQR-UOVの安全性評価や実装技術の改良を進め、国際標準化および社会実装に向けた研究開発を行う。