量子脅威:どの暗号技術が死に、どのが生きるのか? (あるいは:なぜZK-STARKはPQ安全なのか?) 以前、量子コンピュータの仕組みを説明しました: 問題解決は迷路から脱出しようとするものだと考えてください。 可能なルートはたくさんあり、出口を見つけるまではすべて確認する必要があります。これが古典的(量子ではない)コンピュータの仕組みです。 しかし、量子力学の法則はより良い方法を可能にしています。これらは(粒子の集合体)が迷路内の*すべての*異なる経路を並行して探索できるようにします。出口にたどり着く道は有効で、行き止まりに続く道は消えてしまいます。 そして宇宙は残された有効な道の中からランダムに一つを選ぶ(これはアインシュタインが「神はサイコロをしない」と言った部分で、実際にサイコロをするのは神だけだと言った)。 これが、古典的なコンピュータで何百万年もかかる問題をQCが解決する方法です。 しかし、量子コンピュータで解読可能な暗号プリミティブの中には、安全に保たれるものもあります。 どうしてこんなことが可能なのでしょうか? 前回の説明で重要な部分を省きました:すべての迷路が同じではありません。 行き止まりの道が消え、宇宙には出口にたどり着く良い道しか残らない迷路もあります。 私はこれらを「量子イージー迷路」と呼んでいます。なぜなら、宇宙がそのような迷路の経路をサンプリングすると、必ず出口へと続く道だからです。迷路の終わりに簡単にたどり着ければ、壊しやすいということです。 しかし、「量子難関迷路」では、行き止まりであれ出口に至ろうと、すべての道が「生きた」ままです。 このような迷路において、量子コンピュータは古典的なコンピュータと変わらない。神がサイコロを投げて道を選ぶとき、すべての道――良い道も悪い道も――同じ確率で現れます。 量子コンピュータは古典コンピュータの類似を行い、迷路内の単一の経路をランダムにチェックします。 今、あなたはおそらくこう尋ねているでしょう: どの迷路が量子的に簡単で、どれがそうでないのか?...