耐量子暗号技術の研究動向
草川 恵太(くさがわ けいた)
NTTセキュアプラットフォーム研究所

現在のインターネット上では、プライバシ情報やクレジットカード番号等の機密性の高い情報が多くやり取りされています。通信内容を秘匿するためには、共通鍵暗号や公開鍵暗号が使われています。相手先や送信内容の真正性を確認するために、電子署名やメッセージ認証符号(MAC)といった認証技術が使われています。公開鍵暗号やデジタル署名の中でも現在広く使われているのが、素因数分解問題の困難性に基づく暗号アルゴリズム(RSA暗号、RSA署名など)や離散対数問題の困難性に基づく暗号アルゴリズム(Diffie-Hellman鍵交換、楕円曲線Diffie-Hellman鍵共有、DSAなど)です。
1994年、Peter Williston Shor氏はこの2つの問題を効率良く解く量子コンピュータ用のアルゴリズムを提案しました。大規模かつ安定して計算が行えるような量子コンピュータが完成すると、現在広く用いられている暗号アルゴリズムは安全でなくなります。そのため、量子コンピュータが完成する前に、量子コンピュータを用いても解読や偽造ができないような暗号技術の研究・開発・標準化が盛んになっています。公開鍵暗号技術の中でも、量子コンピュータが苦手とすると考えられている問題を基に暗号アルゴリズムが設計されているものを、耐量子公開鍵暗号技術と呼びます。

耐量子暗号技術への移行を検討する必要があるかどうかについては、Michele Mosca氏提案の計算式が参考になります。

• ・x＝今後生成される情報の安全性を保ちたい年数
• ・y＝耐量子暗号アルゴリズムへの移行(研究開発、標準化、普及)に必要な年数
• ・z＝大規模量子コンピュータが完成するまでの年数

x＋y＞zであれば、y年後に「x年間安全性を保ちたい」と思って暗号化した暗号文は、x年未満に量子コンピュータによって破られる可能性があります。したがって、現時点でx＋y＞zだと考えられるのであれば、耐量子暗号技術の標準化や耐量子暗号技術への移行を真剣に検討する必要があります。
昨今の量子コンピュータの開発状況からzが現実的な年数になるのではないかと考えられており、各国のいろいろな組織や標準化団体が移行の検討を進めています。

• ・日本のCRYPTREC(Cryptography Research and Evaluation Committees)^＊は、2014年ごろに「格子問題等の困難性に関する調査」として耐量子暗号技術の調査報告を行っています。
• ・米国国立標準技術研究所 (NIST)は、2015年春ごろからワークショップを開催し始め、2016年には耐量子公開鍵暗号技術の標準化活動を行うことを宣言しました。
• ・米国国家安全保障局(NSA)は、2015年8月、機密情報の保護のために用いる暗号アルゴリズムのリスト Suite Bについて、耐量子暗号技術への移行が将来的に行われることを表明しました。
• ・欧州電気通信標準化機構(ETSI)は2013年ごろから量子暗号と耐量子暗号技術のワークショップを毎年開催しています。
• ・国際標準化機構(ISO)と国際電気標準会議(IEC)は2015年ごろから耐量子暗号技術に関する議論の時間を設けています。
• ・IETFでも、耐量子署名のプロジェクトが進んでおり、RFCとして公開され始めています(RFC8391: XMSS: eXtended Merkle Signature Schemeなど)。

これらの動きの中でも世界の暗号技術標準に強い影響力を持つNISTの耐量子暗号技術標準化プロジェクトを紹介します。

1. ＊CRYPTREC：電子政府推奨暗号の安全性を評価・監視し、暗号技術の適切な実装法・運用法を調査・検討するプロジェクト。

NISTの耐量子暗号技術標準化プロジェクトは2016年ごろから本格的に開始しました。デジタル署名、公開鍵暗号、鍵共有の3つのカテゴリの暗号アルゴリズムを選定し標準化するためのプロジェクトです。NISTのスケジュールは以下のとおりです(図)。

• ・2016年2月：耐量子暗号技術標準化開始の宣言
• ・2016年8月：NISTIR 8105 『Report on Post-Quantum Cryptography』 の発行
• ・2016年8月：募集要項および選定基準についてのコメント募集
• ・2016年12月：受付開始
• ・2017年11月：受付締切
• ・2017年12月：書類および形式審査を行い、Round 1の開始
• ・2018年4月：第1回耐量子暗号技術標準化会議
• ・2018～2019年：Round 2の開始
• ・2019年8月：第2回耐量子暗号技術標準化会議の予定
• ・2020～2021年：Round 3の開始またはアルゴリズム選定
• ・2022～2024年：ドラフト準備完了

2017年11月締切時点では82の投稿があり、署名の提案が23件、暗号化・鍵共有の提案が59件でした。その後、1カ月ほど書類や形式の審査を行い、2017年12月にRound 1が開始されました。このとき、69件が残りました。のちに5件取り下げがあり、現時点では64件が残っています。署名の提案が19件、暗号化・鍵共有の提案が45件残っています。
すでに書いたとおり、書類および形式を審査した結果がRound 1の候補である69件です。
そのため、Round 1に進んだからといって、安全であるとは限りません。
Round 1の候補が公開された直後から、NISTのpqcメーリングリストにおいて、各方式の安全性について激しい議論が交わされました。
その中でも、以下のように実際に破れることが示された例が多数あります。

• ・Guess Again(その他・暗号)
• ・RaCoSS(符号・署名)
• ・RVB(その他・暗号)→取り下げ
• ・HK17(その他・暗号)→取り下げ
• ・CFPKM(多変数多項式・暗号)
• ・SRTPI(多変数多項式・暗号)→取り下げ
• ・Edon-K(符号・暗号)→取り下げ
• ・Comact LWE(格子・暗号)
• ・WalnutDSA(その他・暗号)
• ・RankSign(符号・署名)→取り下げ

今後も、Round 2に進むまでに安全性評価手法が改良されることが想定されるため、注視が必要です。

NTTでは、NISTの耐量子暗号標準化活動には独自のアルゴリズムを提出していません。
しかし、安全性強化手法の提案や第三者的立場での安全性評価というかたちで参加し、適切なアルゴリズムが選ばれるよう協力しています。
またNISTの耐量子暗号標準化は耐量子公開鍵暗号技術のみを対象にしていますが、NTTでは独自に耐量子共通鍵暗号技術についても研究を進めています。…