ニュース

量子コンピュータでも解読が困難な新暗号方式が国内で開発

公開鍵暗号の変遷

 国立研究開発法人情報通信研究機構(NICT)は、格子理論に基づく新暗号方式「LOTUS」を開発したと発表した。

 NICTサイバーセキュリティ研究所セキュリティ基盤研究室が開発したもので、量子コンピュータでも解読が難しい、耐量子計算機暗号として開発された暗号化方式。

 現在広く使われているRSA暗号や楕円曲線暗号は、ある程度性能の高い量子コンピュータを使うことで、簡単に解読できることが数学的に証明されている。

 近年では、商用販売や無償クラウド利用が提供されるなど、量子コンピュータの高性能化と普及が進んでおり、現行の公開鍵暗号では安全な通信ができなくなる可能性がある。そのため、耐量子計算機暗号の標準化が求められていた。

 そういった背景から、米国国立標準技術研究所(NIST)が耐量子計算機暗号を公募していたが、今回のLOTUSも書類選考を通過した69件の候補の1つで、今後を数年かけて、各候補の評価と選定が行なわれる。

 LOTUSは「Learning with errOrs based encryption with chosen ciphertexT secUrity for poSt quantum era」の略称で、格子暗号の技術を使った暗号方式となる。

 略称にもあるように、変数よりも式の数が多い連立一次方程式において、左辺と右辺の差が小さくなるような整数解を求める「LWE(Learning with Errors)問題」を用いている。LWE問題は、パラメータ次第で格子の最短ベクトル問題と同等の難しさとなることが証明されているため、量子コンピュータでも解を求めるには非常に時間がかかると予想されている。

 まず、格子暗号では、全データが行列やベクトルで表現される。

 暗号化処理では、一度平文ベクトルをスクランブルした後、それと復元に必要な付加情報とセットにして暗号文ベクトルとし、復号時には、秘密鍵と付加情報から暗号文のスクランブルを解除するための情報を復元し、平文を計算する。

格子暗号の概要

 しかし、同種の暗号方式をシステムに組み込むときには、データの破損が問題となる。

 たとえば、保存してある暗号文ベクトルが、記録メディアの損傷などで元と異なるものに変化してしまった場合、その暗号文を正しい鍵で復号しても、元の平文を得られない。また、悪意のある攻撃者によって、意図的にデータが破損されることで情報を復元不可能にされてしまうか、無理やり破損した暗号文を復号した結果を利用して、ほかの秘密情報を読み取られる危険性がある。

破損した暗号文の復号結果は悪用される危険性がある

 そういった暗号文破損への対策として、LOTUSでは、暗号化のさいに、暗号文とその枠の形を示す情報を一度にパッキングし、復号の直前にそれらを比較することで、暗号文が破損していないかをチェックする機構が追加されているという。

 この整合性チェックで、もしデータが破損していた場合、データの異常を検知して復号を中断することで、攻撃者が余分な情報を得ることを防ぐ。このチェック機構の追加は「藤崎・岡本変換」と呼ばれ、同機構を組み込むことで、公開鍵暗号と置き換え可能な汎用性を持ち、多くのシステムに組み込めるようになるとしている。

藤崎・岡本変換によって汎用性を持たせた格子暗号

 またNICTでは、LOTUSとともに、格子理論に基づく暗号技術の安全性評価手法を同時に開発。LOTUS以外の格子暗号方式を評価することも可能であるため、いくつか提案されている格子暗号同士を、統一的な基準で評価することで、公平な議論に役立つと期待されるとしている。

 暗号方式の概要は、2018年4月12日~13日に米フロリダで開催される「First PQC Standardization Conference」において発表される予定。