2026/04/21 1:37
量子コンピュータが、128 ビットの対称鍵に対する脅威ではない
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
元のサマリーは流れと明晰さの点で優れており、主要なメッセージを効果的に捉えています。「全ての主要なキーポイントが反映されている」と厳密に準拠させるためには、Grover 攻撃を並列化する際の困難性の具体的な理由を追加するか、CNSA 2.0/BSI を名称で明示することも可能ですが、現在のバージョンは提供されたテキストに基づき非常に読みやすく正確です。
本文
暗号学上重要な量子コンピュータの脅威が進展するにつれ、ショアのアルゴリズムによって脆弱である現在展開中の非対称暗号素数——鍵交換（ECDH）およびデジタル署名（RSA、ECDSA、EdDSA）——の置換が急務となっています。ただし、これに対照的に、既存の対称暗号アルゴリズム（AES、SHA-2、SHA-3）やそれらの鍵長には影響はありません。
量子コンピュータが対称暗号の鍵強度を「半減させる」という一般的な誤解があります。すなわち、128 ビットのセキュリティを得るために 256 ビットの鍵が必要とするという考えです。これは量子アルゴリズムによるスピードアップの正確な解釈ではなく、どのコンプライアンスガイドラインにも反映されていません。この誤解は、実際になくてはならないポストクオンタム移行作業からエネルギーと注意を逸らせるリスクをもたらします。この誤解の多くは、別の量子アルゴリズムであるグローバー法（Grover's algorithm）の適用範囲に対する誤った理解に基づいています。
AES-128 は量子コンピュータに対して安全です。SHA-256 も同様です。ポストクオンタム移行に伴い鍵長を変更する必要はありません。これは専門家および標準化機関の間でほぼ共通見解となり、この認識を IT コミュニティ全体へ広める必要があります。本稿の残りは、技術的な根拠と関連する権威のある文献への言及を通じて、この主張を支持します。
グローバー法のスピードアップ
グローバー法は、非構造された関数 $f$ に対して入力空間のサイズ $N$ で「正しい答え」を検索することを可能にする量子アルゴリズムです。これは $f$ の呼び出しを $\pi/4 \times \sqrt{N}$ 回行うことを意味します。一般的には、AES-128 の鍵は $2^{64}$ という「時間」で発見できるという解釈がなされますが、実際にはそのような攻撃を単一のシーケンシャルスレッドとして実行すれば数千年かかるため、現実には可能とはいえません。また、並列化を行うと総コストが増大します。
グローバー法について理解すべき重要な点はいくつかあります：
- 関数オラクル $f$ は量子回路の一部として実装する必要があります；
- オラクルの呼び出しはシリアルに順次行わなければなりません；
- 特に重要なのは、Zalka (1997) の議論にあるように、検索空間を分割するという方法以外に、攻撃を並列化する方法はないということです。
最後の点がなぜ重要なのかといえば、通常のブルートフォース攻撃とは異なり、「非常に並列化しやすい（embarrassingly parallel）」性質を持たないため、検索空間を分割するとグローバー法による 2 乗のスピードアップが減少してしまうからです。
64 ビットの鍵に対する古典的なブルートフォース攻撃を考えてみます。各試行に 5 ナノ秒（3GHz で約 16 サイクル）かかります。これを単一の CPU 上で実行するには、ほぼ $2^{64} \times 5 \text{ ns} \approx 3,000$ 年間かかることになります。そこでこれを $2^{16} = 65,536$ 個の CPU で並列化し、それぞれ $2^{(64-16)} = 2^{48}$ の鍵を探索します。これにより所要時間はわずかに 16 日を超えることになります。システム全体の処理量（$2^{16} \times 2^{48} = 2^{64}$）は変化していないことに注意してください。これが 64 ビット鍵が弱いとみなされる理由です（効率的に並列探索可能だから）。もし攻撃がシリアルに行わなければ危険はありませんでした。
次に、128 ビット鍵に対するグローバー攻撃を見てみましょう。やはり $\sqrt{2^{128}} = 2^{64}$ の操作を連続して実行するのは不可能ですので、再度 $2^{16}$ 個の量子コンピュータで並列化し、それぞれ $2^{(128-16)} = 2^{112}$ の鍵を探索します。
各インスタンスでは $\sqrt{2^{128} / 2^{16}} = 2^{56}$ の作業を行う必要があります。ここが重要な点ですが、これは $2^{48}$ ではありません！検索空間の $2^{16}$ 倍の縮小率が平方根の中にあるため、各インスタンスで得られるのは $2^8$ 分の作業削減にしかならず、古典的には $2^{16}$ 分とらえるからです。
結果として、システム全体の処理量は $2^{64}$ から $2^{56} \times 2^{16} = 2^{72}$ に増大し、並列化によってグローバー法の 2 乗スピードアップが薄まってしまいました。
数値検証
これでグローバー法がなぜ並列化しないかの直感が得られますが、まだ脅威かどうかを決めるには具体的なオーダーでの計算が必要です。
まず、連続して実行可能なオペレーション（ゲート）の数を決定しなければなりません。慎重さを欠かすため、超伝導量子ビットのような高速クロックの量子アーキテクチャを想定し、1 ゲートを 1 マイクロ秒とするものとします。攻撃を継続的に行い（停電や保真度の低下なし！）、期間を 10 年とすれば、最大深さ（gate depth）は $10 \text{ years} / 1 \text{ µs} \approx 2^{48}$ に達します。
次に、量子回路内部で AES-128 を計算するために必要なシリアルゲートの数を把握する必要があります。Liao と Luo (2025) は、深さ 232 の T ゲート（かつ回路の「幅」が 724、これは並列動作する論理量子ビット数に相当）を持つ AES-128 用の高度に最適化されたグローバーオラクルを提供しています。
ここで、各インスタンスの最大深さ $2^{48}$ （すなわち、これらの仮想的で高速かつ完全な量子コンピュータ上で 10 年以内に完了）を保証する最小並列化因子を求解します： $$ \pi / 4 \times \sqrt{2^{128} / x} \times 232 = 2^{48} $$ $$ x \approx 2^{47} $$
つまり、AES-128 をグローバー法で破るためには、10 年間にわたって並列して動作する 724 の論理量子ビットを備えた 140 兆個の量子回路が必要となります。
この攻撃のコストを測る別の方法として DW コスト（深さ × 幅の積）があります。これは古典計算におけるサイクル数とコア数の積に概して相当します： $$ \pi / 4 \times \sqrt{2^{128} / 2^{47}} \times 232 \times 724 \times 2^{47} \approx 2^{104.5} $$
注目すべきは、ショアのアルゴリズムの実行例や量子誤り訂正のように年々大幅に改善される項が少ないことです。最適化の余地があるのは AES-128 グローバーオラクルの深さ (232) と幅 (724) の 2 つだけです。しかしこれらは総コストに寄与するのはわずか 17 ビトであり、さらに改善の余地はほぼありません。Liao と Luo (2025) は Grassl ら (2015) の最初の推定量から 7.5 ビト、Jaques ら (2019) の最初のグローバー特化推定量からは 1.5 ビト削減しました。
ショア法との比較
ショア法について触れますが、これは最近議論された 256 ビット楕円曲線に対する量子攻撃と比較するとどうなるでしょうか。実は、これらも不確実と信じたり信じたりする人々がいますし、私もそれらを真剣に受け止めるべきだと主張してきました。
Babbush ら (2026) は、ゲート数が $70\text{M} \approx 2^{26}$ のショア法の実行を示唆しており、これは「高速」なゲート時間 10 マイクロ秒を有するアーキテクチャ上で数分で実行可能です（私たちは前述の通りより保守的な仮定を行っていました）。 $$ 2^{104.5} / 2^{26} = 2^{78.5} $$
つまり、Grover 法による AES-128 の破棄は、Shor 法による 256 ビット楕円曲線の破棄よりも $2^{78.5}$ 倍（約 430 兆兆兆兆倍）高価です。
NIST も同意している
米国国立標準技術研究所（NIST）は、国際的なポストクオンタム暗号競技会を実施し、ML-KEM および ML-DSA の仕様文書を作成した標準化機関です。NIST は AES-128 を安全であるとみなすだけでなく、ポストクオンタム素数に対するセキュリティの基準として採用しています。AES-128 は定義上カテゴリー 13 のポストクオンタムアルゴリズムです。
AES-128 の使用を正当化する際、NIST は上記の説明された観測を引用し、「MAXDEPTH」という概念を導入します。これは並列化を強制し、グローバー法の二次元的スピードアップを制限する最大シリアル計算量に他なりません。これらの参照素数に基づくセキュリティカテゴリは、直感的な分析よりもはるかに多くの量子耐性を提供することがわかります。例えば、カテゴリー 1, 3, 5 はブロック暗号に基づいて定義されており、グローバー法による二次元的量子スピードアップを用いて破られます。しかし、グローバー法には長時間かかるシリアル計算が必要であり、実用上は困難です。現実的な攻撃では、アルゴリズムの多数の小型インスタンスを並列に実行する必要があり、その際量子スピードアップの効果は大幅に減少します。
NIST の計算では Grassl ら (2015) のより最適化されていない（つまりより保守的でない）AES 量子回路を使用していますが、ゲート速度についてはより高速（つまりより保守的な）仮定を採用しています（Liao と Luo (2025) ではなく）。それでも大まかに同程度の結果となり、同じ結論に至ります。
さらに証拠として、NIST IR 8547 ipd "Transition to Post-Quantum Cryptography Standards" では、量子耐性のある暗号への移行において、2035 年までにすべての量子脆弱なアルゴリズムを禁止すると定めています。しかし、同文書はセクション 4.1.3 で AES のすべての鍵長が引き続き許可されていることを再度強調しています。NIST が既存に対称暗号に関する標準（ハッシュ関数、XOF、ブロック暗号、KDF、DRBG など）は、公開鍵暗号の標準（SP 800-56A, SP 800-56B, FIPS 186 など）よりも既知の量子攻撃に対してはるかに耐性が高いと結論付けています。特に、NIST のポストクオンタム標準化プロセスにおけるパラメータセットの評価のための 5 つのセキュリティ強度カテゴリのうち、少なくともカテゴリー 1 のセキュリティ要件を満たすと見なされる、128 ビット以上の古典的セキュリティを提供するすべての NIST 承認対称暗号素数は該当します（テーブル 1 を参照）。
最後に、「ポストクオンタム暗号に関する FAQ」には「AES の鍵長を倍にすべきでしょうか」という質問への明確な回答があります（強調は著者）：
量子コンピュータの脅威に対抗するために、現在 AES の鍵長を倍にすべきでしょうか？（2018/11/18 追加） グローバー法は、古典的な場合よりも 2 乗分の少ないステップでブルートフォース鍵検索を実行することを量子コンピュータに可能にします。字面の意味をとれば、これは量子コンピュータを持つ攻撃者が、古典的なコンピューターしか持たない攻撃者よりも長い鍵（最大 2 倍）を持つ対称暗号を攻撃できることを示唆しています。しかし、この結果から疑われるほど劇的にスピードアップすることはないと示唆するいくつかの緩和要因があります。まず、量子コンピューティングハードウェアは古典的なハードウェアよりも構築し使用する方がコストがかかる可能性が高いことです。さらに、Zalka によれば、1997 年に証明されている通り、完全な二次的なスピードアップを得るためには、グローバー法のすべてのステップをシリアルに実行する必要があります。実際の世界では、暗号への攻撃は大量に並列処理を使用するため、グローバー法の利点は小さくなります。 これらの緩和要因を考慮すると、Grover 法は AES を攻撃するための実質的な利点を与えず、AES-128 は今後数十年間も安全であると考えるのが妥当です。さらに、量子コンピュータが予想以上に安価であるという可能性があっても、Grover 法を並列化する際の既知の困難さにより、AES-192 および AES-256 も非常に長期間にわたり安全であると考えられます。これは当然ながら、AES に古典的および量子 cryptanalysis との観点から新たな暗号学的弱点が発見されていないことを前提としています。 このような理解に基づき、現在のアプリケーションでは 128、192、または 256 ビットの鍵長を使用された AES を継続的に使用できます。NIST は対称鍵アルゴリズムおよびハッシュ関数の移行に関するガイダンスを発行し、量子コンピュータからの脅威に対抗する必要があると予測される時点を待っています。その間には、すでに NIST が発行した推奨事項およびガイドラインに従うべきです。特に、128 ビットの古典的セキュリティ未満のものは使用すべきではありません。
NIST はこれについて曖昧な態度をとっているわけではなく：128 ビットの鍵は問題ありません。
BSI も同意している
他の標準化機関はどうでしょうか？ドイツ連邦情報セキュリティ庁（BSI）は最近、「ポストクオンタム暗号領域における更新」を含まない BSITR-02102-1「Crypto Mechanisms: Recommendations and Key Lengths」という文書を公開しました。そこではグローバー法に言及していますが、NIST よりも結論的ではありませんが、同じ結論に達しています：
新しい暗号システムでの使用におすすめされる次のようなブロック暗号はあります： AES-128、AES-192、AES-256
同じ出版物において、BSI は NIST よりもはるかに早期に量子脆弱な素数を廃止する移行を推奨しています（注：AES-128 は含まれていません）：
古典的な鍵同意メカニズムのみの使用は、2031 年までのみ推奨されます。参照：セクション 2.3。
Samuel Jaques も同意している
Samuel Jaques は、ウォータロー大学の組み合わせ・最適化部で暗号学および量子計算を専門とする准教授です。おそらく彼の「Quantum Computing のlandscape」を知っています。私は上記の数値をすべて計算した後で見つけた 2024 年のスライドデッキですが、実質的に同じ作業を 2 年後にドメイン知識が少なくて行っていたことに対して少し恥ずかしく思いました。しかし、結論の一致は非常に驚くべきものです。推測と最適化の重要性が十分に小さく、許容範囲が十分広いため、私たちが反復して同等の結論に達しているのです。
彼は単一の論理量子ビットを構築する困難さについて言及していますが、私はこれを無視しています（なぜなら、私たちは拡張可能な量子誤り訂正が行われる世界を仮定しているためです）。もしそうでなければ、非対称暗号も心配する必要がありませんでした。また、彼はデコヒーレンスについても触れ、私が保守的に仮定しているような、10 年もの間停電なしに動作する量子コンピュータが存在することを非常に不確かであることに言及しています（私がヒントした点）。
彼は優れたポイントとして、Grover オラクル回路に対する正しい最適化指標は depth² × width であるとしています。なぜなら深度はコストと最大深さに達することに両方に関与するためです。これは Liao と Luo (2025) の回路が最適ではないことを示唆しており、代わりに Jang ら (2022) からのものである使用しています。それでも結果は非常に似ています。
最後に、彼は表面符号アーキテクチャにおいて各論理 T ゲートには $2^{16}$ の物理的操作が必要であり、実用的なリソース見積もりに達する前に式に含まれていない項があると指摘しています。
なぜわざわざ安全のためにswitchしないのか、知っていますか？
ポストクオンタム移行全体は推測リスクを軽減することについてですが、なぜ対称鍵も「安全」にするのはダメなのか？それはリソースが有限であり、チェーンにはコストがかかるため、そして協調性が重要だからです。この分野は非対称暗号への具体的な危険性について専門家から告げられているため、ポストクオンタム暗号の展開を急いでいます。逆に、同じ専門家が対称暗号には危険性がないと言っています。
対称暗号と非対称暗号は十分に分離しているため、通常は最小限の追加コストで両方を同時に切り替えることはできません。例えば、ネゴシエートされる TLS 鍵交換および PKI 署名アルゴリズムを変更することが、サポートされるサイファースイートを 변경することとはほとんど関係ありません。必要な変更と不必要な変更を混同することは、無駄なチェーンを引き起こし、緊急のアップデートからリソースを奪ってしまいます。対称暗号（サブ）システムを触らなくて済むことに幸運です。その祝福を利用して、実際に必要な作業に焦点を当てましょう。それは Plenty です。
複雑性と協調性という観点からも：TLS や異なるライブラリおよびプログラミング言語で実装されたものなどのオープンエコシステムを移行させるには、ターゲットの合意が必要です。技術的に正確なことは合意するのに容易です：私たちは自発的に収斂するか、技術的論理で互いに説得できます。不必要で定義されていない目標を目指す代わりに、相互運用性の問題を引き起こし、複数の異なる独自の見解をサポートする必要があります。これにより複雑性が生じます。
CNSA 2.0 はどうでしょうか？
確かに、256 ビット対称鍵を要求するコンプライアンス制度の一つがあります：CNSA 2.0 ですが、これは量子コンピューティングへの適応ではありません。CNSA 2.0 は、その前身である Suite B が Top Secret 分類のために常にしていたように、すべてのものに 256 ビットの「セキュリティレベル」を要求します。実際には ML-KEM-1024 および ML-DSA-87 も強制しています。私の知る限り、その意図は「セキュリティレベル」によって導入された非常に同じ断片化を避けるために、すべての設定に対して 1 つの過剰な素数を採用することにあります。
256 ビットセキュリティレベルで AES-256 を受入れること（存在しない AES-512 の代わりに）により、CNSA 2.0 はグローバー法が AES のセキュリティを半減させないことを認めました。おそらく Go は CNSA 2.0 プロフィールを実装するでしょう。「256 ビット everything」は定義された目標であり、動きやすい可能性が低いからです。私が好む「安全かつ合理的な」目標ではありませんが、これは異なる人々に対して異なる意味を持つことのできる「安全かつ合理的だが一部の素数のセキュリティについて部分的に誤解している」状態とは異なり、コミットできるものです。
256 ビット鍵は常に無用なのか？
一般的に私は、256 ビットの「セキュリティレベル」がブランケットのようなものと数秘術の間のどこかだと考えています。なぜなら、同僚が最近言ったように「$2^{128}$ を数えることは信じていないからです」からです。しかし、これは 256 ビット鍵（またはブロックサイズ）が常に 128 ビットセキュリティレベル達成のために無用であることを意味するわけではありません。衝突が懸念でありバースデー境界が作用する場合、ビットあたりのセキュリティは実際に半減するため、例えば 128 ビットの衝突セキュリティを得るには 256 ビットのハッシュ出力が必要となります。（SHA-128 が存在しないのはそのためです。）同様に、多目標攻撃（敵の優位性は多くのメッセージ/鍵の中のいずれかを破る確率として測定される）は、ノンシー如何使用に応じて追加のマージンを必要とする場合があります。
しかし、これは暗号エンジニアがプロトコルを設計する際に深く関与する懸念であり、政策決定またはシステム管理の選択には含まれません。適切に設計されたプロトコルはこれらすべてを考慮しています。例えば、TLS で AES-128 を使用しても、そのノンシーデザインのおかげで大きな多目標マージンを持って 128 ビットセキュリティレベルを満たします。
暗号エンジニアとして、私はすべての暗号が 256 ビット鍵を持つことを願いますが、それは私の生活をより容易にするためです：
- 私たちは既に 128 ビット鍵を適切に処理する作業を行い、今すぐ切り替えるのは無駄な努力であり、実際には緊急のポストクオンタム移行に向けて投入できるはずのリソースを浪費することになります；
- AES-256 は不幸にも AES-128 よりも多くのラウンドを実行するように定義されており、不必要に遅くなります。
より希望的観測対現実的な PQ 移行については、Bluesky で @filippo.abyssdomain.expert または Mastodon で @filippo@abyssdomain.expect をフォローしてください。
絵面
先月、UBC で開催された AtmosphereConf 2026 に参加しました。キャンパスは非常に美しく、森を通る素晴らしい道があり、そこに海が見えて夕日を水面上に眺めることができます。
私の作業は可能にする Geomys（プロフェッショナルな Go メインテナーの組織）によって支えられています。Geomys は Ava Labs、Teleport、Tailscale、Sentry によって資金提供されており、私たちのオープンソースメンテナンス作業の持続可能性と信頼性を保証し、他の Geomys メインテナと私の専門知識に直接アクセスできる権利を得ます。（Geomys のアナウンスを参照してください。）いくつかの言葉があります！
- Teleport — 過去 5 ヶ年にわたり、攻撃と侵害は従来のマルウェアやセキュリティ侵害から、ソーシャルエンジニアリング、credential theft、またはフィッシングによる有効なユーザーアカウントや認証情報の特定および侵害にシフトしてきています。Teleport Identity は、アクセス監視を通じて弱いアクセスパターンを排除し、アクセスリクエストによって攻撃対象領域を最小限にし、必須のアクセスレビューを通じて未使用の権限を廃止するように設計されています。
- Ava Labs — 私たちは Ava Labs で、最も広く使用されている Avalanche Network 用のクライアントである AvalancheGo のメインテナであり、ブロックチェーン技術の広範な採用のためにオープンソース暗号プロトコルの持続可能なメンテナンスと開発が不可欠だと信じています。Filippo および彼のチームに対する私たちの継続的なスポンサードシップを通じて、この必要かつ重要な作業を支えることを誇りに思っています。