量子コンピュータ時代に向けた暗号通信

## はじめに

最近、量子コンピュータの活用がホットな話題となり様々な応用に付いて議論されるようになってきていますが、かつては「量子コンピュータが実現すると暗号が破られてしまい安全な通信が行えなくなる」と盛んに言われ、合わせて量子暗号通信が紹介されることが多くありました。
しかし量子コンピュータの脅威への対策として量子暗号通信の実用化まで待たずとも、古典コンピュータで実行可能な量子コンピュータでも解読が難しい耐量子暗号（Post-Quantum Cryptgraphy, PQC）の検討が進められています。ここ2〜3年は特にその動きが活発となり、昨年2023年には一般向けの記事でも耐量子暗号の話題を目にする様になりました。NTTデータグループからも[耐量子計算機暗号（PQC）へ移行する際の留意点をまとめたホワイトペーパー](https://www.nttdata.com/global/ja/news/topics/2023/100301/)が同年の10月3日に公開されています。
耐量子暗号の実用化に向けた動きとしては、アルゴリズムに関する安全性や効率の評価及び標準化が進められている一方で、通信プロトコルの方でも耐量子暗号に対応させる試みや仕様化の検討が進められています。
この記事では、特にネットワークで使用される通信プロトコルについての取り組みを紹介します。

## おさらい

### 安全な通信

安全に通信が出来るとは、通信の機密性、整合性、可用性が確保されている状態を指します。その中でも、公開鍵暗号技術は機密性と整合性の保護に貢献しています。

機密性とは、通信されるデータが不正な者によって閲覧されることなく、送信者と受信者だけが内容を理解できることを指します。公開鍵暗号技術は、通信相手が本人であることを確認し、通信に使用する鍵を安全に共有することで、通信内容の盗聴を防ぐ役割を果たします。これにより、第三者が通信内容を傍受しても、その内容を理解することができません。

整合性とは、通信されたデータが途中で改竄されていないことを保証することです。安全に共有された鍵を用いて暗号化を行ったり認証符号を付加したりすることで、受信したメッセージが正しい送信者から送られたものであり、途中で改ざんされていないことを確認できます。

以上のように、公開鍵暗号技術によって、通信者は盗聴や改竄の恐れのある通信路上にセキュアトンネルを確立することを可能にしています。

### 公開鍵暗号技術と量子コンピュータ

現在の暗号通信において広く使われている公開鍵暗号技術は、素因数分解や離散対数問題などの数学的難問を安全性の根拠としています。代表例としてRSAやDiffie-Hellman鍵共有、楕円曲線暗号などがあります。しかし量子コンピュータを使うと、これらの問題に対して現実的な時間内で解を求めることが可能とされており、これは従来の公開鍵暗号が破られて安全な通信が行えなくなることを意味しています。

従来の公開鍵暗号を破ることが出来る量子コンピュータは汎用型の「ゲート方式」のもので、現在D-Wave社が提供している特化型の「量子アニーリング方式」とは異なります。ゲート方式の量子コンピュータは実験室レベルのもので、暗号解読を行うには未だ数多くの技術的課題が存在します。しかし研究は着実に進められ、一歩一歩、実現に近づく成果が出ています。現実となるかは分かりませんが、2030年ごろに2048bitのRSAが破られる可能性があるとの予想を基に対策が進められている所です。

このように通信セキュリティを維持するためには、量子コンピュータに対しても耐え得る新しい公開鍵暗号技術が必要とされています。これが各所で注目を集めつつある耐量子暗号です。

## 耐量子暗号

### 耐量子暗号とは

量子コンピュータを用いても高速に攻撃するアルゴリズムが見つかっていない暗号です。代表的な分類として、「格子暗号」「符号ベース暗号」「多変数多項式暗号」「同種写像暗号」「ハッシュベース暗号」などがあります。これらのアプローチは、それぞれ異なる数学的背景を持っています。
近年、特に注目されることとなった暗号ではありますが、その基本的な技術自体は1970年代後半～1990年代には提案されていました。

### 標準化

耐量子暗号は様々なアルゴリズムが提案されていましたが、その安全性や効率性を評価し、有用なアルゴリズムや推奨パラメータの標準化が行われています。通信では使用する機器・ソフトウェアの相互運用性が非常に大切であり、その視点でも重要なプロセスとなります。
ここで大きな存在感を示しているのが NIST（National Institute of Standards and Technology, 米国標準技術研究所）による Post-Quantum Cryptograhy Project [^NIST] です。

NIST PQC ProjectではRound 1が2016年に69ものアルゴリズム候補から始まり、2020年7月に終了したRound 3で1つの公開鍵暗号及び鍵共有アルゴリズム(Public-key Encryption and Key-establishment Algorithms)と3つのデジタル署名アルゴリズム(Digital Signature Algorithms)の標準化が決定[^NIST-2022]し、標準化が進められています。この決定が大きな影響を与え、ここ数年の動きの活発化に繋がっていると考えられます。2024-03-29現在では、3つのアルゴリズムについてFIPSの草稿が公開されています[^NIST-DRAFT]。Round3で決定したアルゴリズムの標準化と並行して、引き続き4つの公開鍵暗号及び鍵共有アルゴリズムについてRound4で評価されると共に、追加公募した署名アルゴリズムによるRound 1[^NIST-DIG-SIG]も開始しています。これは選考が進む中でアルゴリズムに脆弱性が見つかるなどして、ベースとなる暗号技術が「格子暗号」と「ハッシュ関数署名」に偏ってしまった為、攻撃方法が発見された場合に備えた多様性を確保する意図があります。

[^BSI]: [BSI TR-02102-1: "Cryptographic Mechanisms: Recommendations and Key Lengths" ](https://www.bsi.bund.de/EN/Themen/Unternehmen-und-Organisationen/Standards-und-Zertifizierung/Technische-Richtlinien/TR-nach-Thema-sortiert/tr02102/tr02102_node.html)
[^NIST]: [NIST Post-Quantum Cryptography](https://csrc.nist.gov/projects/post-quantum-cryptography)
[^NIST-2022]: [NIST Post-Quantum Cryptography - Selected Algorithms 2022](https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022)
[^NIST-DRAFT]: [NIST Comments Requested on Three Draft FIPS for Post-Quantum Cryptography](https://csrc.nist.gov/news/2023/three-draft-fips-for-post-quantum-cryptography)
[^NIST-DIG-SIG]: [NIST Post-Quantum Cryptography: Digital Signature Schemes](https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures)

### ハイブリッド方式

耐量子暗号技術は、量子コンピュータでも解読が困難とされている暗号方式ですが、攻撃方法の研究が本格化してから日が浅く、安全性を十分に確信出来る状態とは言い難い状態にあります。従来の暗号技術は、攻撃方法が十分に研究され、現在のコンピュータにおいては安全であると考えられているものの、量子コンピュータによる攻撃が危惧されています。

このような背景から、当面の間は耐量子暗号を使用する際にはハイブリッド方式を使用するという考え方が広まっています。ハイブリッド方式では、通信の鍵交換や認証で耐量子暗号技術と従来の暗号技術の両方を組み合わせることで、一方の暗号技術が破られたとしても、他方の暗号技術により通信の機密性と整合性を担保することが可能となります。具体的な例としては、両方の暗号技術でそれぞれの鍵や認証コードを計算し、その値を結合してハッシュ関数を通すなどの方法が考えられています。

## 暗号通信への適用

### 影響を受けるプロトコル

基本的には公開鍵暗号方式を利用したオンライン鍵共有やデジタル署名を利用しているすべてのプロトコルが影響を受けるため、RFCが存在するものだけでもHTTPS(TLS, X.509証明書), IPsec(IKE), S/MIME(CMS), SSH, DNSSEC, OpenPGPなど、枚挙に暇がありません。安全な通信を行うためにTLSやX.509証明書を利用しているものも数多くあり、非常に多くのプロトコルが影響を受けると言えます。逆にセキュリティを確保するためのレイヤが独立している場合は、例えば下位層のTLSなどのプロトコル・ライブラリが対応すれば、上位層のプロトコルとしては変更が必要ないことも考えられますが、少なくとも影響の有無を含めて個別に評価・検討が必要となるでしょう。

### プロトコルの対応に向けて

一般に通信プロトコルを変更する際には、プロトコル仕様の議論、ソフトウェア・ハードウェアへの実装、実装間の相互運用性の成熟、対応した実装による置き換えといった流れとなりますが、このプロセスには非常に時間を要します。プロトコル仕様の検討だけを考えても、次のような多様な項目の様々な選択肢からデザイン・セキュリティ・パフォーマンス・整合性・拡張性・互換性など多角的な視点で議論して仕様化する必要があり、容易ではないことが分かります。

* PQCアルゴリズムに依存しないフレームワーク部分
    * どの部分にPQC対応が必要か
    * ハイブリッド方式の鍵交換/署名をどう実現するか
    * プロトコルの構造をどうするか
        * PQCアルゴリズムを扱うメッセージを新設する
        * メッセージ構造を維持するがフィールドを増やす
        * メッセージ構造を維持して１つのフィールドに従来型とPQCの２種類の値を詰め込む
        * など
    * など
* PQCアルゴリズムごとに定義する部分
    * フィールドに入れる値を、どのように計算するか
    * フィールドに入れる値の表現をどうするか
        * ASN.1符号化データとして構造を持たせる
        * バイナリ値を単純に結合する
    * 受信した値から、必要な値（プロトコルで使用する共有鍵など）をどのように計算するか
    * など

そこでアルゴリズムの標準化が完了次第速やかにプロトコルの対応を進められるよう、IETFでもアルゴリズムの標準化を待たずにプロトコル仕様の議論が行われています。この議論は個別のWGで行われて来ており情報が散らばっていましたが、PQC対応のサポートやガイダンスの文書化などを行うPost-Quantum Use In Protocols (pquip) Working Groupが2023年2月に立ち上げられました[^PQUIP]。このPQUIP WGによりPQCに関連した文書(RFCやInternet-Draft)やHackasonなどが纏められ資料があり[^PQUIP-STATE]、PQCへの取り組み状況を一望できるようになっています。

[^PQUIP]: [IETF launches post-quantum encryption working group](https://www.ietf.org/blog/pquip/)
[^PQUIP-STATE]: [GitHub - ietf-wg-pquip/state-of-protocols-and-pqc](https://github.com/ietf-wg-pquip/state-of-protocols-and-pqc)

### PQC対応の検討例

PQUIP WGが作成したリストの通り、PQC対応に関して非常に多くの検討・提案がされていますが、特に重要であったり検討が進んでいるものを簡単に紹介します。

#### X.509証明書

現在X.509証明書で使用されている署名アルゴリズムや記載されている公開鍵を利用するアルゴリズムは、量子コンピュータによる解読の恐れがあり、PQCアルゴリズムとのハイブリッド方式をサポートする検討が行われています。
従来の証明書には、通常、主体者の公開鍵と発行者の署名が1種類ずつ記載されています。ハイブリッド方式で電子署名を行うには、1つの証明書に複数の署名や公開鍵を格納出来るよう拡張する必要がありますが、その方法はいくつも提案されています。ここではIETFのHackathonで相互運用の検証が行われている３つの方式を紹介します。これらはフレームワークとしての定義で、具体的なPQCアルゴリズム、例えばML-DSAでのアルゴリズム識別子や公開鍵の署名をどのようなバイト列で表現するかなどは、別途個別に定義する必要があります[^X509-MLDSA]。

##### コンポジット方式[^X509-COMPOSITE]

従来のアルゴリズム + PQCアルゴリズム の組み合わせに１つのアルゴリズム識別子を割り当て、従来は１つの公開鍵や署名を格納していた領域に、両者のアルゴリズムの公開鍵や署名を結合して格納する方式です。
証明書のフォーマットに手を加えずに済み、証明書を利用するプロトコルへの影響も最小限に留められますが、従来のアルゴリズムのみサポートする実装では証明書を読み取ることが出来ません。

##### Alternative拡張方式[^X509-ITU-T]

ITU-TのX.509勧告の `9.8 Alternative cryptographic algorithms and digital signature extensions` で定義された、以下の3つのextensionにPQCアルゴリズムの公開鍵や署名などを格納する方式です。

* subject alternative public key information extension
* alternative digital signature algorithm extension
* alternative signature value extension

このextensionをサポートしない環境では無視するよう指定が可能であるため、従来のアルゴリズムのみサポートする実装でも有効な証明書として認識することが出来ます。ただし証明書を利用するプロトコルの側でサポート状況を検出し、適切なアルゴリズムを選択して通信に使用するよう工夫が必要となります。

##### DeltaCertificate方式[^X509-DELTA]

従来の証明書とPQCアルゴリズムの鍵や署名を含む証明書の２枚の証明書を用意し、その差分をDeltaCertificateDescriptorというextensionとして格納することで１枚の証明書にまとめる方式です。
このextensionをサポートしない環境では無視するよう指定が可能であるため、従来のアルゴリズムのみサポートする実装でも有効な証明書として認識できます。また差分として格納できる情報はAlternative拡張方式より多様であり、PQC対応以外にも、例えばCAやSubjectなどが異なる証明書をまとめて移行に利用するなどの応用が考えられます。
ただしAlternative拡張方式と同様に、証明書を利用するプロトコルの側でサポート状況を検出し、適切なアルゴリズムを選択して通信に使用するよう工夫が必要となります。

[^X509-HACKATHON]: [GitHub - IETF-Hackathon/pqc-certificates](https://github.com/IETF-Hackathon/pqc-certificates)
[^X509-COMPOSITE]: [Datatracker - draft-ounsworth-pq-composite-sigs](https://datatracker.ietf.org/doc/draft-ounsworth-pq-composite-sigs/)
[^X509-ITU-T]: [ITU-T X.509](https://www.itu.int/rec/T-REC-X.509-201910-I)
[^X509-DELTA]: [Datatracker - draft-bonnell-lamps-chameleon-certs](https://datatracker.ietf.org/doc/draft-bonnell-lamps-chameleon-certs/)
[^X509-MLDSA]: [Datatracker - draft-ietf-lamps-dilithium-certificates](https://datatracker.ietf.org/doc/draft-ietf-lamps-dilithium-certificates/)

#### TLS

通信路の機密性を確保するためのオンライン鍵共有、通信相手が正しいことを保証する為の証明書によるサーバ認証・クライアント認証が行われていますが、ここで現在使用されている公開鍵暗号方式のアルゴリズムは量子コンピュータによる解読の恐れがあります。
ハイブリッド方式のオンライン鍵共有を実現するために多くのプロトタイプ実装で採用されている仕様は、X.509証明書のコンポジット方式と同じ考え方を採っています[^TLS-HYBRID]。従来のアルゴリズム + PQCアルゴリズム の組み合わせ毎に1つのグループ(証明書のアルゴリズム識別子に相当するもの。名前の由来はDiffie-Hellmanグループ。具体例としては ffdhe2048, secp256r1, x25519 など)を割り当て、従来は1つの鍵共有データを格納していた領域に、両者のアルゴリズムの情報を結合して格納するという方法です。個々のグループには定数が割り当てられており、鍵共有アルゴリズムのネゴシエーションや、鍵共有データのアルゴリズム種別を伝える為に使用されます。
証明書によるサーバ認証・クライアント認証に関しては、公開鍵や署名にPQCアルゴリズムのみを含む証明書を扱えるプロトタイプ実装は多くありますが、ハイブリッド方式に関しては、形となった提案や実装は見られないようです。

[^TLS-HYBRID]: [Datatracker - draft-ietf-tls-hybrid-design](https://datatracker.ietf.org/doc/draft-ietf-tls-hybrid-design/)

#### IPsec(IKEv2)

IPsecでオンライン鍵共有を行う際には、主にIKEv2プロトコルが使用されます。このオンライン鍵共有で現在使用されている公開鍵暗号方式のアルゴリズムは量子コンピュータによる解読の恐れがあります。
これに対応するため、従来の鍵交換に加えて追加の鍵交換を複数回行うことで、ハイブリッド方式での鍵共有を可能にするメッセージ・シーケンスがRFC 9370[^RFC9370]として発行されています。従来のアルゴリズムとPQCアルゴリズムを最大で8種類まで併用することが可能となっています。RFC 9370もフレームワークの定義であり、具体的なPQCアルゴリズム、例えばML-KEMでのTransformIDの値やKey Exchange Dataをどのようなバイト列で表現するかなどは、別途個別に定義する必要があります[^IPSEC-MLKEM]。

[^RFC9370]: [RFC 9370 - Multiple Key Exchanges in the Internet Key Exchange Protocol Version 2 (IKEv2)](https://datatracker.ietf.org/doc/rfc9370/)
[^IPSEC-MLKEM]: [Datatracker - draft-kampanakis-ml-kem-ikev2](https://datatracker.ietf.org/doc/draft-kampanakis-ml-kem-ikev2/)

### ソフトウェアの対応に向けて

#### Open Quantum Safe Project

Linux FoundationのPost-Quantum Cryptography Alliance[^PQCA]に、Open Quantum Safe (OQS) Project[^OQS]という、PQCの暗号ライブラリ liboqs の開発と、liboqsをOSSソフトウェアに組み込んでのPQC対応のプロトタイピングを行っているプロジェクトがあります。
liboqsは様々なPQCアルゴリズムを統一的なインタフェースで扱える様になっており、多数のアルゴリズムへの対応や比較を容易に行うことが出来ます。現在のliboqsはプロトタイピングと研究の目的に対して提供されており、OQS Project以外でもソフトウェアの実験的PQC対応に利用されています[^OQS-EXTERNAL]。
OQS ProjectはTLSやSSHなどの代表的OSSプロダクトのPQC対応のプロトタイピングを行っています。特にTLSはApache httpd, nginx, haproxy, Chromium, Wiresharkなどの対応が行われており、ブラウザ -> ロードバランサ -> HTTPサーバ の一連の流れをPQC対応させた検証を行うことが可能です。テスト用のWebサーバも提供されており、対応版ChromiumをインストールすればPQCの世界を簡単に体験することが出来ます。

[^PQCA]: [Post-Quantum Cryptography Alliance](https://pqca.org/)
[^OQS]: [Open Quantum Safe Project](https://openquantumsafe.org/)
[^OQS-EXTERNAL]: [External users of OQS](https://openquantumsafe.org/applications/external.html)

#### OQS以外のPQC対応例

まだ数は少ないものの、リリース版又はリリース候補版としてPQC対応が組み込まれたプロダクトも出てきています。ここでは、そのようなプロダクトを幾つか紹介します。

##### SSH

OpenSSH 9.0でx25519とPQCアルゴリズムの１つであるStreamlined NTRU Primeとのハイブリッド方式での鍵交換がデフォルトで利用されるようになりました[^OPENSSH]。PuTTYも0.78で鍵交換アルゴリズムをサポートしており、この組み合わせで利用できます。

[^OPENSSH]: [OpenSSH Release 9.0](https://www.openssh.com/txt/release-9.0)
[^PUTTY]: [PuTTY Changes](https://www.chiark.greenend.org.uk/~sgtatham/putty/changes.html)

##### IPsec (IKEv2)

strongSwanは6.0のベータ版で `RFC 9370: Multiple Key Exchanges in the Internet Key Exchange Protocol Version 2 (IKEv2)` に対応しており[^STRONGSWAN-IETF]、OQSプラグインを利用することでPQCアルゴリズムを使用したハイブリッド方式での鍵交換を行うことが出来ます[^STRONGSWAN-PLUGINS]。また証明書を使った認証で、PQCアルゴリズムによる署名が利用できます。

[^STRONGSWAN-IETF]: [strongSwan 6.0beta - IPsec and Related Standards](https://docs.strongswan.org/docs/6.0/features/ietf.html)
[^STRONGSWAN-PLUGINS]: [strongSwan 6.0beta - What’s New in strongSwan 6.0](https://docs.strongswan.org/docs/6.0/news/whatsNew.html)

OpenIKEDは7.0でStreamlined NTRU PrimeとX25519のハイブリッド方式での鍵交換をサポートした[^OPENIKED]。ただしRFC 9370によるものではないため、相互運用性には期待できない点に注意が必要です。具体的には `TransformType: D-H` の `TransformID` にStreamlined NTRU PrimeとX25519の組み合わせを表す独自の値を割り当て、Key Exchange Payload の `Key Exchange Data` に２つのアルゴリズムの鍵交換データを結合したものを詰め込む形式となっています。

[^OPENIKED]: [OpenIKED - openiked-7.0-relnotes](https://ftp.openbsd.org/pub/OpenBSD/OpenIKED/openiked-7.0-relnotes.txt)