STAGE6 それでも2⁶⁴回 ― オラクルは比較しない

STAGE 6それでも2⁶⁴回

誠実な結論

🎯 ミッション

最後のミッションだ。約2⁶⁴回という数の重さを自分で見積もり、「なぜAESの鍵は256ビットに伸ばされたのか」を説明しよう。そのうえで、最初の疑問――オラクルは中で1個ずつ比較しているのでは？――に、自分の言葉で完全に答えられれば、クエスト達成。

未達成

ねこ博士

仕上げに、前回の「約2⁶⁴回」の重さを量ろう。2⁶⁴を数字で書くと約1845京――1.8×10¹⁹だ。
ここで大事な事実をひとつ。グローバーの反復は、直列でしか実行できない。1回目の折り返しが終わった状態に2回目のオラクルを掛け、その結果に3回目を掛ける……という数珠つなぎだから、途中を飛ばすことも、まとめて一気にやることもできない。古典の総当たりなら計算機を1万台並べて手分けできるが、この反復は行列に並ぶしかないんだ。

うさ美

では見積もってみます。オラクル1回はAES計算2回ぶんを含む数万ゲートでした。仮に誤り訂正まで含めて1回を1マイクロ秒（100万分の1秒）でこなせる、かなり楽観的な機械があるとします。
2⁶⁴回 × 1マイクロ秒＝ 1.8×10¹³秒。1年は約3200万秒だから……約58万年。
人類の文明より長いです。1000倍速い1ナノ秒の機械でも585年かかります。

ねこ博士

その見積もりで方向は合っている。実際の研究でも、誤り訂正のコストまで入れてAES-128へのグローバー攻撃を試算すると、必要な時間や量子ビット数は現実離れした規模になる、という結果が繰り返し出ている。つまり「量子コンピュータでAESが一瞬で破られる」は、オラクルの中身を数えた瞬間に崩れる話なんだ。

うさ美

待ってください、いまの比較は片側だけです。古典の総当たりだって、計算機を並べて手分けできます。グローバー機と同じ予算で古典のAES回路を大量に買って並べたら――同じお金を掛けた勝負では、どちらが速いんですか？

ねこ博士

公平な問いだ。そして答えは意外かもしれない。現在の見積もりでは、同じ予算・現実的な期限なら、古典の並列探索のほうが速い可能性が高い。理由は2つある。
ひとつ、並列化の効率。古典の総当たりは分担がきれいに効く――10台なら10倍、台数にそのまま比例する。ところがグローバーの反復は、M台で手分けしても1台あたり √(N÷M)回が必要で、得は√M倍どまり。構造的に手分けが苦手なんだ。
ふたつ、誤り訂正の代金。概算では、誤り訂正済みの論理ゲート1回のコストは古典ゲートの10⁹〜10¹²倍になり得る。「1年で解く」と期限を切った専門の試算では、量子側はプロセッサ約10²¹台（1台あたり数千論理量子ビットの巨大装置）が要り、同じ期限に必要な古典の専用AES回路の台数と大差ない。1台あたりの値段は量子側が桁違いに高いから、同予算の勝負では負ける。
実際、標準化を仕切るアメリカのNISTも、グローバーはAES攻撃で「ほとんど、またはまったく優位を持たない可能性が高い」と評している。
――念のため言えば、どちらの陣営も宇宙的な規模で、実際にはどちらも成功しない。それでも暗号の専門家は2次加速を軽く見なかった。将来ゲートが劇的に安く速くなれば勘定は変わりうるし、「実質の安全性が64ビット相当に目減りする」こと自体を問題にして、対策を打った。

うさ美

対策は……グローバーが「√Nに減らす」ことしかできないなら、Nを増やせばいいんですね。鍵を256ビットにすれば、候補は2²⁵⁶個。グローバーを使っても√(2²⁵⁶)＝2¹²⁸回で、今度こそ絶望的な数に戻ります。

ねこ博士

そう、それがAES-256だ。共通鍵暗号の量子対策は「鍵長を2倍に」でほぼ片が付く。慎重を要する場面ではAES-256を選ぶ、というのが現在の標準的な考え方だよ。
――なお、暗号全体で見ると、本当に危ないのは共通鍵ではなく公開鍵暗号のほうだ。前作のショアのアルゴリズムは因数分解を指数的に速くするから、こちらは鍵長を伸ばしてもしのげない。だから2024年に、ショアが効かない新方式（耐量子計算機暗号）が標準化された。グローバー対策は鍵長2倍、ショア対策は方式の交換――脅威の大きさに応じて、処方箋も違うわけだ。

うさ美

では、最初の疑問に自分で答え直します。「オラクルは、中で2¹²⁸個の候補を1個ずつ正解と比較しているのでは？」――していません。理由を全部言えます。
第一に、一致判定に比較は要らない。正解Cの情報はXゲートの配置として回路の形に焼き付いていて、候補リストも比較用メモも存在しない（STAGE1・2）。
第二に、重ね合わせの全成分に効くのは、回路の仕掛けではなく法則の性質。線形性が「1個ずつ通したのと同じ結果」を保証するだけで、回路は1回しか動かない（STAGE3）。

うさ美

第三に、「瞬時」でもない。多重制御Zはトフォリの鎖と逆計算で建てる数百ゲートの建築物で、オラクル1回にはAESの計算と逆計算まで含まれて数万ゲート（STAGE4・5）。
第四に、目印が付いただけでは読み出せない。位相は測定に現れないから、折り返しで長さに変える反復が約2⁶⁴回、しかも直列に必要（前作STAGE6と今日）。
――「同時に全部比較して一瞬で破る」という絵は、四重に間違っているんですね。

ねこ博士

完全な答えだ。これでクエスト達成だよ。
オラクルという言葉は「神託」――中身の見えない魔法の箱を思わせる。でも開けてみれば、中にいたのは錠前職人の地道な仕事だった。NOTの位置に正解を刻み、ANDを鎖に編み、メモを消し、目印を付けて返す。魔法がないと知ることは、量子コンピュータをつまらなくするどころか、どこが本当にすごいのか――装置ではなく法則が仕分けをしてくれること――をはっきりさせてくれる。
それが分かったいま、きみはもう「同時に計算するから速い」とは言わないはずだ。

オラクル1回（AES計算＋照合＋逆計算）にかかる時間を仮定して、攻撃全体の所要時間を見積もる表。反復は直列なので、機械を増やしても行列は縮まない。1マイクロ秒＝100万分の1秒という楽観的な仮定でも、AES-128に58万年。鍵長を256ビットに伸ばせば、どの仮定でも宇宙の年齢を桁違いに超える。√Nの加速は本物、しかし魔法ではない。

【クエスト全体のまとめ ― オラクルは比較しない】 ①一致判定は固定回路：正解Cの情報はNOT／Xの配置に焼き付く。比較リストなし、部品数はビット数に比例（STAGE1・2） ②目印は位相に：Xサンド＋「全部1なら反転」で |C⟩→−|C⟩。長さは不変、いま測っても差は見えない（STAGE2） ③仕分けは線形性の仕事：回路は1回動くだけ。「足してから通す＝1個ずつ通してから足す」を法則が保証（STAGE3） ④巨大ゲートは建築物：トフォリの鎖でANDを積み、Zを1発、逆計算でメモ（手がかり）を消す（STAGE4） ⑤レジスタは1本：Σ|k⟩|AESₖ(P)⟩ は数百量子ビットの装置の1状態。「オラクル1回」＝AES計算＋照合＋位相反転＋逆計算（STAGE5） ⑥それでも2⁶⁴回・直列：AES-128の攻撃は現実離れした時間。手分けの得は√M倍どまりで、誤り訂正の代金（論理ゲート1回＝古典の10⁹〜10¹²倍）も重く、同予算なら古典並列のほうが速い可能性が高い（NISTも「ほとんど、またはまったく優位なし」と評価）。対策は鍵長2倍（AES-256）。指数加速のショアとは脅威の質が違う（STAGE6）

確認クイズ

Q1. グローバーのアルゴリズムでAES-128の鍵を見つけるのに必要なオラクルの回数は、おおよそ？

Q2. グローバーの反復2⁶⁴回を、量子コンピュータを1万台並べて手分けし、1台あたり2⁶⁴÷1万回に短縮する――この作戦が成り立たない理由は？

Q3. 量子コンピュータ時代に向けた、AESなど共通鍵暗号の標準的な対策は？

← 前のステージ