NTT､世界最高性能の耐量子公開鍵暗号を実現

May, 7, 2018, 東京--日本電信電話（NTT）は、量子コンピュータ完成後の時代に必要とされる耐量子公開鍵暗号について、新たな安全性強化手法を開発した。
　今回開発した手法を用いると、世界最高水準の効率性を持ち、更に量子コンピュータでも改ざんが不可能である等の強い安全性を持つ耐量子公開鍵暗号方式を容易に構成できるようになる。
　この研究結果は、国際暗号学会主催の暗号関連のトップ会議Eurocrypt 2018で発表した。
　実際の通信状況下で安全な暗号通信を行うには、公開鍵暗号はメッセージを秘匿するだけでなく、メッセージの改ざんを防止する等のより強い安全性が必要。専門的には、これをCCA安全性と呼ぶ。従って、現在では、CCA安全性を持つことが現実に使用する公開鍵暗号のための必須の条件とされている。量子コンピュータ完成後も、安全な通信を続けるためにはCCA安全性を持つ耐量子公開鍵暗号が必要となる。
　CCA安全性を持たない公開鍵暗号をCCA安全性を持つ公開鍵暗号へと強化する手法は古くから研究されてきたが、2010年頃からこれらの手法が量子コンピュータに対しても安全であるかどうかが研究されはじめた。その結果、これらの手法は効率性を2倍以上悪くすれば、量子コンピュータに対しても有効であることが証明された。しかし、効率の悪い暗号方式を用いる場合、従来に比べて鍵サイズや暗号文サイズが大きくなったり、計算リソースがより必要になったり、計算速度が遅くなったりする。そのため、効率性を犠牲にしない安全性強化手法が理想的であるが、量子コンピュータに対しても有効であるような安全性強化手法で、効率性を犠牲にしないものは知られていなかった。今回開発した手法ではこの課題を解決した。
　今回開発した安全性強化手法では、既存の手法と同じく、改ざん検知を行う仕組みを付加して安全性を強化するというアプローチをとる。しかし、既存の手法では、復号の際に暗号文が不正なフォーマットであることが検出された場合、エラーが出力されるが、同時に攻撃者が改ざんを施した暗号文が不正なフォーマットであるかどうかの情報も漏れてしまう。この情報を利用して暗号への攻撃が高速化する可能性があった。従来手法では、この問題を解決するために鍵サイズを2倍以上にしてあり得る鍵の候補数を増やす必要があったが、今回の提案手法では、不正なフォーマットであることが検出された場合、エラーを出力する代わりに乱数を出力する。これにより、攻撃者は暗号文が不正なフォーマットであるかどうかを知ることができないため、上記のような解読の可能性はなくなる。このようなアイディアを用いて、効率性を犠牲にせずに量子コンピュータに対して安全であることが証明できた。
(詳細は､www.ntt.co.jp)