量子コンピューターを使っても解読が難しい暗号とは？
量子コンピューター技術の進歩によって、RSAやECDSA、EdDSAなどの非対称暗号が量子アルゴリズムに対して脆弱(ぜいじゃく)になってしまうため、早急に代替する必要が生じているといわれています。しかし、プログラミング言語Goの暗号標準ライブラリの保守担当である暗号技術エンジニアのフィリポ・バルソーダ氏が「量子コンピューター技術が進化しても、AES-128など暗号化と復号で同じ鍵を使う対称鍵暗号には影響を与えない」という見解を示しています。
https://words.filippo.io/128-bits/
量子コンピューター向けのアルゴリズムの1つである「Groverのアルゴリズム」は、正解を総当たりで探すタイプの問題を、量子コンピューターで古典コンピューターより少ない試行回数内に解けるようにする探索アルゴリズムです。数学的には、入力空間の大きさがNのとき、古典的な総当たりではおおむねN回の試行が必要なのに対し、Groverではおおむねπ/4×√N回の関数呼び出しで正解を見つけられるとのこと。そのため、AES-128のような対称暗号を脅かすアルゴリズムだといわれています。
しかし、バルソーダ氏は「量子コンピューターとGroverのアルゴリズムによってAES-128が脅かされていると言われがちですが、その理解は正確ではありません」と主張しています。Groverのアルゴリズムは確かに高速化が可能ですが、現実の攻撃で重要になる並列化のしやすさまで含めると、古典コンピューターにおける総当たりのように素直には効かないとのこと。
Groverのアルゴリズムでは探索対象の関数、つまり「この候補が正解か」を判定する処理そのものを量子回路の中に実装する必要があり、その呼び出しを基本的に直列で積み重ねなければなりません。しかも、Groverのアルゴリズムをうまく並列化する方法はないそうで、結局は探索空間を分割するしかありません。ところが探索空間を分けると、古典計算では1台あたりの仕事量が分割数に応じてそのまま減るのに対し、Groverでは「√N」となっているので、減り方が鈍くなります。
例えば、64ビット鍵の総当たりを216台の古典コンピューターに分散すると、各コンピューターの負担は216分の1になります。一方で、128ビット鍵へのGrover攻撃を216台の量子コンピューターに分散しても、各インスタンスの負担は28分の1にしかなりません。その結果、Groverは理論上は速くても、現実の大規模攻撃で重要な「大量のコンピューターに投げて一気に終わらせる」という運用との相性がよくないというわけです。
by Pierre Metivier
つまり、Groverのアルゴリズムは「量子コンピューターが総当たり探索を理論上速くできる」ことを示す重要なアルゴリズムですが、それは必ずしも「AES-128は半分の強度になる」という意味ではありません。理論式だけを見ると強力に見えるものの、実際には量子回路化や直列性、並列化の難しさ、長時間動作の必要性といった制約が大きくなります。
量子ゲート1回の計算に1マイクロ秒しかかからない高速な量子コンピューターがあり、しかもそれを10年間ほぼ止まらず動かせると仮定します。この時、1台の量子コンピューターが積み重ねられる処理の長さ、つまり直列計算の最大長は約248ゲートになります。
仮にAES-128をGroverのアルゴリズムが使える形の量子回路として組み込む場合、Groverのアルゴリズムでは「正しい答えかどうかを判定する関数f」もその一部として組み込む必要があります。しかし、2025年に発表されたAES-128の最適化を適用しても、その判定には「724論理量子ビットを232個並列にして約10年動かす必要がある」とのこと。つまり、量子回路としてはかなり大がかりなものとなってしまいます。
要するに、Groverのアルゴリズムは探索回数を減らすことができても、1回の探索で行う判定処理が重いので、理論上はAES-128の答えを264回の試行で済んでも、実際はその264回の試行それぞれに判定するための回路がぶら下がります。そのため、Groverが理論上速くても、AES-128を実際に破る攻撃全体は非常に計算コストが高くなってしまうというわけです。
by Steve Jurvetson
量子コンピューター上で素因数分解問題を解くための「Shorのアルゴリズム」は、RSAや楕円曲線暗号のような公開鍵暗号に効果があるといわれています。256ビット楕円曲線暗号をShorのアルゴリズムで解く場合、実行に必要な規模は約226ゲートだといわれています。1ゲートでの計算が10マイクロ秒程度であれば、これは数分で終わる計算になります。
バルソーダ氏は、AES-128をGroverのアルゴリズムで解く場合にかかるコストは、256ビット楕円曲線暗号をShorのアルゴリズムで解く場合の約278.5倍、すなわちおよそ43×1020倍も大きいと論じています。「量子コンピューターの登場で暗号が危ない」と一口に言っても、Shorのアルゴリズムによる公開鍵暗号解析と違って、Groverのアルゴリズムによる対称鍵暗号解析はかなり現実的ではありません。
アメリカの国立標準技術研究所(NIST)はAES-128を引き続き安全とみなしており、AES-128、AES-192、AES-256をそのまま使ってよいという立場を明示しています。これはドイツの情報セキュリティ庁(BSI)も同じで、新しいシステム向けにAES-128、AES-192、AES-256を推奨しています。
暗号研究者のサミュエル・ジェイクス氏は、2024年にバルソーダ氏とほぼ同じ主張を発表しており、「Groverのアルゴリズムで高速化されたからといって、AESの鍵長を倍にすべきというのは誤りだ」と主張。Groverのアルゴリズムを並列で実行するような攻撃はコストが高すぎるため、AES-128が破られることは生涯中どころか永遠に起きないかもしれないと述べています。
その上で、バルソーダ氏は「とりあえず念のために対称鍵暗号も全部256ビットにしておけばいいのではないか」という考えには否定的な姿勢をみせています。本当に急ぐべきなのはShorのアルゴリズムによって脆弱になってしまう公開鍵暗号の置き換えであり、不要な変更まで行うと作業や調整が増えてしまい、相互運用性に支障が出るためです。バルソーダ氏は、「TLSの鍵共有や署名方式を変えること」と「対称暗号の鍵長を変えること」は別作業なので、必要な部分に資源を集中した方がよいという考えを示しました。
