今回のクエストは、量子コンピュータはなぜ速いのかで通り過ぎた場所を、じっくり掘り返す。始める前に、解きたい問題を先にはっきり掲げておこう。
相手はAES――インターネットの通信を守っている共通鍵暗号だ。詳しい仕組みはSTAGE5で扱うから、いまは「128ビットの鍵kをダイヤルにして、データPを暗号文にかき混ぜる機械」だと思えばいい。
攻撃者は、データPと、正しい鍵Kでかき混ぜた暗号文Cのペアを手に入れた。知りたいのは鍵Kそのもの。手がかりは「候補kでPをかき混ぜた結果がCと一致すれば、そのkが正解」という検算の条件だけ。候補は2¹²⁸個ある。

その疑問に正面から答えるのが、このクエストの目的だよ。先に結論だけ言っておくと、比較はしていない。そして「比較していないのに判定できる」のは、量子の魔法ではなくて、ふつうの論理回路にもともと備わっている性質なんだ。
進み方も先に示しておこう。いきなり128ビットのAESは大きすぎる。だからSTAGE1〜4では「3ビットの値が C=101 と一致するか」というおもちゃの問題で判定回路――以降錠前と呼ぶことになる――の作り方を練習して、STAGE5で本物のAES鍵探索に組み込む。

いいところで立ち止まった。答えはこうだ。これから作る回路は探す装置ではなく、検算する装置なんだ。
さっきの問題設定を思い出してほしい。攻撃者が最初から知っているのは、答え合わせの目標である暗号文C。知らないのは鍵K。本番の回路に刻み込まれるのはCのほうで、探している鍵は回路のどこにも書かれていない。鍵の候補は、検算係の手前でAESの計算にかけられて暗号文に変換されてから、Cと照合される――この組み立てはSTAGE5で見る。
つまり「Cとの一致判定」は、探索の答えではなく検算の道具だ。道具の作り方さえ分かれば、オラクルの謎はほとんど解ける。だから今日は量子の話もいったん忘れて、電気で動くただの回路から始めよう。

それで十分だ。ではおもちゃの問題を正確に決めよう。検算の目標はもう分かっていて、C=101 だとする。やりたいのは、入力されてくる3ビット――上の桁から y₂、y₁、y₀ と呼ぶ――が、この C と一致するかどうかの判定だ。一致していたら1（ランプ点灯）、違ったら0を出す。
きみなら、どう作る？

そう、それで完成だ。ここで、いま作った回路の動きをよく観察してほしい。この回路は
「まず000と見比べる。違う。次に001と見比べる。違う。次に010……」
という動作をしていない。8個の候補のリストも、正解Cを書いたメモも、回路の中には存在しない。入ってきた3本の信号線の電圧が「1・0・1」という条件を満たすかどうかを、その場で、いっぺんに調べているだけだ。

いちばん大事な問いだ。答えは――回路の形そのものだよ。さっき自分で決めたはずだ。「y₁=0 だから y₁ にNOTを付ける」と。つまりどの入力線にNOTを置くかという配線の選び方が、Cの中身をそのまま写し取っている。C=110 用の回路を作るなら、NOTの位置は y₀ に移る。
正解の情報は、データとしてしまってあるのではなく、設計図として配線に焼き付いている。だから判定のたびに読み出す必要がないんだ。

いいたとえだ。以降このクエストでは、一致判定回路のことを錠前とも呼ぶことにしよう。
錠前のたとえで、もうひとつ確認しておきたいことがある。錠前は、開けようとする鍵が1本でも100万本でも、作るのは1個でいい。判定の相手が何通りあるかは、錠前の部品数と関係がない。部品数を決めるのは鍵の刻みの数――ビット数のほうだ。

その通り。これがこのステージの核心だよ。「2¹²⁸個の候補がある」ことと「一致判定に2¹²⁸の手間がかかる」ことは、まったくの別問題なんだ。1個の候補について一致を判定するだけなら、128ビットぶんの小さな固定回路で足りる。ふつうのコンピュータの総当たりが2¹²⁸回かかるのは、判定が重いからではなく、候補を1個ずつ順番に入れ直すからだ。
次のステージでは、この錠前をそっくり量子回路に移植する。