耐量子暗号

耐量子暗号は、ショアのアルゴリズムによって破られるRSA暗号や楕円曲線暗号に代わり、量子コンピュータにとっても困難であると信じられている問題に安全性の根拠を置く公開鍵暗号方式を開発するものです。

Definition

耐量子暗号は、大規模な量子コンピュータを装備した攻撃者に対しても安全性を維持するように設計された古典的（非量子的）な暗号アルゴリズムであり、効率的な量子アルゴリズムが知られていない問題に依拠しています。

Scope

このトピックでは、量子脅威（ショアのアルゴリズムとグローバーのアルゴリズム）、量子耐性のある主要な暗号方式のファミリー（格子ベース、符号ベース、ハッシュベース、多変数）、NISTの標準化への取り組みとその選定アルゴリズム（ML-KEM、ML-DSA、SLH-DSA）、および「今収集して後で解読する（harvest-now-decrypt-later）」やハイブリッド展開などの移行に関する懸念事項について扱います。量子ハードウェアを使用する量子暗号（量子鍵配送）は対象外です。

Core questions

• 量子コンピュータはなぜRSA暗号や楕円曲線暗号を破るが、対称暗号にはそれほど深刻な影響を与えないのか？
• どのような困難な問題（格子、符号、ハッシュ）が量子攻撃に耐えると信じられているのか？
• NISTは標準化のためにどの方式を選定し、それらのトレードオフは何か？
• 「今収集して後で解読する」脅威とは何か、なぜそれが緊急性を生むのか？
• 移行中に耐量子方式と古典方式はハイブリッド展開でどのように組み合わせられるのか？

Key concepts

• ショアのアルゴリズム
• グローバーのアルゴリズム
• 格子ベース暗号（学習誤差）
• 符号ベース暗号
• ハッシュベース署名
• ML-KEM（Kyber）とML-DSA（Dilithium）
• 今収集して後で解読する
• クリプトアジリティ
• ハイブリッド鍵交換

Key theories

ショアのアルゴリズムによる量子脅威

ショアの量子アルゴリズムは、整数を素因数分解し、離散対数を多項式時間で計算できるため、RSA、Diffie-Hellman、および楕円曲線暗号を破ります。グローバーのアルゴリズムは総当たり攻撃を二次的に高速化するに過ぎないため、対称鍵は単に鍵長を倍にするだけで十分です。

量子困難な問題群

耐量子の安全性は、格子における学習誤差問題や最短ベクトル問題、ランダムな線形符号の復号、ハッシュ関数の安全性といった問題に求められます。これらの問題に対しては、効率的な量子アルゴリズムは知られていません。

Mechanisms

ML-KEM（CRYSTALS-Kyberに由来）のような格子暗号は、モジュール学習誤差問題（module learning-with-errors problem）の困難性に基づいて鍵カプセル化を行い、秘密鍵のみが除去できる小さなランダムな「誤差」を追加します。ハッシュベース署名（SLH-DSA/SPHINCS+）は、ハッシュ関数の安全性のみから署名を構築します。符号ベース暗号は、ランダムに見える線形符号の中に復号可能な構造を隠します。移行では通常、古典暗号と耐量子暗号を組み合わせたハイブリッド構成が用いられ、どちらか一方が生き残れば安全性が保たれます。

Clinical relevance

移行はすでに展開されているシステムで進行中です。主要なブラウザやTLSライブラリはハイブリッドML-KEM鍵交換を有効にし、メッセージングアプリ（SignalのPQXDH）やSSHは耐量子ハンドシェイクを追加しています。標準化団体は、組織に対し暗号の棚卸しと移行計画の策定を促しています。「今収集して後で解読する」リスクは、長期的な機密性を必要とするデータが今日から量子攻撃に対して保護されるべきであることを意味します。

Evidence & guidelines

NISTは2024年に最初の耐量子標準を確定しました。鍵カプセル化にはFIPS 203（ML-KEM）、署名にはFIPS 204（ML-DSA）とFIPS 205（SLH-DSA）です。NIST、NSA（CNSA 2.0）、および各国の機関からのガイダンスが移行のタイムラインを設定しています。移行期間中のベストプラクティスとしては、耐量子アルゴリズムと古典アルゴリズムを組み合わせたハイブリッド方式が推奨されます。

History

1994年のピーター・ショアのアルゴリズムは、量子コンピュータが主要な公開鍵システムを破ることができることを示し、代替手段の探求を促しました。格子ベース暗号は、Ajtaiの最悪ケースの困難性に関する結果やRegevの学習誤差問題（2005年）を通じて進歩しました。NISTは2016年に公開標準化プロセスを開始し、複数回のラウンドを経てCRYSTALS-Kyberなどを選定し、2024年に最初の標準（FIPS 203-205）を公開しました。

Key figures

• Peter Shor
• Daniel J. Bernstein
• Tanja Lange
• Oded Regev
• Chris Peikert

Seminal works

• shor1997
• nist2024mlkem
• bernstein2017

Frequently asked questions

RSAを破ることができる量子コンピュータはすでに存在しますか？

いいえ。現在の量子コンピュータは、実際の鍵サイズでショアのアルゴリズムを実行するには、あまりにも小さくノイズが多いです。懸念されるのは将来の機械であり、今日暗号化されたデータが、そのような機械が存在するまで保存され、その後解読される可能性があるという事実と結びついています。

耐量子暗号には量子ハードウェアが必要ですか？

いいえ。耐量子方式は通常の古典コンピュータ上で動作します。これらは単に、量子攻撃者にとっても困難であると信じられている数学的問題に依拠しているだけです。量子ハードウェアを使用する量子鍵配送は、別の手法です。