世界最高性能の耐量子公開鍵暗号を実現 量子コンピュータでも改ざん不可能な安全性強化手法を提案

発表概要

日本電信電話株式会社（本社：東京都・千代田区、代表取締役社長：鵜浦博夫、以下　NTT）は、量子コンピュータ※1完成後の時代に必要とされる耐量子公開鍵暗号※2について、新たな安全性強化手法を開発しました。今回開発した手法を用いると、世界最高水準の効率性を持ち、更に量子コンピュータでも改ざんが不可能である等の強い安全性を持つ耐量子公開鍵暗号方式を容易に構成できるようになります。
　この研究結果は、国際暗号学会主催の暗号関連のトップ会議Eurocrypt 2018※3（2018年4月29日からイスラエルのテルアビブで開催）で発表します。

背景

情報化社会の進展に伴い、インターネット上でプライバシー情報やクレジットカード番号等の機密性の高い情報が多くやりとりされています。このような情報を守るための技術として、公開鍵暗号は必要不可欠になっており、WEBブラウザで表示される鍵マーク（HTTPS）は、公開鍵暗号を要素技術として用いた暗号化が行われていることを表しています。しかし、近年急速に開発が進んでいる量子コンピュータが完成すると、現在広く用いられているRSA暗号や楕円曲線暗号等の公開鍵暗号方式は簡単に解読されてしまうことが知られています（注）。したがって、量子コンピュータが完成する前に、量子コンピュータを用いても解読することが出来ないような公開鍵暗号（耐量子公開鍵暗号）の研究を進めることが急務であり、世界の暗号標準に強い影響力を持つ米国国立標準技術研究所（NIST）は、2024年までを目途に、耐量子公開鍵暗号の標準化方式の選定を開始しています。
　また、実際の通信状況下で安全な暗号通信を行うには、公開鍵暗号はメッセージを秘匿するだけでなく、メッセージの改ざんを防止する等のより強い安全性が必要です。専門的には、これをCCA安全性※4と呼びます。過去には、CCA安全性を持たない公開鍵暗号方式を使用していたために、暗号を解読されてしまった事例が報告されています（例：RSA社の標準暗号方式RSA PKCS#1v1.5に対するBleichenbacher攻撃※5）。したがって、現在では、CCA安全性を持つことが現実に使用する公開鍵暗号のための必須の条件とされています。量子コンピュータ完成後も、安全な通信を続けるためにはCCA安全性を持つ耐量子公開鍵暗号が必要です。

提案方式の特徴

このたび、NTTではCCA安全性を持たない耐量子公開鍵暗号を、CCA安全性を持つ耐量子公開鍵暗号へ変換し、安全性を強化する新たな手法を開発しました。これにより、世界最高水準の耐量子公開鍵暗号方式を高効率に構成できます。また、今回の手法は汎用性が高く、様々な既存の耐量子公開鍵暗号に対しても適用可能であり、NIST標準化候補暗号方式でも、少なくとも7件に適用可能です。この技術に基づく耐量子公開鍵暗号を用いることで、量子コンピュータ実現後の時代においても、余分な負荷の小さい暗号通信が可能になります。

技術の詳細

CCA安全性を持たない公開鍵暗号をCCA安全性を持つ公開鍵暗号へと強化する手法は古くから研究されてきましたが、2010年頃からこれらの手法が量子コンピュータに対しても安全であるかどうかが研究されはじめました。その結果、これらの手法は効率性を2倍以上悪くすれば、量子コンピュータに対しても有効であることが証明されました。しかし、効率の悪い暗号方式を用いる場合、従来に比べて鍵サイズや暗号文サイズが大きくなったり、計算リソースがより必要になったり、計算速度が遅くなったりします。そのため、効率性を犠牲にしない安全性強化手法が理想的です。しかし、量子コンピュータに対しても有効であるような安全性強化手法で、効率性を犠牲にしないものは知られていませんでした。今回開発した手法ではこの課題を解決しました。
　今回開発した安全性強化手法では、既存の手法と同じく、改ざん検知を行う仕組みを付加して安全性を強化するというアプローチをとります。しかし、既存の手法では、復号の際に暗号文が不正なフォーマットであることが検出された場合、エラーが出力されますが、同時に攻撃者が改ざんを施した暗号文が不正なフォーマットであるかどうかの情報も漏れてしまいます。この情報を利用して暗号への攻撃が高速化する可能性がありました。従来の手法では、この問題を解決するために鍵サイズを2倍以上にしてあり得る鍵の候補数を増やす必要がありましたが、この方法では効率も同時に劣化してしまいます。今回の提案手法では、不正なフォーマットであることが検出された場合、エラーを出力する代わりに乱数を出力します。これにより、攻撃者は暗号文が不正なフォーマットであるかどうかを知ることができないため、上記のような解読の可能性はなくなります。このようなアイディアを用いて、効率性を犠牲にせずに量子コンピュータに対して安全であることが証明できました。

今後の展望

このたび開発した安全性強化手法を含め耐量子公開鍵暗号技術を取り揃え、量子コンピュータの完成後も安心・安全な暗号通信技術の開発・実用化に向けた検討を進めていく予定です。

注釈

注：アニーリング型と呼ばれる特定の計算に特化した量子コンピュータは既に実用化されていますが、ゲート型と呼ばれる汎用的な量子コンピュータは未だ開発途上です。暗号解読に用いることが出来るような大規模かつ安定したゲート型量子コンピュータが開発されるまでには、さまざまなハードルがあります。

用語解説

量子コンピュータ：

量子力学に基づく、従来とは全く異なる原理のコンピュータ。素因数分解問題等のある種の問題については、従来のコンピュータよりも圧倒的に高速に解くことができると考えられています。

耐量子公開鍵暗号：

公開鍵暗号とは、1976年にDiffieとHellmanにより提唱された、受信者と送信者が事前に鍵を共有する必要のない暗号です。耐量子公開鍵暗号とは、量子コンピュータを用いても解読できないような公開鍵暗号です。

Eurocrypt 2018：

国際暗号学会（International Association for Cryptologic Research）が主催する、暗号理論における世界最高峰の国際会議であり、世界最先端の暗号技術が発表されます。

CCA安全性：

選択的暗号文攻撃（Chosen Ciphertext Attack）に対する安全性。攻撃者が一つを除いて全ての暗号文を復号できる状況下でも、その一つの暗号文は解読できないという非常に強い安全性です。CCA安全性を持つ公開鍵暗号方式は改ざん不可能であることが知られています。

RSA PKCS#1v1.5に対するBleichenbacher攻撃：

RSA PKCS#1v1.5は、Rivest, Shamir, Adlemanが1978年に発明したRSA暗号に基づいてRSA社が定めた標準的暗号化方式です。Bleichenbacherは1998年に、RSA PKCS#1v1.5を解読する選択暗号文攻撃を発見しました。Böckらにより、2017年現在でもこの攻撃が一部システムに対して通用することが報告され、ROBOT攻撃として知られています。