役に立つ知識を持っていると想像してみてください。秘密のレシピや暗号の鍵などです。 何も明かさずに、あなたがその知識を持っていることを友人に証明できますか? コンピューター科学者は、30 年以上前に、ゼロ知識証明と呼ばれるものを使用すれば可能であることを証明しました。
この考えを理解する簡単な方法として、迷路を通り抜ける方法を知っていることを友達に見せたいとしましょう。道についての詳細は明かしません。 友達が見ることを禁じられている間、制限時間内に迷路を簡単に横断することができました。 (時間制限が必要なのは、十分な時間が与えられれば、試行錯誤を経て最終的には誰でも道を見つけることができるからです。) 友達は、あなたができることは知っていますが、方法は知りません。
ゼロ知識証明は、秘密情報を扱う暗号学者だけでなく、さまざまな問題の難しさを分類する計算複雑性の研究者にも役立ちます。 「現代の暗号化の多くは、複雑さの仮定に依存しています。特定の問題は解決が難しいという仮定に基づいているため、XNUMX つの世界の間には常に何らかの関係がありました」 クロード・クレポー、マギル大学のコンピューター科学者。 「しかし、[これらの]証拠は、つながりの全世界を生み出しました。」
ゼロ知識証明は、対話型証明と呼ばれるカテゴリに属しているため、前者がどのように機能するかを知るには、後者を理解することが役立ちます。 初め 記載された コンピューター科学者による 1985 年の論文で Shafiゴールドワッサー、Silvio Micali と Charles Rackoff によると、インタラクティブな証明は尋問のように機能します。一連のメッセージで、一方の当事者 (証明者) は、与えられたステートメントが真実であることを他方の当事者 (検証者) に納得させようとします。 インタラクティブな証明は、XNUMX つのプロパティを満たさなければなりません。 第一に、真の陳述は常に正直な検証者を最終的に納得させます。 第 XNUMX に、与えられたステートメントが偽である場合、証明者は (特定の知識を持っているふりをしたとしても) ごくわずかな確率を除いて、検証者を納得させることができません。
インタラクティブな証明は、本質的に確率論的です。 証明者は運によって XNUMX つまたは XNUMX つの質問に正しく答えることができます。そのため、検証者が、証明者が実際にステートメントが真であることを知っていると確信するには、十分な数のチャレンジが必要です。
この相互作用のアイデアは、当時カリフォルニア大学バークレー校の大学院生であった Micali と Goldwasser が、ネットワークを介してポーカーをプレーするというロジスティクスに戸惑ったときに生まれました。 すべてのプレイヤーが仮想デッキからカードを取得したときに結果がランダムであることをどのように確認できますか? インタラクティブな証明が先導する可能性があります。 しかし、その後、プレイヤーは、途中ですべてのプレイヤーの手札を明らかにすることなく、プロトコル全体 (ルールの完全なセット) が正しく守られたことをどのように確認できますか?
この目標を達成するために、Micali と Goldwasser は、インタラクティブな証明に必要な XNUMX つのプロパティに XNUMX つ目のプロパティを追加しました。証明は、知識自体について何も明らかにせず、ステートメントの真実性のみを明らかにする必要があります。 「プロトコルを通過するという概念があります。その最後に、[ポーカー プレイヤー] は知っているはずの以上のことは何も知らないと考えられます」と Goldwasser 氏は言います。
古典的な例を考えてみましょう。 アリスはボブに、あるグラフが G — エッジ (線) によって接続された頂点 (ドット) の一意のコレクション — 「ハミルトニアン サイクル」があります。 これは、グラフには、すべてのドットを XNUMX 回だけ訪れ、開始した同じドットで終了するパスがあることを意味します。 アリスは、これを行うパスをボブに示すだけでこれを行うことができますが、もちろん、ボブもそのパスを知っていることになります。
アリスがそのようなパスが存在することをボブに見せずに知っていることをボブに納得させる方法は次のとおりです。 まず、彼女は新しいグラフを描き、 H、それは次のようには見えません G しかし、重要な点で似ています。同じ数の頂点があり、同じ方法で接続されています。 （もしも G は実際にハミルトン サイクルを持っているため、この類似性は次のことを意味します。 H ）次に、すべてのエッジをカバーした後 H マスキングテープでロック H 箱に入れて、その箱をボブに渡します。 これにより、彼はそれを直接見ることができなくなりますが、彼女がそれを変更することもできなくなります. それからボブは選択をします: 彼はアリスにそれを示すように頼むことができます. H 本当に似ている G、または彼は彼女にハミルトニアンサイクルを見せるように頼むことができます H. どちらの要求もアリスにとっては簡単なはずです。 H 本当に十分に似ています G、そして彼女は本当にその道を知っています。
もちろん、アリスがハミルトン閉路を知らなくても、 G、似ていないグラフを描くことによって、ボブをだまそうとすることができます。 G、またはパスがわからないグラフを提出することによって。 しかし、彼らが複数のラウンドをプレイした後、アリスが毎回ボブをだます可能性はほとんどなくなります。 彼女がすべて正しく理解できれば、最終的にボブは、アリスがグラフのハミルトニアン サイクルを知っていると確信するでしょう。 G、ボブはそれを見たことがありません。
そのような証明を最初に記述した最初の論文の後、Micali と XNUMX 人の数学者 (Oded Goldreich と Avi Wigderson) は、広範囲に及ぶ影響を伴う予想外の結果を発見しました。 これは、NP として知られる、ほぼ同じ難易度の問題の主要なカテゴリと関係があります。 これらの問題は解決が困難ですが、その解決策は簡単に確認できます。 三人の研究者 あれを見つけた、本当に安全な暗号化の場合 可能だの場合、NP のすべての問題の解は、ゼロ知識証明でも証明できます。 この研究は研究者を助けました 考える そもそも安全な暗号化さえも必要としないゼロ知識証明の変種。 これらは、マルチ証明者インタラクティブ証明として知られています。
そして1988年、ミカリら 示されました 証明者と検証者がランダムなビットの短い文字列を共有している場合、相互作用は必要ありません。 これは理論的には、ゼロ知識証明はインタラクティブである必要がないことを意味し、21 つの当事者間の絶え間ないコミュニケーションは必要ないことを意味します。 これは研究者にとってはるかに有用なものになるでしょうが、そのような証明が軌道に乗ったのは XNUMX 世紀に入ってからのことでした。
「2000 年代後半に、ゼロ知識証明を構築するための効率的な手法の進化が見られ始めました。 マシュー・D・グリーン、ジョン・ホプキンス大学の暗号学者。 「私たちは、『ちょっと待ってください。実際にこれを実際に使用する方法があるかもしれない』と気づいたところまで来ました。」
現在、証明者は検証者に 2016 つのメッセージを送信でき、両方がオンラインである必要はありません。研究者は、非常に複雑な問題であっても、迅速に検証できる非常に短い証明を作成できます。 これは、トランザクションの詳細を隠しながら暗号通貨トランザクションの後にブロックチェーンを迅速に検証する機能など、いくつかの実用的な用途につながっています. そしてXNUMX年、物理学者のグループが 示されました ゼロ知識証明が核軍縮にどのように役立つか: 核弾頭の設計に関する秘密を一切明らかにすることなく、国は弾頭がアクティブか非アクティブかを核査察官に証明できるようになりました。
最近では、量子コンピューティングの進歩により、Crépeau 氏はゼロ知識プロトコルがまだ実行可能であることを確認するために、過去の研究のストレス テストを行う必要がありました。 2021年、お世話になりました 実証します 複数の証明者によるインタラクティブな証明は、量子コンピューターが関与する場合でも秘密を保持しますが、同じレベルのセキュリティを達成すると、プロトコルがはるかに遅くなります。 この発見は朗報だったが、技術が進歩するにつれて新たな懸念が生じるだろうと彼は言った。
「私たちが将来行う可能性のあるあらゆる種類の計算には、量子コンピューターが関与するでしょう」と Crépeau 氏は述べています。 「したがって、偏執狂的な優れた暗号学者として、システムのセキュリティを評価するときはいつでも、システムが安全であることを確認したいと考えています。」
編集者注: シャフィ ゴールドワッサーはシモンズ財団から資金提供を受けています。 編集上独立した出版物. シモンズ財団の資金提供の決定は、私たちの報道に影響を与えません。
