第２話：NIST による PQC 標準化プロジェクト

サイバートラスト研究開発ブログシリーズ耐量子計算機暗号 (PQC) の現状～ Open Quantum Safe project の PQC 実装はどこまで動くのか？～

NIST による PQC 標準化プロジェクト

「耐量子計算機暗号 (PQC) の現状」第 1 話で言及した通り、NIST は現在、PQC 標準化計画を進めています ^[1]。その背景として、以下のような趣旨を記載（2016 年）しています。

・・・大規模な量子コンピュータが構築された場合、それらは現在使用されている公開鍵暗号システムの多くを破ることができるでしょう。これは、インターネットやその他の場所でのデジタル通信の機密性と完全性を著しく損なうことになります。耐量子計算機暗号の目標は、量子コンピュータと従来型のコンピュータの両方に対して安全であり、既存の通信プロトコルおよびネットワークと相互運用できる暗号システムを開発することです。
・・・（略）・・・
歴史的に、我々の最新の公開鍵暗号化インフラストラクチャを展開するのにほぼ 20 年という時間がかかりました。従って、量子コンピューティング時代が到来を正確に見積もれるかにかかわらず、量子コンピューティングに抵抗できるように情報セキュリティシステムの準備を今から始めなければなりません。

出典：NIST,"Post-Quantum Cryptography"^[1],Background の内容を一部抜粋、和訳

PQC 標準化計画は、2017 年に PQC 候補を公募し、その後、3～5 年かけて安全性と効率性を評価し、選定、標準化するという計画です。
2020 年 7 月からは、以下の 7 方式（代替 6 方式）について Round 3 の評価が開始されています ^[2]。下表のように、PQC の暗号方式としては複数種類が提案されており、いずれも、量子コンピュータが苦手な計算処理を必要とすると考えられる問題を基に暗号アルゴリズムが設計されています。

暗号方式	使途：　暗号名称
格子暗号	鍵交換・暗号化：CRYSTALS-KYBER、NTRU、SABER、（Frodo-KEM、 NTRU Prime）デジタル署名：　CRYSTALS-DILITHIUM、FALCON
符号暗号	鍵交換・暗号化：Classic McEliece、（BIKE、HQC）
多変数多項式暗号	デジタル署名：　Rainbow、（GeMSS）
ハッシュ関数署名	デジタル署名：（SPHINCS+）
同種写像暗号	鍵交換・暗号化：（SIKE）
その他	デジタル署名：（Picnic）

出典： CRYPTREC RP-1000-2020, 表 3.1-1 Round 3^[2]

さて、元々の予定では、2022～2024 年に標準化ドラフトを策定とされていましたが、"NIST Status Update on the 3rd Round"^[3]（「第 3 ラウンドの NIST ステータスの更新」）では、Time Line として更に以下の予定であることが伝えられました。

Round 3 は、2021 年末近くに終了、標準化する最終アルゴリズムを発表する
Round 4 の候補についても発表、Round 4 も従来同様 12〜18 ヶ月予定
Round 3 に関するレポートを発行予定
2022～2023 年にパブリックコメント基準案を発表、最終標準は 2024 年までに準備が整うことを願っている

しかし 2021 年末には発表はなく、2022 年 2 月～３月前半頃の時点では、NIST PQC team は PQC Emailing List ^[4] 上で、Round 3 が間もなく終了し、Round 3 レポートを作成しており、3 月末には報告したい、と回答。が、更に 3 月末も過ぎ、4 月 20 日に再度 Emailing List 上で "We appreciate your patience." から始まり、『まもなく標準化するアルゴリズムを発表する。遅延は技術的な考慮事項によるものではなく、法律上や手続き的なもので想定以上に時間がかかっている』というような内容を伝えています。

引き続き発表を注視したいところですが、もう１点、『遅延は技術的な考慮事項によるものではない』と伝えられたところは実は気になっていた点でした。NIST PQC team が 3 月末には報告したいと最初に Mailing List で答えたその後、2022 年 2 月の末近く、"Cryptology ePrint Archive: Report 2022/214" として "Breaking Rainbow Takes a Weekend on a Laptop" という論文が公開されました ^[5]。意訳すると、上記 PQC 標準化の Round 3 に残っている Rainbow 署名アルゴリズムについて、「Rainbow はラップトップコンピュータを使った週末の計算で破れる」といったところかと思います。

NIST の PQC 標準化プロセスでは、セキュリティレベル（鍵サイズなど）がより強くなる SL1～SL3 の３通りのパラメタを各 PQC 候補が提出していますが、論文は、この中で一番小さい SL1 パラメタの場合について、実際に一般的なラップトップコンピュータを使って Rainbow 公開鍵に対する攻撃のデモンストレーションを行い、平均 53 時間程度で秘密鍵が見つけられた、ということでした。量子コンピュータに対する耐性以前に、従来型のコンピュータでの攻撃方法が見つかってしまったというもので、安全性の評価や実際の利用実績が浅いことから、こういったことも起きてしまうのでしょう。

Rainbow team はこれに対しすかさず、『Rainbow レベル 1 パラメタとしてレベル 3 パラメタを使い、レベル 3 パラメタとしてレベル 5 パラメタを使うよう置き換えることを NIST に提案』することで、セキュリティレベルを高める対応をとっています ^[6]。しかし、そういう類の対応が必用なこと自体に疑問を持ち、候補として適当ではないなどの厳しい意見も Web 上の記事なども含めて出され、さらに、格子暗号などの他の暗号方式にまで飛び火した意見が Mailing List の同じスレッド上で一部交わされるなど、議論がまとまるよりは発散しているように見えました。その後、発表見込みの 3 月がすぎ、4 月半ばになっても発表がないことから、ついつい、技術的な選定で紛糾しているのだろうか・・と勘ぐってしまっていた次第です。

さて、ここまでのところでは、この後、代替６方式に関する Round 4 もあるようですし、NIST による PQC 標準化の動きは着実ではあっても、まだ実際の利用 " 現場 " に降りてくるには時間を要しそうに感じていましたが、一方で、PQC 推進に追い風となる動きもありました。2022 年 1 月、米国バイデン大統領が国家安全保障覚書 8（NSM-8）（" Memorandum on Improving the Cybersecurity of National Security, Department of Defense, and Intelligence Community Systems"（「国家安全保障、国防総省、およびインテリジェンスコミュニティシステムのサイバーセキュリティの改善に関する覚書」））^[7] に署名し、発効となりました。ここには、商用国家安全保障アルゴリズム（CNSA(Commercial National Security Algorithm)）のリストの更新を行いなさいとあり、耐量子計算機暗号の追加の指示が明記されたのです。

これまで NSA（National Security Agency（アメリカ国家安全保障局））は、"CNSA Suite" の中で、耐量子計算機暗号アルゴリズムへの今後の移行について計画と調整を早期に開始するとしながらも、『耐量子計算機暗号に対応した製品が利用可能になるまでは、現状の暗号利用状況を費用をかけて変えることなどもあまりせず、短期的には今の暗号手法（2048 ビットの RSA）を維持するのが望ましいかもしれない・・』との趣旨のことを言っているように思い ^[8]、これはこれで当然なのですが、待ちのスタンスがあるようにも個人的には感じていたので、今後どうなるのかは気になるところです。

国内では CRYPTREC が、NIST の PQC 標準化動向を考慮した PQC ガイドラインを 2023 年（？）頃に作成・公開することを検討しているようで ^[9]、こちらも、利用 " 現場 " 推進の力になると思われ、期待感があるところです。

Open Quantum Safe project

前述の NIST の標準化に並行して、実装面での実証実験としてオープンソースの PQC 暗号ライブラリ「LIBOQS」が Open Quantum Safe project (OQS Project) としてプロトタイピングされ、公開されています ^[10]。NIST が Round 3 で評価している PQC がサポートされており（ただし GeMSS は除く）、プロジェクトは産学連携で、Waterloo 大学、AWS、IBM、Microsoft、他（順不同）が推進しています。

2022 年 4 月時点で、C ライブラリ liboqs（ver. 0.7.1）や同ライブラリを組み込んだ OQS-OpenSSL_1_1_1-stable などが Github 上 ^[11] に公開されており、PQC を利用した TLS プロトコルなどまでも試せる環境が既に整っています。

Open Quantum Safe サイトの画面

出典："Open Quantum Safe"^[11] サイト画面

試しに PQC ライブラリ liboqs ですが、Github（open-quantum-safe/liboqs）^[12] の "Quickstart" の記載に従ってソースを get し、build して、liboqs がサポートしている暗号アルゴリズム一覧を見たり、例えば格子暗号 DILITHIUM（「ダイリチウム」と呼ぶそうです）の鍵ペアの作成を試してみたり、なども簡単に試すことができます。

PQC ライブラリ liboqs

まさに OSS で言う「巨人の肩に乗る」を感じます。先人・先駆者の知恵と尽力に感謝です。

次回：Open Quantum Safe project / OpenSSL や Demo

次回は、PQC 対応の「OpenSSL」や「ハイブリッド」などについて解説します。

この記事の著者

サイバートラスト R&D センター

「R&D センター」は、2022 年 4 月 1 日に立ち上げられた研究開発部門です。
サイバートラストは、お客様のサービスの信頼性を支えるプラットフォーマーとして、先々のプラットフォームや社会制度、他がどのように変化するのかを考えています。
さまざまな IoT 機器が普及し、OSS や AI やブロックチェーンが活用され、量子コンピュータが発達する一方で、それらによる新たなセキュリティリスクも生じると想像される未来においても、引き続き、安心・安全な社会を実現するため、サイバートラストが果たす役割を含め、研究開発を進めていきます。