This post is also available in the following languages. English, Korean

PQCへの旅路：量子コンピュータ時代にデータを守るために

はじめに

こんにちは。Security R&D チームのHan Juhongです。私たちのチームは、LINEヤフーグループのサービス全般のセキュリティ強化を目的に、さまざまなセキュリティ技術の研究、開発、コンサルティングを担当しています。

現在、私たちが使用している多くのITサービスでは、安全なサービスを提供するためにさまざまな暗号技術が使用されています。LINEヤフーグループも、エンドツーエンドの暗号化技術であるLetter Sealingから、簡単なユーザー認証を実現するFIDO（Fast Identity Online）、安全なバックアップシステムの構築など、ユーザーが安心してサービスを利用できるように、さまざまな場面で暗号技術を活用しています。

ところが最近、量子コンピュータに関する研究が活発になり、量子コンピュータの開発が現実味を帯びてきたことで、私たちが現在安全だと信じて使用している暗号技術の安全性に問題が生じる可能性が出てきました。この問題に備えるために、多くの専門家がPQC（Post-Quantum Cryptography）という分野を研究しています。今回の記事では、量子コンピュータの開発が現在の暗号システムにどのような影響を与えるのか、そして量子コンピュータの時代に私たちのデータをどのように守ることができるのかについてお話ししたいと思います。

量子コンピュータの脅威に現代の暗号アルゴリズムは安全なのか？

量子コンピューティングは、従来のコンピュータとはまったく異なる方法でデータを処理する技術です。現在使用しているコンピュータはビット(bit)を使ってデータを0と1で表しますが、量子コンピュータはキュービット(qubit)を使い、0と1の状態を同時に持つことができます。この特性のおかげで、量子コンピュータは従来のコンピュータよりも特定の計算をはるかに高速に処理することが可能です。

量子コンピューティングの核心的な概念は、重ね合わせ（superposition）とエンタングルメント（entanglement）です。重ね合わせ状態のキュービットは、0と1の状態を同時に持つことができ、並列計算を行うような効果を生み出します。また、エンタングルメントしたキュービットはお互いの状態に強く依存しており、一方のキュービットの状態が決定されると、他方のキュービットの状態も即座に決まります。このような量子コンピュータの特性により、素因数分解などの特定の問題を非常に高速に解決できるようになります。

2023年にevolutionQのMichele Mosca博士とMarco Piani博士がGlobal Risk Instituteのライセンスで発行した「QUANTUM THREAT TIMELINE REPORT 2023」レポートによると、「キーのサイズが2,048ビットのRSA暗号を1時間以内に破ることができる量子コンピュータ」が登場する可能性について、約27%の専門家が10年以内に50%以上と予測し、期間を30年に延ばすと、約78%の専門家が70%以上と予測したそうです。

このように、量子コンピュータの発展はまだ初期段階にありますが、多くの専門家は数百または数千のキュービットを扱える量子コンピュータの開発がそう遠くないと見ています。これは現在、量子コンピュータの開発をリードしているIBMの量子コンピュータ開発ロードマップからも予測できます。最近IBMが発表したHeronプロセッサは、133個のキュービットを安定的に扱うことができ、モジュール型の構成により柔軟に拡張できる設計を備えています。現在は3つのプロセッサで399キュービットまで拡張するのが限界ですが、2033年以降にはプロセッサあたり2,000キュービットを扱うことを目標としており、これをモジュール式に構成すれば、本当に数千、数万のキュービットを使えるようになるかもしれません。

では、将来数万個のキュービットを扱える量子コンピュータが開発された場合、現代の暗号システムにはどのような影響があるのでしょうか？

対称鍵暗号とハッシュ関数

対称鍵暗号は、データの暗号化と復号化に同じ鍵を使用するアルゴリズムです。一般的に、高速で効率的であり、大量のデータブロックを処理するのに適しています。このような利点があるため、一般的なデータの暗号化にはほとんどの場合、対称鍵暗号が使用されていると考えてよいでしょう。

対称鍵暗号の安全性は一般的に鍵の長さによって決まります。つまり、128ビットの鍵を使用するアルゴリズムは、128ビットのセキュリティ強度を持つことになります。ここでのセキュリティ強度とは、その暗号の鍵を見つけるために必要な計算量を指します。例えば、128ビットのセキュリティ強度というのは、暗号鍵を見つけるために $2^{128}$ 回の計算が必要であることを意味します。 $2^{128}$ 回の計算は、現在の計算能力では約10兆年以上かかるため、現実的な時間内では解読できないということになります。

しかし、このような対称鍵暗号はGroverのアルゴリズムによって無力化される可能性があります。Groverのアルゴリズムは、量子コンピュータで動作する量子アルゴリズムで、非線形検索問題を解く時間を $O(N)$ から $O(\sqrt{N})$ に大幅に短縮することができ、対称鍵暗号やハッシュ関数の安全性に大きな影響を与えます。

例えば、Groverのアルゴリズムを使用して対称鍵暗号を攻撃すると、セキュリティ強度が半分になり、128ビットの対称鍵暗号化アルゴリズムのセキュリティ強度は64ビットになります。これにより、10兆年以上かかっていた攻撃時間が約6か月に短縮される結果をもたらします。

ハッシュ関数も同様の状況です。ハッシュ関数は、データをランダムなビット列に見える固有の固定長の出力値に変換する関数です。ハッシュ関数は、入力値が1ビット異なるだけでまったく異なる出力値を生成するため、主にデータの整合性検査に使用され、改ざんも非常に困難です。

このようなハッシュ関数において、一般的に $N$ ビットのハッシュに対して、逆像（ハッシュ値に対応する元のデータ）を見つける問題は $2^N$ 回の計算が、衝突ペア（同じハッシュ値を持つ異なる入力データ）を見つける問題は $2^{\frac{N}{2}}$ 回の計算で解けると言われています。しかし、Groverのアルゴリズムを使用すると、それぞれ $2^{\frac{N}{2}}$ 、 $2^{\frac{N}{3}}$ 回の計算で解くことが可能になります。

非対称鍵暗号

非対称鍵暗号（公開鍵暗号）は、データの暗号化と復号化、および署名の作成と検証の際に異なる鍵を使用するアルゴリズムです。一方の鍵は公開鍵で誰でもアクセス可能ですが、もう一方の鍵は秘密鍵で所有者のみがアクセスできます。非対称鍵暗号は、主に鍵交換、電子署名、認証などに使用されます。代表的な非対称鍵暗号のアルゴリズムには、IFC系列（Integer Factorization Cryptography）のRSA（Rivest-Shamir-Adleman）や、ECC系列（Elliptic Curve Cryptography）のECDSA（Elliptic Curve Digital Signature Algorithm）、ECDH（Elliptic-curve Diffie–Hellman）などがあります。

現代の公開鍵暗号アルゴリズムの安全性は、対称鍵暗号やハッシュ関数とは異なり、数学的に解くことが非常に難しい問題に基づいています。そのため、これらの数学的問題を効率的に解決するアルゴリズムが存在しないという前提のもとで、安全性が保証されています。

しかし、このような非対称鍵暗号はShorのアルゴリズムによって無力化される可能性があります。Shorのアルゴリズムは、量子コンピュータで動作する量子アルゴリズムで、RSAやECC系列の暗号の基盤となる問題を短時間で解決することができます。例えば、大きな数の素因数分解が難しいという特性を利用して設計されたRSAアルゴリズムの場合、現在のコンピュータでは2,048ビットの鍵の素因数分解に数兆年かかるとされていますが、Shorのアルゴリズムを使用すれば、この作業を非常に短い時間（約2,000万キュビットの量子コンピュータで約8時間（参考））で解決することが可能です。

量子コンピュータの脅威に備える方法

対称鍵暗号化と非対称鍵暗号化は、金融をはじめとするITシステム全般で広く利用されており、データ保護の重要な要素として確立されています。そのため、セキュリティの脅威に備えることが非常に重要です。では、量子アルゴリズムから私たちのデータをどのように守ることができるのか、見ていきましょう。以下は、それぞれの暗号化方式に対して脅威となる量子アルゴリズムと、その対応策をまとめた表です。

分類	量子アルゴリズム	対応方法	対応前	対応後
対称鍵暗号	Grover アルゴリズム	鍵の長さの増加	128ビット、192ビット、256ビット	256ビット以上
ハッシュ関数	Grover アルゴリズム	出力長の増加	224ビット、256ビット、384ビット、512ビット	384ビット、512ビット以上
非対称鍵暗号	Shor アルゴリズム	アルゴリズムの置き換え	IFC、ECC、FFC	Lattice、Code、Isogeny、Hash、Multivariate

幸い、対称鍵暗号での対策はそれほど難しくありません。現在の対称鍵暗号アルゴリズムはほとんどが256ビットの鍵をサポートしているため、128ビットや192ビットの鍵を使用しているシステムでは、鍵の長さを256ビットに増やし、ハッシュ関数はより長い出力を持つアルゴリズムに置き換えることで、128ビット以上のセキュリティ強度を維持できます。もちろん、すでに配布されたシステムのアルゴリズムを置き換えるのは簡単ではないかもしれませんが、安全性が十分に証明されているアルゴリズムがすでに存在するため、新たにアルゴリズムを開発する必要はありません。

しかし、非対称鍵暗号は、対称鍵暗号やハッシュ関数のように既存のアルゴリズムを再利用するだけでは対応できません。アルゴリズムの設計に使用された基盤となる問題自体が破られるため、量子アルゴリズムでも解決が困難な新しい基盤問題を使ったアルゴリズムを作る必要があります。このため、現在多くの専門家が、量子コンピュータに備えたPQC（Post-Quantum Cryptography）の研究を進めています。

PQCの標準化と移行

CRQC（Cryptographically Relevant Quantum Computer）は、NSA（National Security Agency、米国国家安全保障局）が、実際に暗号システムを攻撃できる量子コンピュータを指す際に使用する用語です。PQCは、CRQCの攻撃にも耐えることができるアルゴリズムを意味し、そのため量子耐性暗号（Quantum-Resistant Cryptography）とも呼ばれています。したがって、PQCの範囲には、鍵長が増加した対称鍵暗号や出力長が長くなったハッシュ関数も含まれる場合があります。しかし一般的には、従来の環境および量子環境の両方で解くことが難しい数学的問題に基づいて作られ、従来の公開鍵暗号アルゴリズムを置き換えることができるアルゴリズムだけをPQCと呼ぶことが多いです。

PQCアルゴリズムの標準化状況

2017年、米国国立標準技術研究所（National Institute of Standards and Technology、NIST）は、CRQCの攻撃にも耐えられる暗号アルゴリズムを標準化するために、PQCコンテストを開始しました。これにより、世界中の専門家たちがさまざまな数学に基づいたアルゴリズムを提出しました。それらのアルゴリズムは、安全性だけでなく、既存のコンピューティング環境でのパフォーマンス、置き換えの容易さ、完全前方秘匿性、サイドチャネル攻撃に対する耐性、誤用に対する耐性など、さまざまな指標で評価されました。

PQCコンテストには合計69のアルゴリズムが提出され、数年にわたる評価プロセスで多くのアルゴリズムが脱落しました。合計3回のラウンドの末、2022年7月に次の4つのアルゴリズムが最終的な標準化候補として選ばれました。そして2024年に、これらのアルゴリズムが最終的に連邦情報処理標準（Federal Information Processing Standard, FIPS）として承認されました。

CRYSTALS-Kyber（ML-KEM）：格子基盤の非対称暗号化および鍵交換アルゴリズム
CRYSTALS-Dilithium（ML-DSA）：格子基盤の電子署名アルゴリズム
FALCON（FN-DSA）：格子基盤の電子署名アルゴリズム
SPHINCS+（SLH-DSA）：ハッシュ基盤の署名アルゴリズム

しかし、選定されたアルゴリズムの中で、KEMアルゴリズムは格子ベースのアルゴリズムが1つしかなかったため、NISTは格子ベースの暗号の安全性に問題が生じた場合に備えて、他の基盤で作られたKEMアルゴリズム（BIKE、Classic McElliece、HQC、SIKE）を候補にして第4ラウンドを進めています。また、第4ラウンドには電子署名アルゴリズムが含まれていないため、電子署名アルゴリズムを対象とした追加ラウンドも進行中です。

脅威モデルと移行開始時期

多くの専門家は、今からPQCへの移行を準備すべきだと述べています。まだCRQCの開発には時間がかかるため、この文章を読んでいる方の中には、なぜもうPQCを研究し、マイグレーションの準備をしなければならないのか疑問に思うかもしれません。その理由は、HNDL攻撃とMoscaの定理によって説明できます。

HNDL（Harvest Now, Decrypt Later）攻撃とは、現在のデータを収集し保存しておき、将来的にCRQCが利用可能になった時点で復号する攻撃を指します。このような攻撃は、長期間にわたってセキュリティを維持する必要がある、機密データやファームウェア、ソフトウェアに使われる署名など、寿命が長いデータに影響を及ぼす可能性があります。したがって、まだ量子攻撃が現実化していなくても、それに備えた暗号アルゴリズムを事前に開発し、配布する必要があるのです。

では、PQCへの移行はいつ始めるべきでしょうか？これについては、Moscaの定理を用いて、おおよその時期を計算することができます。この理論は、3つの主要な変数を考慮に入れています。

$x$ ：現在使用している暗号アルゴリズムの安全性が維持されるべき期間
$y$ ：PQCアルゴリズムを設計、標準化、配布、マイグレーションするのにかかる時間
$z$ ：量子コンピュータが十分に強力になり、現在の暗号アルゴリズムを破ることができる時点までの時間

私たちがCRQCの脅威から安全であるためには、次の数式を満たす必要があります。

$x + y < z$

つまり、PQCアルゴリズムの開発およびマイグレーションにかかる時間（ $y$ ）と、現在使用している暗号化アルゴリズムの有効期間（ $x$ ）の合計が、CRQCが開発されるまでの時間（ $z$ ）より短くなければなりません。

現在、多くの専門家は、最近の科学技術の進展が非常に速いため、量子コンピュータの開発速度を慎重に見積もったとしても、CRQCの開発時期はおおよそ2030年頃になると予想しています。この予測に基づくと、PQCアルゴリズムの本格的な研究を開始した時点から、 $z$ はおおよそ20年程度と考えることができます。

では、 $y$ に該当するマイグレーションにかかる時間はどうでしょうか？

IT環境でのマイグレーション作業は、運用環境に応じて考慮すべき要素が異なり、次のリリースまでに数年かかる環境もあるため、予想以上に多くの時間が必要です。過去の移行事例からもこれが確認できます。例えば、SHA-2やAESの場合、標準化後ほとんどのシステムに適用されるまで約10年かかり、TLSもTLS 1.2への移行には10年以上かかりました。

ハンマーが打ち込まれた時期は、各アルゴリズムに対する実際の攻撃が成功した時期を指します。

PQCへの移行プロセスは、これまでのマイグレーション作業とは異なり、より複雑で広範囲な作業になると予想されます。そのため、マイグレーションにかかる時間（ $y$ ）は少なくとも10年以上かかると考えられます。この前提に基づくと、今からマイグレーションの準備を始める必要があることがわかります。

実際に、各国のPQC移行に向けたロードマップにもこのような前提が反映されています。アメリカのNSAは、PQCアルゴリズムを含むCNSA 2.0（Commercial National Security Algorithm Suite 2.0）を発表し、このロードマップでは、ほとんどの分野で2024年から準備を開始し、2033年までに移行を完了することを目標としています。このロードマップに合わせてホワイトハウス（参考）や主要機関は新しい政策や規定を発表しており、ドイツのBSI（参考）、英国のNCSC（参考）、フランスのANSSI（参考）、カナダのCSE（参考）も、それぞれPQC移行のためのロードマップや、公共および民間向けのガイドラインを発表しています。

出典: Announcing the Commercial National Security Algorithm Suite 2.0

PQC移行を準備する方法：ハイブリッドモード

では、私たちはどのようにしてPQCへの移行を準備すればよいのでしょうか？PQC移行プロセスについては専門家の間でもさまざまな意見がありますが、現在のところハイブリッドモードを用いた段階的な移行が多く採用されています［参考資料：1, 2, 3, 4, 5, 6］。

ハイブリッドモードは、従来の非対称鍵暗号アルゴリズムとPQCアルゴリズムを同時に使用する方式です。専門家がPQC単独ではなくハイブリッドモードを採用する最大の理由は、現在提案されている複数のPQCアルゴリズムに未知の脆弱性が存在する可能性に備えるためです。現在のPQCアルゴリズムは、比較的新しい技術であり、研究が始まってからそれほど長い時間が経っていないため、理論的な欠陥や現時点では発見されていない脆弱性が存在する可能性があります。そのため、PQC移行中に新たな脆弱性が発見されたとしても、従来の暗号アルゴリズムによって保護を継続できるようにハイブリッド構造が選ばれるのです。

ハイブリッドモードを選択することで、PQCアルゴリズムが完全に検証され安定するまで段階的に移行でき、新たな脆弱性が発見された場合でも、従来の暗号アルゴリズムがヘッジ（hedge）として機能するため、セキュリティリスクを最小限に抑えることができます。

実際に、NISTのPQCコンペティションに提出され、第3ラウンドの最終候補に残っていたアルゴリズムRainbowは、新たな鍵回復攻撃が発表されたことでコンペティションから脱落しました（参考）。また、かつてGoogle Chromeに実験的に導入されたSIKEアルゴリズムでも脆弱性が発見されましたが（参考）、ハイブリッド構造を採用していたおかげで、セキュリティ事故には至らなかった事例もあります。

さらに、ハイブリッドモードは、既存の仕様にPQCアルゴリズムを追加する形で構成できるため、比較的簡単に既存製品のプロトコルにおいて、可用性や各種規制要件を満たすことができるという利点もあります。これにより、現時点で移行を準備する上で、最も効果的な方法として評価され、採用されています。

もちろん、ハイブリッドモードにもリスクは存在します。ハイブリッド構造では2つの暗号を同時に使用するため、設計や実装が複雑になるだけでなく、相互運用性の問題や鍵管理の煩雑さなどの追加課題が生じ、予期しないセキュリティ脆弱性が発生する可能性があります。また、ハイブリッド構造は一時的な解決策にすぎないため、PQCの安全性が十分に検証された後は、最終的にはPQC単一構造に移行する必要があります。過去のAESやSHA-2の事例からもわかるように、このような移行プロセスは多大なコストと時間を要する複雑な作業です。したがって、ハイブリッドモードは現在のセキュリティシステムを維持しつつ、量子コンピュータの脅威に備えるための重要な戦略である一方で、長期的な解決策ではないことを心に留めておくべきです。

結びに

今回の記事では、量子コンピュータの登場が現代の暗号システムの安全性をどのように脅かすのかについて説明し、その状況に備える理由と方法を見てきました。前述のとおり、対称鍵暗号やハッシュ関数の場合は比較的簡単に解決できますが、非対称鍵暗号については新しいアルゴリズムの開発と適用に多くの時間が必要です。そのため、ハイブリッドモードのような暫定的な解決策を用いて、非対称鍵暗号の移行プロセスを段階的に準備していくことが重要です。

各国の政府やセキュリティ機関が発表しているPQC移行のロードマップからもわかるように、これからの10年、20年はPQCへの移行を準備し、実行する上で重要な時期となります。量子コンピュータとPQCに関する研究は着実に進行しており、今後も多くの変化と進展が予想されるため、私たちのデータを未来にわたって守るためには、これらの変化に迅速に適応していく必要があります。

今回の記事が、量子コンピュータ時代の暗号技術とセキュリティに関する理解を深める一助となれば幸いです。次回の記事では、LINEヤフーグループがPQC移行のためにどのような取り組みを行っているかについて詳しく取り上げる予定ですので、ぜひご注目ください。それでは、この辺りで締めくくらせていただきます。長文をお読みいただき、ありがとうございました。