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

　NICTサイバーセキュリティ研究所セキュリティ基盤研究室は1月11日、量子コンピュータでも解読が困難な格子理論に基づく新暗号方式LOTUS（ロータス）を開発したことを発表した。LOTUSは、暗号文の復号の際にその構造をチェックする機能を持っており、現在の公開鍵暗号と置き換え可能な汎用性も有している。さらに、格子理論に基づく暗号技術の安全性評価手法を同時に開発し、複数の格子暗号同士を統一的な基準で比較することが可能になった。
　LOTUSの特徴としては、量子コンピュータでも解読が難しい耐量子性を持ち、また、ブラウザ、データベースなどに組み込み可能な汎用性を持つことなどが挙げられる。そのため、暗号の専門家でなくても安全に使うことが可能だ。
　近年の量子コンピュータの発展に伴い、これら新しいタイプのコンピュータでも解読が困難な耐量子計算機暗号の標準化が急務となっている。米国国立標準技術研究所（National Institute of Standards and Technology: NIST）が現在の暗号方式を置き換える耐量子計算機暗号を世界中から公募しており、今回、書類選考を通過した69件の候補が公開された。NICTで開発した暗号方式もこの候補の一つだ。今後数年かけて、これらの候補の評価・選定が行われる。

背景

　インターネットを利用するときに使うウェブ・ブラウザ等には、パスワードやクレジットカード番号等の重要な情報を暗号化する機能が組み込まれている。この中で、RSA暗号や楕円曲線暗号などの公開鍵暗号が使われている。
　しかしながら、現在広く使われているRSA暗号や楕円曲線暗号は、ある程度性能の高い量子コンピュータを使うと簡単に解読されてしまうことが数学的に証明されている。近年、量子コンピュータの商用販売や無償クラウド利用が提供されるなど、量子コンピュータの高性能化・普及が進んでおり、現行の公開鍵暗号では安全な通信ができなくなる可能性がある（図1参照）。
　このような社会的背景の下、現在の公開鍵暗号を置き換えるための新たな暗号方式を標準化する議論が米国NISTを中心に進んでいる。

今回の成果

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

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

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

　これまで、NICTセキュリティ基盤研究室では、耐量子計算機暗号の有力候補とされる格子暗号の開発と安全性評価に取り組んできた。その知見を活かし、今回、耐量子性だけではなく、汎用性を持った格子暗号方式の開発に取り組んだ。格子暗号にはいくつかの方式があるが、それらの中でも最も安全性に関する理論の研究が進んでいるLWE問題に基づく方式を選択した。この方式はそのままでは汎用性を持たないが、暗号文の復号の際にその構造をチェックする機能（補足資料参照）を追加することで、汎用的な暗号方式となる。これにより、米国NISTが標準化を進めている、現在の公開鍵暗号方式と置き換え可能な方式を開発し、米国NISTの耐量子計算機暗号の候補の一つとなった。
　さらに、格子理論に基づく暗号技術の安全性評価手法を同時に開発し、暗号の長期利用に適したパラメータの設定が可能になった。この安全性評価手法は、他の格子暗号方式を評価することも可能であるため、多数提案されている格子暗号同士を統一的な基準で評価することにより、公平な議論に役立つと期待されている。

今後の展望

　この暗号技術は、量子コンピュータ普及後も、引き続き、情報インフラの安全な利用を支えることができる。今回開発された方式の概要は、4月12日～13日に米国フロリダ州で開催される会議First PQC Standardization Conferenceにおいて発表される予定だ。
　また、米国NISTが発表した候補暗号方式は、今後3年以上かけて専門家による詳細な解析が行われる。NICTは「本暗号技術の普及に向けた活動を続けるとともに、耐量子計算機暗号の安全性評価にも貢献していく」としている。

LOTUSの技術(補足資料)

　LOTUSは、 “Learning with errOrs based encryption with chosen ciphertexT secUrity for poSt quantum era”の略称であり、格子暗号の技術を使っている。
　格子暗号では、全てのデータは行列やベクトルで表現される（図2参照）。暗号化処理は一度平文ベクトルをスクランブル（図中の薄緑から濃緑への矢印）した後、それを復元に必要な付加情報（図中の灰色の部分）とセットにして暗号文ベクトルとする。復号時には、秘密鍵と付加情報から、暗号文のスクランブルを解除するための情報を復元し、平文を計算します。この原理は、以前開発したセキュリティアップデータブル暗号（2015年1月19日付け NICT報道発表参照 http://www.nict.go.jp/press/2015/01/19-1.html）の基本部分と同じだ。

　図2のような暗号方式を実社会でシステムに組み込むとき、データの破損が問題になる（図3参照）。例えば、保存してある暗号文ベクトルがメディアの損傷などで、元とは異なるものに変化してしまった場合、その暗号文を正しい鍵で復号しても元の平文を得られる。また、悪意のある攻撃者は、意図的にこのデータ破損を引き起こし、情報を復元不可能にしてしまうか、無理やり破損した暗号文を復号した結果を利用して、さらに、他の秘密情報を読み取る危険性がある。

　このような暗号文破損への対策として、LOTUSでは暗号化の際に暗号文とその枠の形を示す情報を一度にパッキングし（図4上参照）、復号の直前にそれらを比較し暗号文の破損が起きていないことをチェックする機構を付け加えた（図4下参照）。もしもデータが破損していた場合、上と下で枠の形が異なるため、データの異常を検知して復号を中断することで、攻撃者が余分な情報を得ることを防げる。このチェック機構の追加を専門的には、「藤崎・岡本変換」と呼ぶ。また、この機構を組み込むことで、暗号方式が汎用性を持ち、多くのシステムに組み込むことが可能となる。