量子コンピュータ時代に向けた新暗号技術を開発

2018年1月11日



国立研究開発法人情報通信研究機構（NICT）



量子コンピュータ時代に向けた新暗号技術を開発

～格子理論に基づき、かつ汎用性に優れた公開鍵暗号を国際標準化に提案～



【ポイント】

■　量子コンピュータでも安全な格子理論に基づく公開鍵暗号を開発

■　暗号技術の安全性評価手法を開発、統一的な基準で様々な格子暗号を比較可能に

■　米国NIST主催の量子コンピュータ時代に向けた暗号技術の標準化プロジェクトの候補暗号に



　国立研究開発法人情報通信研究機構（NICT、理事長: 徳田 英幸）サイバーセキュリティ研究所セキュリティ基盤研究室は、量子コンピュータでも解読が困難な格子理論に基づく新暗号方式LOTUS（ロータス）を開発しました。LOTUSは、暗号文の復号の際にその構造をチェックする機能を持っており、現在の公開鍵暗号と置き換え可能な汎用性も有しています。さらに、格子理論に基づく暗号技術の安全性評価手法を同時に開発し、複数の格子暗号同士を統一的な基準で比較することが可能になりました。

　LOTUSの特徴としては、量子コンピュータでも解読が難しい耐量子性を持ち、また、ブラウザ、データベースなどに組み込み可能な汎用性を持つことなどが挙げられます。そのため、暗号の専門家でなくても安全に使うことが可能です。

　近年の量子コンピュータの発展に伴い、これら新しいタイプのコンピュータでも解読が困難な耐量子計算機暗号の標準化が急務となっています。米国国立標準技術研究所（National Institute of Standards and Technology: NIST）が現在の暗号方式を置き換える耐量子計算機暗号を世界中から公募していましたが、このたび、書類選考を通過した69件の候補が公開されました。NICTで開発した暗号方式もこの候補の一つです。今後数年かけて、これらの候補の評価・選定が行われます。



【背景】

　インターネットを利用するときに使うウェブ・ブラウザ等には、パスワードやクレジットカード番号等の重要な情報を暗号化する機能が組み込まれています。この中で、RSA暗号や楕円曲線暗号などの公開鍵暗号が使われています。

　しかしながら、現在広く使われているRSA暗号や楕円曲線暗号は、ある程度性能の高い量子コンピュータを使うと簡単に解読されてしまうことが数学的に証明されています。近年、量子コンピュータの商用販売や無償クラウド利用が提供されるなど、量子コンピュータの高性能化・普及が進んでおり、現行の公開鍵暗号では安全な通信ができなくなる可能性があります（図1参照）。

　このような社会的背景の下、現在の公開鍵暗号を置き換えるための新たな暗号方式を標準化する議論が米国NISTを中心に進んでいます。



【今回の成果】

　量子コンピュータが普及した時代でも情報の安全性が守れるよう、NICTでは以下の条件を満たす新暗号方式LOTUSを開発しました。

①耐量子性: 通常のコンピュータのみならず、量子コンピュータでも解読が難しいこと。これにより、量子コンピュータ普及後も情報の安全性が守られます。

②汎用性: ベースとなる暗号方式に対して、復号の際に暗号文が破損していないことをチェックする機構を追加することで、ブラウザ、データベースをはじめ、多くの通信・交通・産業システムに組み込むことが可能となりました。また、本暗号を組み込んだシステム全体も量子コンピュータに対して安全となることが数学的に証明されているため、暗号の専門家以外でも安心して使うことができます。

　これまで、NICTセキュリティ基盤研究室では、耐量子計算機暗号の有力候補とされる格子暗号の開発と安全性評価に取り組んできました。その知見を活かし、今回、耐量子性だけではなく、汎用性を持った格子暗号方式の開発に取り組みました。格子暗号にはいくつかの方式がありますが、それらの中でも最も安全性に関する理論の研究が進んでいるLWE問題に基づく方式を選択しました。この方式はそのままでは汎用性を持ちませんが、暗号文の復号の際にその構造をチェックする機能を追加することで、汎用的な暗号方式となります。これにより、米国NISTが標準化を進めている、現在の公開鍵暗号方式と置き換え可能な方式を開発し、米国NISTの耐量子計算機暗号の候補の一つとなりました。

　さらに、格子理論に基づく暗号技術の安全性評価手法を同時に開発し、暗号の長期利用に適したパラメータの設定が可能になりました。この安全性評価手法は、他の格子暗号方式を評価することも可能であるため、多数提案されている格子暗号同士を統一的な基準で評価することにより、公平な議論に役立つと期待されます。



【今後の展望】

　本暗号技術は、量子コンピュータ普及後も、引き続き、情報インフラの安全な利用を支えることができます。今回開発した方式の概要は、2018年4月12日（木）～13日（金）に米国フロリダ州で開催される会議First PQC Standardization Conferenceにおいて発表される予定です。

　また、このたび米国NISTが発表した候補暗号方式は、今後3年以上かけて専門家による詳細な解析が行われます。NICTは、本暗号技術の普及に向けた活動を続けるとともに、耐量子計算機暗号の安全性評価にも貢献していきます。