スターク対スナーク、そして量子脅威 有名なのは、STARKはポスト量子安全ですが、SNARKは量子コンピュータに突破されます。なぜでしょうか。 ここで言及しているのは、皆さんがよく知っている楕円曲線のSNARKs(例えばGroth16のような)です。 SNARKは「証明鍵」の秘密を使って、証明者が特定の質問に答えられるようにします。秘密を作る方法は、ある数学的な演算を何度も繰り返すことです。 良い例えとして、ルービックキューブから始めてある操作(例えば片面をひねる+手の中でキューブを回す)をするようなものです。そして、それを何度も、何百万兆回も繰り返す。その操作を正確に何回行うかが秘密です。そして、壊れたルービックキューブを世界中に見せる。 もしキューブを見て、この状態に至るまで何回この操作が行われたか答えられたら、SNARKを破ることができます。 一つの方法は、ルービックキューブを手に取り、何回操作を繰り返して公開されている設定にたどり着くかを数えていくことです。しかしそれには多くの時間がかかります(百万億億歩数)。 ああ、量子コンピュータとは立方体を見て数字を吐き出す非常に賢いコンピュータです。例えば112,302,305,166回も。この答えでSNARKは壊れました。 じゃあ、STARKはどう? この場合、STARKを壊すには「ハッシュを壊す」必要があります。 ハッシュの仕組みはこうです:ルービックキューブを使って、その操作の一つを行います。それから紙にパターンを書き、折りたたみ、切り、四角を変な形で並べて新しいルービックキューブに貼ります。次にルービックキューブでもう一度操作し、また紙に進みます。などなど、さまざまなことが続きます。 重要な点はこうです:SNARKの場合、数学的には「グループ演算」と呼ばれる一種類の操作だけを行うのではなく、STARKではつながりや構造を欠く非常に異なる操作を大量に混ぜ合わせることになります。 そして、この多くの要素の混ざり合いこそが、古典的・量子的なコンピュータを混乱させ、そして問題を救う要因となっています。 最後です。