ハクソク

世界を動かす技術を、日本語で。

量子コンピュータは128ビット対称鍵に対する脅威ではない

16時間前原文(words.filippo.io)

概要

  • 量子コンピュータによる脅威は主に公開鍵暗号に影響
  • 対称鍵暗号（AES, SHA-2, SHA-3）は量子攻撃に強い
  • AES-128やSHA-256は鍵長変更不要との専門家合意
  • Groverアルゴリズムの誤解が鍵長倍増論を生む
  • NISTやBSIもAES-128の安全性を公式に認めている

量子時代における対称鍵暗号の安全性

  • 量子コンピュータの進展により、RSAやECDSA、EdDSAなどの公開鍵暗号はShorアルゴリズムで容易に破られるリスク
  • AES、SHA-2、SHA-3などの対称鍵暗号は量子攻撃の影響が小さい
  • 「量子時代には鍵長を倍にしなければならない」という通説は誤解であり、実際にはAES-128やSHA-256のままで安全
  • 誤解の根拠はGroverアルゴリズムの適用範囲の誤認によるもの

Groverアルゴリズムの現実的な影響

  • Groverアルゴリズムは探索空間Nに対し、√N回の関数呼び出しで解を見つけられる
  • 例：AES-128の鍵探索には2^64回の試行が必要となるが、これは現実的な時間内で実行不可能
  • 攻撃を並列化しようとすると、Groverの二乗的高速化は大幅に減衰
    • 並列化による効率低下
    • 通常の総当たり攻撃のような「恥ずかしいほど並列」にはならない
  • AES-128のGrover攻撃には724論理量子ビット×140兆回路×10年稼働が必要という非現実的な計算資源

Shorアルゴリズムとの比較

  • Shorアルゴリズムは256ビット楕円曲線暗号を数分で破るとされる
  • AES-128をGroverで破るコストはShorで256ビット楕円曲線を破るコストの4.3×10^23倍
  • 量子攻撃における公開鍵暗号と対称鍵暗号の安全性格差が明確

標準化機関の見解

  • NISTはAES-128をポスト量子暗号の安全基準とし、AES-128の安全性を公式に認めている
    • MAXDEPTH（連続計算深さ）の概念でGrover攻撃の現実的困難さを説明
    • NIST IR 8547 ipdでもAES-128以上の鍵長は2035年以降も許可
    • 「AESの鍵長を倍にすべきか？」というFAQに対し、「AES-128は今後も数十年安全」と明記
  • BSI（ドイツ連邦情報セキュリティ局）もAES-128/192/256の利用を推奨し、量子脆弱な公開鍵暗号の早期移行を推奨

まとめと実務的指針

  • 対称鍵暗号の鍵長を倍にする必要はない
    • AES-128、SHA-256は量子コンピュータ時代も安全
  • ポスト量子暗号への移行は公開鍵暗号が優先課題
  • AES-128未満の鍵長（112ビット未満）は非推奨
  • NISTやBSIのガイドラインに従い、既存の対称鍵長で運用継続が推奨

参考文献・関連資料

  • NIST: ML-KEM/ML-DSA仕様書, NIST IR 8547 ipd, Post-Quantum Cryptography FAQs
  • BSI: TR-02102-1 Cryptographic Mechanisms: Recommendations and Key Lengths
  • Liao and Luo (2025), Grassl et al. (2015), Jaques et al. (2019), Babbush et al. (2026) などの量子回路最適化論文

Hackerたちの意見

これが本当なら、Wi-Fiアライアンスは生成する電子廃棄物についてたくさんの説明が必要だと思う。WPA3は対称AESからECDHに移行したけど、これは量子コンピュータに対して脆弱なんだよね。IOTインバータの廃棄物が大量に出そう。
└
WPA3はPBKDFからECDHに移行したよ。AES CCMPとGCMPはWPA3の基盤となるブロック暗号で、中国向けのいくつかの拡張もある。
└
WPA3は2018年に発表されたんだよね。次の10年間の暗号研究を予測できなかったからといって、彼らを責めるのは合理的じゃないと思う。…でも、仮に予測できていたとして、実際に何ができたんだろう？ML-KEMは2024年に標準化されたばかりだし。WPA3にECDHが追加されたのは、既存の非常に現実的な攻撃に対処するためだったんだ。> WPAとWPA2は前方秘匿性を提供しないから、一度悪意のある人が事前共有鍵を発見したら、そのPSKを使って将来や過去に送信された全てのパケットを復号できる可能性があるんだ。これらは攻撃者によって受動的に静かに収集されることもある。これにより、公共の場で無料で提供されるWPA保護されたアクセスポイントがあれば、攻撃者は他人のパケットを静かにキャプチャして復号することもできる。0: https://en.wikipedia.org/wiki/Wi-Fi_Protected_Access#WPA3 1: https://en.wikipedia.org/wiki/ML-KEM 2: https://en.wikipedia.org/wiki/Wi-Fi_Protected_Access#Lack_of...
└
参考までに言うと、暗号エンジニアたちはドラゴンフライPAKEにあまり満足していなかったし、PQCは2012年の時点でも正当な懸念だったよ。
└
昨日、WEPしかWiFiオプションがないIoTデバイスを使ったんだけど、言うまでもなく、有線接続を使ったよ。「IoT」の「s」はセキュアを意味するって言われてるけど、私の経験ではそれは本当だね。ほとんど何も捨てられないよ、だって安全じゃないから。
量子コンピュータの脅威は、場合によっては積極的な鍵のローテーションで実質的に軽減できると思う。今、銀行のベンダーと一緒にOAuthの機械間統合をプロトタイプしていて、ECDSAキーが5分ごとにローテーションされるようにしてるんだ。10分後にはキーは削除される予定。これを30秒や60秒に短縮できない理由はないと思う。相手先は頻繁に私たちのJWKSエンドポイントをスキャンしているから、実際には量子コンピュータを持つ攻撃者は、この特定のワイヤー契約を怖い方法で破るためには非常に速く動く必要がある。
└
あなたは明らかにこれらの鍵を証明書に使ってないね。証明書は毎回ルートCAや中間CAによって署名される必要があるから。
└
これは対称鍵暗号には役立たないよ、これが話題になってることだからね。君が回してる鍵は非対称鍵で、実際の暗号化のための対称鍵を交換するためだけに使われるんだ。良い設定では、対称鍵はセッションごとに変わるしね。もし攻撃者が対称暗号を合理的な時間内に破れたら、出力をキャッチして後で解読できちゃう。あと、鍵のローテーションはどうやってるの？ローテーションサービスと認証する方法が必要だし、その鍵を壊すことを防ぐためにはどうするの？自分で新しい証明書を取得するために、信頼されたルート権限を壊すこともできるよね？
└
鍵を1ヶ月で破るのから1秒で破るのに移行するのは、今の状況から1ヶ月で破れるようになる努力に比べると簡単に思える。量子の未来がどうなるかはわからないけど、もし量子が実現したら、君の計画にはあまり期待できないな。
└
やりすぎな気がする。量子は早すぎる心配だけど、そんなにパラノイアがあるなら、変なものを作るよりもML-KEMみたいなPQCを使った方がいいんじゃない？
└
非対称鍵にはあまり役に立たないだろうし、対称鍵には必要ないね。https://arxiv.org/abs/2603.28846によると、攻撃の実行時間は数分だって。今日からスケーラブルな量子誤り訂正までの間に、オーダー・オブ・マグニチュードのブレイクスルーがたくさんあるから、実現可能な攻撃のオーダーを正確に予測するのは無意味だよ。起こらないと思うなら、長期のECDSA鍵を使い続ければいいし、起こると思うなら、回転期間を超える可能性が高いよ。
└
不透明なトークンを使えば、そもそも問題を回避できたんじゃない？
すごく良い分析だね。もし私がグローバーのアルゴリズムを正しく理解しているなら、要するに実現可能にするには計算リソースが足りないか、時間がかかりすぎるってこと？でも、計算リソースが十分にあれば、時間はほぼ無関係になるってこと？例えば、今のデータセンターが手のひらに収まるくらい小さくなったら（初期のコンピュータは部屋を占拠していたのに、今のスマホと比べて）。だから、計算が（何らかの形で）非常に最適化されるか、マイクロプロセッサのような新しいものを使うことができれば、128ビットの対称鍵に対する量子の脅威になるのかな？
└
私は専門家じゃないけど、十分に速い従来のコンピュータ（または並列処理ができるコンピュータ）が128ビットの鍵をブルートフォースで解読できるのはその通りだけど、必要な改善の量は過去40年間に経験したものをはるかに上回るだろうし、コンピュータの動作に根本的な変化がない限り、物理的に不可能だと思う。過去40年間で、計算能力は1秒あたりの命令数で5〜10桁の増加を見てきた。合理的な時間枠でブルートフォースで達成するには、さらに20〜30桁の増加が必要なんだ。それは今のコンピュータの作り方では実現できないよ。
└
量子攻撃の計算されたDWコストは2^104で、これは「ブルートフォース攻撃よりもずっと現実的」っていうのは、128ビットのブルートフォース攻撃が256ビットのブルートフォース攻撃より現実的なことと同じ意味だよね。どちらも実用的とは言えないけど、古典的なコンピュータと同じくらい速く（そして小さく！長期的にコヒーレント！）なる量子コンピュータを想像しても。
一方では、量子コンピュータが因数分解や離散対数を解くって聞くけど、もう一方では、因数分解できる最大の数は15で、21すら実現不可能かもしれないって言われてる。何が起こってるの？
└
この1ヶ月で、暗号技術者の間で雰囲気が急激に変わったんだ。CRQCのデモが予想よりも早く、もしかしたら5年以内に見られるかもしれないって噂が広まってるから。そこから先は満足のいく答えは得られないよ。「15の因数分解」ってことはみんな理解してるし、雰囲気が変わった人たちはそれを織り込んでるから。
└
コヒーレンシー 有用な結果を得るためには、量子コンピュータはすべてのキュービットが互いに絡み合った状態を保たなきゃいけないんだ。グループ全体が結果に崩壊するまでね。現行の技術では、適切なサイズのキュービットのグループがコヒーレントに絡み合うのは非常に難しいから、古典的なコンピュータでも比較的簡単に解ける問題しか解けないんだ。もし今日、たくさんのビットを絡ませ続ける方法が見つかったら、量子コンピューティングは瞬時に量子安全でない暗号を破れるようになる。これはゆっくり進んでいるわけじゃなくて、いつ、あるいはもしそれが起こるかも予測できない突破口なんだよ。
└
この記事「因数分解はQデーを追跡するのに良いベンチマークではない」は、Cloudflareの主要なポスト量子研究者の一人が今月投稿したもので、因数分解の問題に特に触れてるよ。https://bas.westerbaan.name/notes/2026/04/02/factoring.html それ自体はあまり言ってないけど、関連する非常に良いリンクが4つあるんだ。そのうちの1つには、因数-21回路の最小既知の写真が載っていて、因数-15回路のものよりもはるかに大きく、もっと大きな数に匹敵するんだ。もう1つは、スコット・アーロンソンの記事で、小さな数の因数分解を「小さな核爆発を求めること」と例えてるんだ。1940年に小さな核爆発を作れないからって、大きな核爆発から遠いわけじゃないってことだね。
└
俺の理解では、15の因数分解はただのスタントで、一般的に使うべき実際の誤り訂正アルゴリズムを使ってなかったみたい。例えるなら、北アメリカを車で横断しようとしてるけど、エンジンが壊れてる状態を想像してみて。近くに整備士がいるから、ニュートラルにして押していく。もし誰かが「整備士のところまで押すのに30分かかったから、北アメリカを横断するのには残りの人生がかかる」って言ったら、それは間違った解釈だよ。整備士がエンジンを直せば、すぐに速く進めるようになるはずだし、逆に壊れたままなら直せないかもしれない。どちらにしても、どれだけ押せるかは整備士が直す速さや、直った後の速さには関係ないよね。量子コンピュータがどうなるかは分からないけど、15の因数分解のタイムラインはあまり関係ない。暗号の文脈では、アルゴリズムを変えるのが難しいことを考慮して、暗号学者は未来を見越して計画を立てる必要がある。彼らは「量子コンピュータが今後15年以内に実際の暗号を破る確率が1%以上か？」みたいな質問に興味を持ってる。最近はその可能性が現実的に感じられるようになってきたね。必ずしも起こるわけじゃないけど、その可能性に備えるのが賢明だと思うし、今がその準備を始める時期だよ。
└
物理的なキュービットを十分なノイズ性能で作れれば、何らかのカスケード効果があるみたいだね。これがよく聞く「閾値」ってやつ。閾値を超えれば、エラー訂正を使って無限に拡張できる可能性があるんだ。ただし、他に問題が起きないことが前提だけど。おそらく、互いに絡み合った何千ものキュービットを「エラー訂正」するのが、その問題の一つになるんじゃないかな。
フィリッポ・ヴァルソルダの文章は本当に分かりやすいなと思う。俺みたいな年寄りでも、彼の数学や例はすごく理解しやすかった。こういう技術的な文章の明快さには感謝だね。
グローバーのアルゴリズムが限界なのか、何か理由があるの？俺は賛成だけど、記事でもコストや優先順位、仮定の問題だって言ってるよね。いいね、今はxaes-256-gcmを使ってるけど、量子がアルゴリズム分析に新しい応用を持つか、他の弱点を突ける可能性があるか、ちょっと気になるな。
└
唯一の注意点は、AESが必ずしもブラックボックスではないってこと。隠れた構造があるかもしれないけど、もしそうだとしても、量子スピードアップに適しているとは限らないよ。グローバーのスピードアップに関しては、すでに最適だし、非構造的検索にはO(√N)のクエリが必要ってのが証明された下限だから。
└
うん、そうとも言えるし、そうじゃないとも言える。グローバーのアルゴリズムは証明された最適解だよ[0]。どんな量子アルゴリズムも、合理的なオラクルへのクエリでnビットの鍵をグローバーのアルゴリズムより速く見つけることはできないし、グローバーのアルゴリズムは深刻な問題になるほど遅くはない。だけど、対称暗号はブラックボックスじゃない。ほとんどがフェイステルネットワークの変種で作られていて、これは混乱した関数を可逆関数に変えるための非常に良い構造なんだ。大学院のとき、フェイステルネットワークに対する量子攻撃の実際のセキュリティ証明を生成するか、面白い量子攻撃を考えるプロジェクトを考えたことがあったけど、実際には時間をかけなかったんだ。そして、3ラウンドのフェイステルネットワークに対する面白い量子攻撃があることも確かだ[1]。これは興味深いよね。必要なセキュリティの種類によっては、フェイステルネットワークの3ラウンドか4ラウンドで古典的な攻撃に対して十分なんだ[2]。今、AESのような暗号は3ラウンド以上あるから、たぶん大丈夫だと思うけど、そうじゃないかもしれない。俺の直感では、対称暗号を破ることができる量子アルゴリズムは、古典的なクエリアクセスがあっても（n1）、ラウンド関数への量子クエリアクセスがあっても（n2）存在しないと思うけど、そういう証明は知らないな。俺の直感を完全に信じるべきじゃないかも！(間違ってても、全暗号へのクエリアクセスに対して十分なラウンド数があるかもしれない。)[0] 古典的な結果は https://arxiv.org/abs/quant-ph/9701001 で、もっと新しい、正確な結果もあるよ、例えば https://arxiv.org/abs/0810.3647 [1] https://ieeexplore.ieee.org/document/5513654 [2] https://ja.wikipedia.org/wiki/フェイステル暗号 [3] もし誰かが量子コンピュータやネットワーク、ストレージを作って、互いに信頼しない二者が実際に通信したり、面白い[5]量子ビットを交換できるようになったら、すごくクールだよね。これについては面白い論文も書いたことがある。もしその技術が手に入ったら、古典的な対称暗号に対する選択量子暗号文攻撃を考えるのも意味があるかもしれない。でも、それはまだまだ先の話だし、どんな場合でも、攻撃者が暗号システムに対して量子クエリ攻撃を行えるのは、被害者がそれを許可した場合だけだよ。[4] それ以外はすべて古典的なクエリになる。[4] あるいは、非常に複雑な設定で、難読化されたブラックボックスがある場合もね。これはzk-snarksや似たような構造に関係があるかもしれない。[5] 商業デバイスで実装されている量子鍵配布の光学量子ビットは、面白いとは思わないな。そのデバイスのベンダーにはごめんね。
└
面白い事実：グローバーのアルゴリズムは発明される前に最適であることが証明された珍しい例だよ。
回転は一つの脅威モデルを守るけど、両方は守れないよ。5分前に壊れた署名キーは一つの偽造窓だし、誰かのアーカイブに保存された暗号文はセッションキーを削除したタイミングなんて気にしない。署名者を回転させるのはいいけど、10年後も安全にしたいならペイロードにはxaes-256-gcmを使った方がいいよ。
量子コンピュータは主にお人好しな投資家にとっての脅威だね。
└
そうだけど…もし何かあったら？
面白いアプローチだね。実際の負荷の下でどうスケールするのか興味あるな。
[遅延]