ゼロ知識証明を5つの難易度で解説

コンピューターサイエンティストであり、UCLAサミュエリ工学部の教授であるアミット・サハイ (Amit Sahai)氏が、このWIREDの制作ビデオで、子供から専門家まで5つの難易度でゼロ知識証明を解説します。この概念は物理的な例えを用いて実演され、技術的な深さを増しながら議論されることで、暗号技術における最も重要な概念の1つを誰もが理解できるようにしています。

このトランスクリプトは、WIREDが公開した元のビデオのトランスクリプト (opens in a new tab)のアクセシブルなコピーです。読みやすさのために軽く編集されています。

イントロダクション (0:00)

アミット・サハイ: こんにちは、私の名前はアミット・サハイです。UCLAサミュエリ工学部のコンピューターサイエンスの教授をしています。今日は、ゼロ知識証明について、5つの段階に分けて難易度を上げながら説明してほしいと頼まれました。

ゼロ知識証明とは、プルーバーが検証者に対して、ある記述が真であることを納得させつつ、その記述が真であるという事実以外の追加情報を一切明かさない方法です。ゼロ知識証明は、ブロックチェーンや暗号資産で使用されています。暗号技術者たちがゼロ知識に興奮しているのは、その驚くべき数学的特性のためだけでなく、非常に多くの異なるシナリオに対する信じられないほどの適用性があるからです。

レベル1: 子供 (0:41)

アミット・サハイ: 好きな科目は何ですか？

チェルシー: 算数かな。小さな問題でも、実はすごく大きくて複雑だったりするから。パズルみたいで。

アミット・サハイ: 私も同じ理由で数学が大好きです。今日は、ゼロ知識証明というものについてお話しします。ゼロ知識証明には、プルーバーと検証者の2人がいます。私はあなたに何かが本当であることを証明したいのですが、奇妙なことに、その理由を一切言わずに本当だと証明したいのです。私が初めてこれを聞いたとき、「待って、何それ？ どうしてそんなことが可能なの？」と思いました。

では、この写真には何が写っていますか？

チェルシー: たくさんのペンギン。

アミット・サハイ: そうですね。このペンギンたちの中に、ツノメドリ（パフィン）が隠れています。探してみますか？ どこにいるかわかりますか？ 私はどこにいるか知っていますが、あなたには教えたくありません。私を信じますか？

チェルシー: うん。

アミット・サハイ: でも、ツノメドリがどこにいるかを明かさずに、私がその場所を知っていることを証明できたらどうでしょう？ 見せてあげましょう。その写真をこのポスターの後ろに置きました。あの穴から覗いてみてください。

チェルシー: ツノメドリが見える。

アミット・サハイ: このボードを見たとき、写真がどこにあったかはわかりませんよね？ 写真の角がここにあって、ツノメドリがずっとこっち側にいたのか？ それとも写真の角がここにあって、ツノメドリが反対側にいたのか？ これがゼロ知識証明の本当にシンプルな例です。私はツノメドリの場所を知っていることをあなたに納得させましたが、あなたはそれ以外のことを何も知りませんでした。

チェルシー: どうしてゼロ知識証明を勉強しているの？

アミット・サハイ: 初めて知ったとき、ただすごくかっこいいと思ったんです。でも、ツノメドリを見つけるだけでなく、実はとても役に立つことがわかりました。パスワードを入力して、ハッカーがコンピューターをハッキングしたら、パスワードを盗まれてしまいますよね。でも代わりに、ゼロ知識証明を使ってログインできたらどうでしょう？ 何も明かすことなく、自分がチェルシーであることを証明できるのです。それができたら素晴らしいですよね。ハッカーがコンピューターをハッキングしても、何も知ることはできません。なぜなら、コンピューターでさえ何も知らないからです。

ではチェルシー、あなたの言葉で言うと、ゼロ知識証明とは何ですか？

チェルシー: ゼロ知識証明は、あることの証明。理由や内容を見せるわけじゃない。ほんの一部を見せるか、本当は手品じゃない変な手品みたいなことをして、相手を納得させるの。そして、理由とかそういうものは一切見せない。

レベル2: ティーンエイジャー (3:31)

アミット・サハイ: ゼロ知識証明という言葉を聞いたことはありますか？

ティーンエイジャー: いいえ、ありません。

アミット・サハイ: これは、プルーバーが検証者に対して、何かが真実であることを、その理由を一切明かさずに納得させる方法です。全く奇妙に聞こえますよね。私がやりたいのは、このダイヤル錠の暗証番号をあなたに明かさずに、私がその番号を知っていることを証明することです。あなたができることは、私が絶対に知らない秘密のメモを書くことです。それを折りたたんで、ここに入れます。そして、もし私が暗証番号を知っていれば、それを開けて、あなたが何を書いたか教えられるはずです。

よし。「私の犬の名前はダグです。」

ティーンエイジャー: 暗証番号が何だったかわかりましたか？

アミット・サハイ: いいえ。つまり、このやり取りのどこにも、あなたがまだ知らない情報は出てきませんでした。それなのに、私は暗証番号を知っていることをあなたに納得させました。

ティーンエイジャー: では、ゼロ知識証明の正確な目的は何ですか？ 何かを証明するけれど、証明しているものを危険にさらすような十分な情報を与えない、ということですか？

アミット・サハイ: 人々は互いを信用していません。もし私が自分の秘密を明かすことなく、何かを正しく行ったことを誰かに証明できれば、その人は私をもっと信用してくれるでしょう。

ティーンエイジャー: これはコンピューター技術とどう関係しているのですか？ 対面でのやり取りですか？

アミット・サハイ: 知っている誰かとメッセージを交換したいとします。おそらく最初に集まって、何か秘密の暗号を考えますよね？ そして、その暗号でお互いにメッセージを書きます。でも、その人に一度も会ったことがなかったらどうでしょう？ もしあなたが私と秘密のメッセージを交換したいのに、私たちが一度も会ったことがなかったら？ 一体どうやってそんなことができるでしょうか？

ティーンエイジャー: 全くわかりません。

アミット・サハイ: 不可能に聞こえますよね？ でもそうではありません。物理的な鍵や物理的な箱は使いません。代わりに数学を使ってこういうことを行います。あなたはメッセージを受け取り、数学を使ってそれを暗号化することができます。そして私は、その鍵を知っていることをあなたに証明し、それを開いて、あなたに送り返すことができます。そうすることで、私は数学的な金庫の数学的な鍵を知っていることをあなたに証明することになります。

では、今日話し合ったことに基づいて、あなたの言葉で言うと、ゼロ知識証明とは何ですか？

ティーンエイジャー: 誰かに知ってほしい本当に重要な秘密があるけれど、すべてを教えたくはない場合のようなものです。ゼロ知識証明を使えば、その秘密をすべて明かすことなく、相手に証明することができます。

レベル3: 大学生 (6:13)

アミット・サハイ: 何を勉強していますか？

大学生: USCビタビ工学部のコンピューターサイエンスの1年生です。データ、インターネット、ブロックチェーン、暗号資産など、あらゆることに興味があります。

アミット・サハイ: ゼロ知識証明について聞いたことはありますか？

大学生: 少し耳にした程度です。

アミット・サハイ: 実は、ブロックチェーンの分野は、ゼロ知識証明が実装されているのを目にする分野の1つであり、これはまだ始まりに過ぎないと考えています。その核心において、ゼロ知識証明は2人の間のやり取りです。私はある記述が真であることをあなたに納得させることができるはずですが、あなたはなぜそれが真なのか全くわからないでしょう。

これにアプローチする方法は、NP完全性と呼ばれるものを通じたものです。NP完全問題とは、解くのが非常に難しい問題です。しかし、もしそれを解くことができれば、クラスNPに属するあらゆる問題を解くことができます。これには膨大な数の問題が含まれます。私たちはNP完全問題を使用して、ゼロ知識証明を通じて信じられないほど多様な記述を実際に証明します。今回見ていく具体的なNP完全問題は、地図の3彩色問題と呼ばれるものです。

ここにたくさんの国がある地図があります。同じ色の国が国境を接しないように配置されています。これが、このような地図が有効に色分けされている条件です。地図がこのように3色で塗り分けられるかどうかは、NP完全問題の一例であることがわかっています。

もしかすると、あなたが本当にやりたいのは、アカウントのアドレスを明かさずに、少なくとも0.3ビットコインを持っているというゼロ知識証明を行うことかもしれません。実は、その記述を受け取り、それを国の地図に変換することができます。その国の地図は、あなたが少なくとも0.2ビットコインを持っている場合にのみ、3色で塗り分け可能になります。

大学生: このようなものをどうやってゼロ知識証明に変えるのですか？

アミット・サハイ: もちろん、最初のステップはすべての色を消すことです。これらの封筒の中にそれぞれ色を入れました。さて、これが有効な色分けであるとどうやってわかりますか？ わかりませんよね。隣り合う2つの国を選ぶ必要があります。ランダムに、好きなように選んで構いません。

大学生: この2つでいいですか？

アミット・サハイ: ここには緑があり、こちらには青があります。ご覧の通り、2つの異なる色です。これで、私がこれを正しく色分けできたという少しの確信が得られました。しかし、2つの国しか見せていないので、それほど大きな確信ではありません。より確信を得る1つの方法は、もっと多くの封筒を開けることですが、それはあなたに情報を明かすことになります。私はそれをしたくありません。

ですから代わりに、後ろを向いてください。そして今、これらの色を変えてみましょう。

ランダムに2つの国を選んでくれますか？ もう一度2つの色を明かしましょう。

大学生: これとこれにします。

アミット・サハイ: すでに持っていたものと同じものを確認するのは賢明ですね。しかしご覧の通り、今は緑ではなく青です。そしてもう一方は緑です。前回見せた色は、これらの新しい色とは一致しません。しかし、今見せているこの色分けでは機能します。つまり私たちがやったことは、あなたがピースを組み合わせるのを不可能にしたということです。そして、これを1000回行い、私が毎回正しく異なる色を見せれば、あなたは本当に納得するでしょう。それだけです。これがゼロ知識証明のすべてです。

大学生: つまり、確率的な証明のようなものですか？

アミット・サハイ: はい。実際の実装では封筒は使いません。暗号化を使用します。しかし、これがプロトコルです。

大学生: では、ゼロ知識証明のより広範な意味合いは何ですか？ 実装においてより実用的であることを意図しているのですか、それとも構造的に何かを証明することを意図しているのですか？

アミット・サハイ: 何かをより効率的にすることではありません。以前はどうすればいいかわからなかったことを可能にすることです。私は自分の秘密を一切明かすことなく、自分が誠実に振る舞っていることを実際に証明できます。その秘密の文書が何であるかを明かすことなく、暗号化された文書に正しく署名したことを証明できるのです。ゲームを変える能力、つまり私たちができることを本当に変える能力こそが、ゼロ知識がもたらすものです。

大学生: ゼロ知識証明を使って、どこでより多くの信頼を築けると思いますか？

アミット・サハイ: 素晴らしい例の1つは選挙です。選挙が正しく行われたこと、つまりすべての投票が数えられ、特定の合計で1人が勝つようにすべてが合算されたことをゼロ知識で証明できれば、誰の実際の投票内容も明かす必要はありません。それなのに、誰もがそれが正しく行われたことを確認できるのです。

レベル4: 大学院生 (11:59)

アミット・サハイ: ここに来てくれて、お話しできてとても嬉しいです、イーライ。あなたの研究について少し教えてもらえますか？

イーライ: 私の研究は暗号技術です。具体的には、マルチパーティ計算プロトコルに取り組んでいます。現在取り組んでいるのは、Google ChromeやTeslaのようなサービスプロバイダーが、個々のユーザーのデータについて何も知ることなく統計を収集できるようにするための、集計統計を計算するシステムです。ユーザーとしての私は、お気に入りのウェブサイトがmylittlepony.comであることをFirefoxに知らせる必要はありません。しかし、彼らは毎日何人のユーザーがmylittlepony.comにアクセスしているかを知ることができます。

アミット・サハイ: それは素晴らしいですね。マルチパーティ計算は私にとって非常に思い入れのある分野です。明らかに、ゼロ知識証明は、証明しているものの詳細を明かすことなく、別の人に物事を証明することです。しかし私の考えでは、ゼロ知識は実際にはそれをさらに超えています。これはマルチパーティ計算でよく見られる包括的な概念であり、そのタスクを達成するために必要なこと以外は何も明かさずに、あるタスクを達成したいというものです。

イーライ: その通りです。そして、実際に誠実に振る舞うために使用する秘密を一切明かすことなく、自分が誠実に振る舞っていることを証明できるようになります。NP完全言語のゼロ知識証明が暗号技術において非常に大きな役割を果たしていることはわかっています。NP完全性との最初の出会いはどのようなものでしたか？

アミット・サハイ: 最初の出会いは、学部生としての最初のアルゴリズムの授業でした。NP完全言語は、それ自体について教えてくれるだけでなく、この問題を解くことで、実際に非常に興味深い問題のクラス全体について教えてくれるという驚くべき問題です。

イーライ: 証明を、お互いに話し合うインタラクティブなゲームとして考え始めたとき、それがゼロ知識を可能にしたのでしょうか？

アミット・サハイ: 全くその通りです。そして、ランダム性が何かを証明するのに役立つというアイデアも、証明のプラトン的理想を考えると、非常に直感に反するように思えます。そこにはランダム性も非決定性も存在しませんから。

イーライ: それは、証明を根本から覆すというアイデア全体に関係しています。古い古典的な証明では、すべてを明白にし、情報の流れを明らかにしようとするため、ランダム性は達成しようとしている目標に明確に反します。しかし、それを根本から覆し、もはやそれをしようとしなくなると、突然ランダム性のすべての悪い特性が良いものになります。

アミット・サハイ: その通りです。ランダムは予測不可能であり、それこそが私たちが望むものです。その予測不可能性が、隠したい情報を実際に隠してくれることを望んでいます。あなたが取り組んだプロジェクトでは、ゼロ知識をどのように使用しましたか？ どのような課題がありましたか？

イーライ: 通常、最も難しいのは、それを使用するのに最適な場所を正確に見つけ出すことです。私はゼロ知識をより理論的な方法で使用した論文をいくつか書きましたが、応用となると、これまで見た中で最もエキサイティングな応用のいくつかはブロックチェーンの分野にありました。

アミット・サハイ: 効率のボトルネックにはどのようなものがありますか？

イーライ: ゼロ知識証明の最もクールな点の1つは、非常に多くの種類があることです。私はそれらをフレーバーと呼ぶのが好きです。一般的に、アプリケーションでゼロ知識証明を使用する場合、主なボトルネックはプルーバーにある傾向があります。

アミット・サハイ: プルーバーの仕事を、多くの並列計算に分割することはできますか？

イーライ: それはとても面白い質問ですね。分野として、私たちはまだその答えを知らないと思います。過去3、4年で私が見た最もクールなことの1つは、理論から応用への移行です。過去30年間に人々が考えてきたこれらすべての素晴らしいシステムが、実際に作成できるほど効率的になり始めているのを見ることです。

アミット・サハイ: 間違いありません。特にクラウドコンピューティングでは、クラウドの力を活用してゼロ知識証明を可能にすることは素晴らしいことです。また、ブロックチェーンの分野でも、証明の生成をスピードアップしたい場合、それが分散型の方法でできれば素晴らしいでしょう。私が抱いている希望の1つは、マルチパーティ計算の力が、互いに不信感を抱いている人々を結びつけることにあるということです。暗号技術におけるその力を利用して、現在社会に存在する途方もないレベルの不信感を和らげるのに役立てることはできないでしょうか？

イーライ: それが、私がマルチパーティ計算にこれほど惹かれた理由の1つだと思います。世界で最も重要な問題の1つは、非常に多くの人々が互いを信用していないという事実です。数学を使って、人々が互いを信用しなくても協力できる技術を生み出すことができるというのは、本当にクールで素晴らしい使命です。

レベル5: 専門家 (17:10)

アミット・サハイ: シャンファ、またお会いできてとても嬉しいです。前回お会いしたのは2017年かそのくらいだったと思います。

シャンファ: パンデミック中に一度Zoomでお話ししたと思いますが、直接お会いできて嬉しいです。実は、86年にRSAの「A」であるレオナルド・エーデルマン教授の暗号技術の授業を受けていました。彼は私に、ゴールドワッサー、ミカリ、チャーリー・ラッコフによるゼロ知識証明に関する論文を課題として与えました。ですから、それがこの国での私の初めてのプレゼンテーションでした。ゼロ知識についてのね。

アミット・サハイ: それは素晴らしいですね。ほとんど催眠術のような概念です。

シャンファ: それらの概念を数学的にどのように定式化するかも興味深いです。例えば、データがあります。最終的にデータから、データマイニングを通じて情報を得ることができます。そして、「知識」という言葉があります。知識は哲学においてさえ長く議論されてきました。知識とは何か？ しかしここには、数学者やコンピューターサイエンティストがこの知識を捉えようとする非常に魅力的な方法があります。「ゼロ情報証明」とは言っていません。では、「情報」や「ゼロデータ証明」ではなく、なぜ「知識」なのかについて、あなたはどう考えていますか？ 明らかにそこにはデータがあるので、ゼロデータにはなり得ません。

アミット・サハイ: 全くその通りです。その質問に対して、私たちはまだ完全に満足のいく答えを持っていないと思います。非常に美しい洞察だったのは、ゼロ知識とはすでに予測できるものであるというアイデアです。もしすでに答えを予測できるなら、そのやり取りによって何の知識も得ていないはずです。未来を正確に予測できること、そしてそれが新しい知識の欠如の証拠であるというこの洞察は、非常に美しく、驚くべき洞察でした。

シャンファ: そうですね、ここにはゼロ情報というわけではありません。根本的に、コンピューティングとセキュリティの観点から重要なのは、どれだけの情報を得たか、どれだけのデータを持っているかよりも、どれだけの知識を得ているかです。データはすぐに知識を意味するわけではありません。しかし、人々は常に区別できるわけではありません。

アミット・サハイ: その通りです。例えば、医学研究において、化合物の構造を明かすことなく、薬があり、それがこのモデルで機能することを証明できたら、どれほど素晴らしいでしょうか？

シャンファ: この分野の次の方向性は何だと思いますか？

アミット・サハイ: ゼロ知識プログラムというこの概念は、やり取りなしに、完全に任意の計算をゼロ知識の方法で実行できるようにするでしょう。私はただプログラムを受け取り、それをゼロ知識プログラム、あるいは難読化されたプログラムに変換して、あなたに送るだけです。あなたはそれを実行し、私ともう話すことなく、その計算の恩恵を得ることができます。

シャンファ: その通りです。非対話的な性質があります。しかし、そこには検証可能性があります。ブロックチェーンでも、より一般的なゼロ知識証明を台帳に組み込み始めました。

アミット・サハイ: 私たちは間違いなく今、ゼロ知識がますます使用されるようになる瞬間にいます。ゼロ知識の分野には、あなたや私が招待されないカンファレンスや会議がたくさんあります。なぜなら、それは私たち数学者ではなく、開発している人々、プログラミングしている人々のためのものだからです。そして、それは1つのサインだと思います。私たちの赤ちゃんが成長し、開発される時期が来たというサインです。

シャンファ: 深く考えると、学生たちはよく私に、暗号技術、ゼロ知識証明、現実世界、そして数学的コンピューティングの両方において、将来の方向性は何ですかと尋ねます。

アミット・サハイ: 素晴らしい質問です。未来が見えればいいのですが。見えませんが、試してみましょう。私たちは過去数十年間、暗号技術において多くのことを行ってきましたが、理解していることはごくわずかだと思います。最も基本的な側面は、困難さを理解することです。どうやって難しい問題を得るのか？ 効率的なゼロ知識プログラムや証明を構築するために使用できるように、数学的に難しい問題を実際にどのように構築するのか？

シャンファ: 量子コンピューティングにおいても、さらに難しい問題が必要になると思います。

アミット・サハイ: その通りです。量子コンピューティングの脅威が迫っている今、量子コンピューターが多くの暗号システムを破る可能性があることは誰もが知っています。これは深刻な課題です。では、量子耐性のある、つまり量子コンピューターでさえ破ることができない新しい困難さの源を見つけることができるでしょうか？ それが、私がここ数年取り組んできたことです。

シャンファ: しかし、それらが美しい数学の動機付けになると確信しています。

アミット・サハイ: はい、その通りです。現実世界の素晴らしい点の1つは、現実世界の人々には要求があるということです。そして、それらの要求はしばしば不可能に聞こえます。そこで私たちの出番です。不可能を可能にするのが私たちの仕事なのです。