、著者：Guo Yu、許可を得てOdailyによって複製されました。

ゼロ知識証明について聞いたことがある人は多いと思いますが、シミュレーションについて聞いたことがある人は少ないと思いますが、ゼロ知識を理解するにはシミュレーションが鍵となります。「ゼロ知識」と「証明」を初めて理解する最初の記事「

「ゼロ知識」と「証明」を初めて理解する

直観主義の観点から説明すると、対話型システムで情報漏洩があることを証明するには、どのビットが情報漏洩を引き起こしているかを証明すればよいだけですが、情報漏洩がないことを証明したい場合は、すべての情報の流れに直面しなければなりません。たとえば、1、2、3、4、5、... の番号が付けられたビットは、いかなる情報も明らかにしません。審査員の皆さん、これは難しいですか？

セキュリティの定義と区別不能性

まず第一に、対話システム、つまり対話、その「知識ゼロ」を証明する必要があります。結局のところ、現代の暗号は厳密な正式なシステムに基づいて構築されています。証明する前に、「安全性の仮定」が何なのかを明確にする必要があります。いわゆるセキュリティの前提、たとえば、システムの権限分離は非常に厳密であり、各ユーザーは許可された情報のみを参照できると言われますが、これは管理者アカウントがクラッキングされていないというセキュリティの前提に基づいています。もう 1 つの例は、モバイル バンキング ソフトウェアでは、転送機能が SMS 認証コードを通じてのみ完了できることです。これも、携帯電話の SIM カードが複製されていないというセキュリティ上の前提に基づいています。安全だと思われるすべてのシステムを詳しく調べてみると、それほどしっかりしているとは思えないセキュリティ上の前提条件が多数存在します。ビットコインの秘密鍵は安全ですか?ビットコイン アカウントには多くのセキュリティ上の前提条件もあります。まず、ニーモニックが他人に知られることはありません。モバイル ウォレットに秘密キーを保存するための暗号化アルゴリズムは十分強力であり、キー導出アルゴリズムは規則的であり、ニーモニックを忘れることはできません。 、 等々。

セキュリティを前提とせずにセキュリティについて語るのはフーリガン行為です。すべてが安全です。数学的な証明ができて初めて、このアルゴリズム/スキームのセキュリティが非常に明確な「セキュリティの前提」に基づいていることを誰もが確信できるようになります。

証明の前に、まだ欠けているものが 1 つあります。それは、「安全性の定義」です。ほとんどの人の認知システムにおいて、セキュリティはあらゆるものをインストールできる箱のようなものです。みなさん、安全という言葉を語るときによく思い出してください、安全とは何かについて考えたことはありますか？どのように安全だと考えられますか?

「セキュリティ」には数学的な意味での厳密な定義が必要です

偉大な科学者であるクロード シャノンは、情報理論の観点から非常に信頼できるセキュリティの定義を示しました [2]。

完璧なセキュリティ: あなたが攻撃者であると仮定すると、暗号文を通じて貴重な情報を取得することはできず、暗号文を解読する唯一の方法は盲目に頼ることです。

皆さん、考えてみてください。この定義は非常に興味深いものです。暗号文を通じて情報を取得することはできません。つまり、余分な計算能力が得られず、平文をより短時間で計算するのに役立ちます。

しかし、この定義は非常に完璧であるため、使用される暗号化アルゴリズムがこのセキュリティ定義を満たすのは困難です。その後、Goldwasser や Micali らは、歴史に記録される別の古典的な「確率的暗号化」[2] を作成しました。

この文書では、セマンティック セキュリティという概念が定義されています。いわゆるセマンティック セキュリティは、完全なセキュリティの定義に関するいくつかの要件を緩和します。

セマンティック セキュリティ: あなたが攻撃者であると仮定すると、多項式時間の暗号文を通じて貴重な情報を計算することはできません。

繰り返しますが、「現実世界」では、あなたに話しかけているのは本物の正直なアリスですが、「理想世界」では、あなたに話しかけているのはズリス（偽のアリス）ですが、ズリスは見た目も言語も同じです。アリスと同じです。しかし、違うのは、ズリスが「知識」を知らない、つまり、三色問題の答えを知らないということです。

その後、両方の世界で、あなたの 2 人の分身が同時に本物のアリスと偽のアリスと会話します。奇跡が起こりました。最終的に、2 つの世界であなたのアバターは両方とも確信し、n 回の挑戦の後、誰も不正行為を発見できませんでした。つまり、「あなた」の 2 つのアバターは、相手が本当に相手であると信じました。 「答え」は分かりました。つまり、「あなた」には、自分が「現実世界」にいるのか「理想世界」にいるのかを「区別」する能力はなく、もちろん、話している相手が「現実世界」なのか「理想世界」にいるのかを「区別」する能力もありません。アリスとかズリスとか。それだけではなく、メロンを食べる人たちにとっても、どんな世界でも「私」を観察者として置いたら、私もあなたと同じように、目の前の「アリス」に見える人が本物なのか、本物なのか「区別がつかなくなる」のです。偽物ではありません。

脳が燃えるような結論は次のとおりです。

なぜこの対話型システムは「知識ゼロ」なのでしょうか？

ズリセには知識がなく、アリスと見分けがつかないからだ。

別の言い方で説明しましょう。あなたも私もどちらの世界にいるのか区別できないため、2 つの世界間の相互作用プロセスはほとんど区別できず、どちらかの世界については何も知識がありません。したがって、この相互作用は合意であると言えます。・「地図の三色塗り問題」は「知識ゼロ」です。

ここにも前提があります。理想世界はアルゴリズム的に構築可能でなければなりません。そして、アルゴリズムによって「理想の世界」を「シミュレート」し、Zliceと呼ばれるアルゴリズムを構築する「神」がおり、インプットとしての「知識」を持たない、つまり「知識ゼロ」であり、さらに「 「理想世界」と「現実世界」は全く同じです。

会話中に本物のアリスが情報を漏らした場合、目の前にいるのが本物のアリスなのかズリスなのかはすぐに分かりますが、ズライズが情報を漏らしたふりをすることは不可能です。したがって、次のように結論付けることができます。

本物のアリスは何も情報を漏らしませんでした。

さて、ここでは「知識ゼロ」を定義するために「シミュレーター」という概念を使います。

次に、ゼロ知識を証明するリンクに入り始めます。

Save World State as Snapshot X

副題

2つの世界を分ける

ゼロ知識証明プロセスは、シミュレーターが「知識なし」で理想世界をシミュレートできる「シミュレーション」アルゴリズムを構築 (発見) することに相当します。このアルゴリズムが存在し、2 つの世界が区別できなければ、証明は完了です。

待ってください、もしかしたら「あなた」は何かがおかしいと感じるかもしれません。

実はここに重要なポイントがあり、映画『インセプション』のスチール写真をお借りすると、「理想の世界」には「現実の世界」とは根本的に異なるものがいくつかあります。これが二つの世界を区別する鍵であり、私たちを「認識不能」にするのです。これは夢の中の独楽ではなく、一種の「超能力」、シミュレーターシミュレータが持つ超能力である。

たとえば、「過去に戻る」などの超大国です。

画像の説明

（上の写真は映画『グラウンドホッグ・デイ』のスチール写真。主人公は目覚めるたびに2月2日の朝に戻り、常に同じ日を生きることになる）

待ってください、読者の皆さん、私たちは今、区別不能性について議論していませんでしたか？なぜ 2 つの世界を再び区別する必要があるのでしょうか? "私は混乱しています"。パニックにならないでください。いわゆる区別不能性は、理想的な世界における個人の認識を対象としています。そして「微分可能性」は世界の外にいる神々のためのものです。

想像してみてください。私たちの周りに、時空を超えたり、1年前に戻ることができる能力を持った人がいたら、私たちのような一般人は完全に（孟）（孟）に混乱して、何もできなくなるでしょう。知覚すること。そして、もし「シミュレーター」が自ら構築した「理想世界」において「時間の逆転」を実現できれば、それによって検証者である「あなた」も、観察者の「私」も欺くことができる、不思議なことが実現できるのです。 「あなた」にとって、「理想の世界」では時間を巻き戻すことができるが、「現実の世界」では現実のアリスが超能力を持つことは当然不可能であることは理解しています。あなたも私もどちらの世界にいるのかは分かりませんが、少なくともこの 2 つの世界の「現実世界」では、反対側のアリスが私たちを騙すことができないことはわかっています。私たちがいる世界。

まず第一に、「知識ゼロ」はアリスの利益を保護するためです。なぜなら、アリスは対話プロセス中にボブにこれ以上の情報を開示したくない、ボブに自分の秘密を知られたくない、さらにはボブにAさえ分析してほしくないからです。ほんの少しの情報。では、これを確実にするにはどうすればよいでしょうか?このとき登場する「シミュレーター」は、現実世界と全く同じ「理想の世界」をシミュレートすることができ、この世界のあらゆる敵を簡単に欺き、人間の行動を不可能にする。相手が現実の世界にいるのか、理想の世界にいるのかを知ることができます。 「シミュレータ」は秘密ｗを手にしていないため、「理想世界」は知識ゼロである。そして、2 つの世界は区別できないため、アリスの対話プロトコルは「ゼロ知識」であると結論付けることができます。

• 地図の三重色問題の知識ゼロの証明

• 「地図 3 つの色分け問題対話型システム」を思い出してください。

• ステップ 1: アリスは地図の色の答えを完全に置き換え、すべての頂点を紙で覆い、それをボブに渡します。

• ステップ 2: ボブはランダムにエッジを選択します

ステップ 3: アリスは指定されたエッジの両端の頂点にある紙を開き、ボブは 2 つの頂点の色が同じかどうかを確認し、異なる場合は合格、同じである場合は失敗します。

最初のステップに戻り、n 回繰り返します

次に、上記の対話がゼロ知識であることを証明します。ここでは、検証者のボブが正直であると仮定します。これは、誰もが証明プロセスを理解するのに役立ちます。次に、ボブが不正である場合の証明方法について説明します。

「理想の世界」においてボブが話しかけるのは、世界全体の姿を模倣した「シミュレーター」だ。ボブは、3 色問題の対話プロトコルに従って対話します。シミュレーターには 3 色の答えはなく、すべての頂点を灰色に着色するだけです。

まず、シミュレーターはアリスを模倣し、各頂点を紙で覆います。それからボブに送ります。

ボブはランダムにエッジを選択し、証明者に挑戦します。

このエッジの両端の色が灰色であるため、シミュレーターは現時点では用紙を開くことができません。

この時、シミュレーターは「超能力」を発揮しようとしていたが、彼は時間を巻き戻すスキルを使い、会話の最初の段階に戻る。

シミュレーターは現在、最初のステップにあり、下端の端を別の色に染め、紙を再度覆い、ボブに送ります。

このとき、ボブは時間が最初のステップに戻ったことを認識できず、彼にとってすべてが新しく、「正直に」再び下端を選択します。

この時点で、シミュレーターは安全に紙を開いてボブに確認させることができます。ボブは明らかにだまされるだろう。その後、ボブはこのプロセスをラウンドごとに繰り返し、そのたびにシミュレーターは時間を遡ってボブを騙すことができます。

不正直なボブ

昔、バグダッドという街にアリババという男がいました。アリババは毎日市場へ物を買いに行きます。

ある日、アリババは泥棒に財布を奪われ、洞窟の入り口まで泥棒を追いかけると、泥棒は姿を消しました。アリババは、下の図に示すように、洞窟の入り口で 2 つの分岐点を発見しました。

アリババは泥棒がどっちに行くのかわからなかったので、「左」の分岐点を見てみることにしましたが、すぐにアリババはここが行き止まりで泥棒の痕跡がないことに気づきました。その後、もう一度確認するために「右」の分岐点に行きましたが、やはり行き止まりで、泥棒の痕跡はありませんでした。アリババは心の中で言いました、「あのいまいましい泥棒はどこへ行ったんだ？」

翌日、アリババは再び物を買うために市場に行きました。今度は別の泥棒が彼のカゴを盗み、アリババは昨日と同じ洞窟の入り口まで泥棒を追いかけましたが、泥棒は再び姿を消しました。 「分岐して見て、泥棒は見つかりません。次に左に行って見てください、これも泥棒はいません。」これはとても不思議なことです。

３日目、４日目、・・・、４０日目も同じような展開で、アリババは４０人目の泥棒を謎の洞窟まで追いかけ、泥棒は消えてしまいました。アリババは、この洞窟には何か仕掛けがあるに違いないと考え、「右」の分岐点の先に隠れて、長い間辛抱強く待ちました。」この時、壁が開き、犯人らが駆け込んだ後、再び壁が閉まり、その時、別の被害者が追いかけてきましたが、長い間探しましたが、何も見つかりませんでした。

アリババは彼らがいなくなった後にその呪文を試してみましたが、それは非常に効果的で、アリババは壁が「左側」の側道に通じていることに気づきました。その後、アリババはその呪文を置き換える方法を見つけ、羊皮紙に新しい呪文と洞窟の場所を書きました。

注：この時点では物語は終わりません…（字幕） 長い長い時を経て

それから何年も経ち、1980年代にアリババの羊皮紙が数人の暗号学者の手に渡った。彼らはバグダッドに行き、洞窟の場所を突き止めた。何世紀も経った今でも、その呪文は今でも有効である。これら数人の暗号学者は興奮して壁を開け、二つの分岐点の間を行ったり来たりしました。

テレビ局はすぐにこの奇妙な出来事を知り、暗号学者のミック・アリ (暗号学者ミカリと同じように発音) は、自分がその呪文を知っていることをテレビの視聴者に見せることに決めました。誰もが洞窟の入り口で待っていました。このとき、ミック・アリは、一人で洞窟に入り、司会者がコインを投げてミック・アリがどの分岐点から逃げ出すかを決めた。アリババと四十人の盗賊を記念して、ミック・アリは 40 回繰り返し、毎回成功を収めました。

これを見ていると、だんだん「シミュレーション」というものが好きになってきませんか？ここで、2 番目のテレビ局の司会者は、「時間を巻き戻す」のではなく、ビデオをカットします。彼の「理想世界」、つまりテレビで放送されるコンテンツが存在する世界への外部介入は、同じ効果をもたらした。理想的な世界では、編集は本質的にスーパーパワーです

この話は実際、1989 年のミミ会議で発表された論文「ゼロ知識プロトコルを子供に説明する方法」(子供にゼロ知識プロトコルを説明する方法) [3] から来ています。

副題

シミュレーションとチューリングマシン

超能力に関して言えば、これは非科学的だと思いますか?そう、何も考えずに「超能力」を使って何かを説明すると、論理は一貫性を失います（一貫性）。理想的な世界では、シミュレータは気軽に開くことはできません。たとえば、シミュレータはボブの内部状態を直接変更してはなりません。たとえば、ボブは検証ステップで明らかに失敗しましたが、シミュレータは検証結果を「」に変更することを要求します。それは、「対話型システムは知識がゼロである」という間違った結論を証明することになります。

シミュレーターは理想世界における全能の神ではありません。

では、エミュレータとは一体何なのでしょうか？シミュレータは実際には単なるチューリングマシンです。 「時間を巻き戻す」「映像を編集する」といったいわゆる超能力は、神秘的な超能力ではなく、チューリングマシンによって実現される機能である。コンピュータの専門家であれば、VMWareや仮想マシンなどを使ったことがあると思いますが、この記事でいう「シミュレータ」とは、コンピュータ環境を仮想化する「仮想マシン」ソフトウェアのことをイメージしていただければと思います。文章。 「過去に戻る」をどう説明するか？仮想マシン ソフトウェアの「スナップショット」機能 (スナップショット) を使用したことがあるのか​​わかりませんが、スナップショットを使用すると、仮想マシン ソフトウェアは仮想コンピュータ全体のすべての状態を保存し、いつでも仮想コンピュータの状態を保存できます。仮想マシン ソフトウェアを復元できます。スナップショットを保存した場所に移動して、実行を続行します。

注: 実は、いわゆる時間反転はコンピュータの基本的な動作であり、プログラミング言語理論には Continuation という概念があります。抽象的に言えば、継続は現在から未来までの計算を表します。 Continuation は制御フローの明示的な抽象化であり、goto、call-with-current-continuation、さらにはスレッド スケジューリングも Continuation を操作するための演算子とみなすことができます。たとえば、call/cc、つまり call-with-current-continuation は、「バックトラッキング」機能を簡単に実装できます。スナップショットの保存は、現在の継続を保存することとして理解でき、過去の特定の瞬間に戻ることは、この継続を適用することです。

Zlice や Bob に関係なく、オブザーバーはそれぞれ実行可能プログラムです。これらのプログラムは仮想マシンにコピーされます。 Zlice と Bob の会話は、実際には 2 つのプログラム間のコミュニケーションです。オブザーバーは、Zlice プロセスと Bob プロセスの IO 上のフック プログラムです。上のマップの 3 色の「理想世界」にいる正直なボブは、実際には仮想マシンの「乱数ジェネレーター」を呼び出すボブ プロセスであり、この乱数ジェネレーターは Zlice によって操作できます。 「現実世界」とは、仮想マシン ソフトウェアを実行している外部コンピューター環境です。

ゼロ知識を証明するプロセスは、アルゴリズムを見つけること、またはより一般的には、外部コンピューター システム上で実行され、仮想マシンの機能を実現するコードを作成することです。そして、仮想マシンには、入力として「知識」のない Zlice が必要であり、仮想マシンに入れられて実行されるボブを騙すことができます。

シミュレーションはあらゆるところで行われており、ゲーデルの不完全性定理はシミュレーションの概念を使用して、ゲーデル数を使用した形式的な算術をシミュレートします。チューリングは、自らをシミュレートできる「ユニバーサル・チューリング・マシン」という概念を提案しました。

しかし、「シミュレーション」の最も初期の概念は、本の第 7 巻「ユートピア」から来ています [4]。古代ギリシャの哲学者プラトンは、そのような寓話、つまり洞窟の寓話について次のように語っています。

暗い洞窟の中に、目の前の壁しか見えないように育てられた鎖につながれた囚人たちが一列に並んでいると想像してください。これらの囚人の後ろには壁があり、その後ろには火の山があります。火と壁の間を何人かの人々が小道具や人形を持って前後に歩き、小道具や人形が反射の下で壁に影を落とします。火のこと。そして、これらの囚人は一日中これらの影を見ることしかできません。なぜなら、この囚人たちは生まれた時から目の前の洞窟の壁に映る様々な影だけを聞いたり見たりしており、自分たちが見ているその影を現実の世界だと思うからです。

しかしある日、囚人が誤って鎖から抜け出し、振り返ると火が見えました。しかし、彼は薄暗い影しか見て育たず、初めて明るい火を見ました。小道具や人形を見て、もし誰かが彼に、これらの小道具や人形は本物だと言ったら、彼は間違いなく嘲笑し、影は本物だと主張するでしょう。

しばらくして、彼は洞窟にいる囚人たちに同情心を抱き、全員を外に連れ出そうと考えました。しかし、再び洞窟に戻ると、外の明るい世界に慣れてしまったため、はっきりと見ることができませんでした。むしろ、閉じ込められた囚人たちは、彼が盲目で、意味のないことを話し、狂人であると考え、最後に、彼が囚人グループを洞窟から連れ出そうと全力を尽くしたとき、彼は囚人たちによって殺されました。

つづく

これは、鎖に繋がれた囚人たちの列に似た、人間の運命の寓意である 私たちは目に映るものが世界の真実であると思っているが、実はそれは地球に映る影のように幻想なのかもしれない洞窟の壁。

つづく

この投稿では、知識ゼロを理解するために必要な重要な概念であるシミュレーションを紹介します。あらゆるゼロ知識プロトコルは、「理想世界」を構築することで理解できます。この概念に初めて触れた読者は、じっくり考える必要があります。

地図の 3 色問題における「理想の世界」と「現実の世界」の間のボブの対話を振り返ってください。ボブは 2 つの世界を区別できませんが、1 つだけ確信できることがあります。現実の世界では、アリスにはスーパーパワーがないということです。

参考文献

ここで問題が発生します。アリスには超能力がありません。そして、アリスが本当に答えを持っていることを直接証明するものではありません。この対話型プロトコルでは、アリスが知識を持っている必要があることが保証されない場合はどうなるでしょうか? 「知識ゼロ」はアリスの利益を守るが、ボブの利益は誰が保証するのだろうか？この質問は次の記事に残されています。

[2] Shafi Goldwasser and Silvio Micali, Probabilistic Encryption, Special issue of Journal of Computer and Systems Sciences, Vol. 28, No. 2, pages 270-299, April 1984.

[3]Quisquater, J.J., Quisquater, M., Quisquater, M., Quisquater, M., Guillou, L., Guillou, M.A., Guillou, G., Guillou, A., Guillou, G. and Guillou, S., 1989, August. How to explain zero-knowledge protocols to your children. In Conference on the Theory and Application of Cryptology (pp. 628-631). Springer, New York, NY.

[1] 初めての「知識ゼロ」と「証明」の理解. Ambi Lab. 2019.

[5] Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. "The knowledge complexity of interactive proof systems." SIAM Journal on computing 18.1 (1989): 186-208.

[6] Oded, Goldreich. "Foundations of cryptography basic tools." (2001).

[7] Rackoff, Charles, and Daniel R. Simon. "Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1991.

[8] Goldreich, Oded, Silvio Micali, and Avi Wigderson. "Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems." Journal of the ACM (JACM) 38.3 (1991): 690-728.