知識ゼロの証明: 魔法のようなものですが、説明します

ペギーが秘密を明かさずに、自分が秘密を持っていることをビクターに証明する必要があるとします。彼女はビクターに本当に秘密を知っていると納得させる方法でそうすることができるでしょうか？これは、アイデンティティ システムで使用できる最も強力な暗号化プロセスの 1 つであるゼロ知識証明(ZKP) の中心となる問題です。

たとえば、ペギーがデジタル運転免許証を持っており、バーテンダーのビクターに、運転免許証を渡すだけでなく、生年月日も提示せずに、自分が 21 歳以上であることを証明したいとします。 ZKPは、ペギーが他に何も明らかにすることなく（つまり、余分な知識がまったくない）、ビクターを説得する方法で、ペギーが運転免許証に彼女が少なくとも21歳であることを証明することを許可します。

この問題は、1980 年代に MIT の研究者である Shafi Goldwasser、Silvio Micali、Charles Rackoff によって、情報漏洩と闘う方法として初めて研究されました。目標は、検証者であるビクターが証明者であるペギーについて知ることができる追加情報の量を減らすことです。

ZKP がどのように機能するかを理解する 1 つの方法は、暗号学者 Quisquater、Guillou、および Berson1 によって最初に公開された Alibaba の洞窟の物語です。次の図は、その例を示しています。

アリババの洞窟には、A と B というラベルが付いた 2 つの通路があり、入り口に接続された 1 つの通路から分かれています。ペギーは、A と B をつなぐドアのロックを解除できる秘密のコードを持っています。ビクターはそのコードを購入したいと考えていますが、ペギーがそれを知っていると確信するまでは支払いません。ペギーは、ビクターがお金を支払うまではそれを共有しません。

ペギーがコードを知っていることを証明するアルゴリズムは次のようになります。

• ビクターは洞窟の外に立っている間、ペギーは洞窟に入り、通路の1つを選択します。ビクターはペギーがどのような道を歩むのかを見ることを許されていません。
• ビクターは洞窟に入り、「A」または「B」をランダムに呼び出します。
• ペギーは、入るときにどの選択をしたかに関係なく、簡単にドアのロックを解除できるため、正しい通路から出てきます。
• もちろん、ペギーは運が良ければ推測が当たっただけの可能性もあるため、ペギーとビクターは何度も実験を繰り返します。

ビクターが選んだどの通路からでもペギーがいつでも戻ってくることができるのであれば、ペギーが本当に暗号を知っている可能性は高まります。 20 回試行した後、ペギーがビクターがどの手紙に電話するかを単純に推測する可能性は 100 万分の 1 未満です。これは、ペギーが秘密を知っているという確率的な証拠となります。

このアルゴリズムにより、ペギーはビクターにコードを知っていると説得できるだけでなく、ビクターが他の誰にもペギーがコードを知っていると説得できないようにすることができます。 Victor が取引全体を記録するとします。観察者が見る唯一のことは、ビクターが手紙を呼び、ペギーが右側のトンネルから出てくることです。観察者は、ビクターとペギーが観察者をだますための一連の手紙について事前に合意していなかったのかどうか確信が持てません。

したがって、ペギーはビクターに対して秘密を知っていることを否定できませんが、他の第三者に対しては秘密を知っていることを否定できます。これにより、彼女がビクターに証明したものはすべて二人の間に残り、ビクターがそれを漏らすことはできません（少なくとも、それがペギーからのものであることを証明する暗号的な方法で）。ペギーは自分の秘密とそれを知っているという事実の両方をコントロールし続けます。

私たちが「知識ゼロ」と言って、ビクターが問題の命題以外には何も学んでいないと話しますが、それは完全に真実ではありません。アリババの洞窟で、ペギーは知識ゼロで秘密を知っていることを証明します。しかし、ビクターがペギーについて知ることの中に、ZKP ではどうすることもできないことが他にもたくさんあります。たとえば、ビクターは、ペギーが自分の声を聞き、彼の言語を話し、歩き、協力的であることを知っています。また、ドアのロックを解除するのにどれくらい時間がかかるかなど、洞窟についてのことも学べるかもしれません。ペギーはビクターについて同様のことを学びます。したがって、現実には、証明は完全に知識がゼロではなく、知識がほぼゼロであるということになります。

ZKPシステム

Alibaba's Cave の例は、ZKP の非常に特殊な使用法であり、いわゆるゼロ知識証明です。ペギーは自分が何かを知っている（または何かを持っている）ことを証明しています。より一般的には、ペギーはビクターに多くの事実を証明したいと考えているかもしれません。これらには、命題句や値さえも含まれる場合があります。 ZKP も同様にそれを行うことができます。

知識ゼロで命題を証明する方法を理解するために、 社会主義大富豪問題とも呼ばれる別の例を考えてみましょう。ペギーとビクターが公正な賃金が支払われているかどうかを知りたいとします。具体的には、彼らは同じ金額を支払われているかどうか知りたいが、具体的な時給をお互いに、あるいは信頼できる第三者にさえ開示したくないのです。この例では、ペギーは秘密を知っていることを証明しているのではなく、平等（または不平等）の命題を証明しているのです。

話を簡単にするために、ペギーとビクターには時給 10 ドル、20 ドル、30 ドル、または 40 ドルのいずれかが支払われていると仮定します。

アルゴリズムは次のように機能します。

• ペギーはロックボックスを 4 つ購入し、10 ドル、20 ドル、30 ドル、40 ドルのラベルを付けます。
• 彼女は、給料が書かれた箱以外のすべての箱の鍵を捨てます。
• ペギーは鍵のかかった箱をすべてビクターに渡し、ビクターは自分の給料が書かれた箱の上部のスロットに「+」と書かれた紙片を個人的に入れます。彼は他のすべてのボックスに「-」の付いた伝票を入れます。
• ビクターは箱をペギーに返し、ペギーはプライベートで鍵を使って給料が入った箱を開けます。
• 彼女が「+」を見つけた場合、彼らは同じ金額を稼ぎます。それ以外の場合は、異なる金額が得られます。彼女はこれを使ってビクターに事実を証明することができます。

これは無自覚転送と呼ばれ、命題VictorSalary = PeggySalary知識ゼロで (つまり、他の情報を明らかにすることなく) 真であるか偽であるかを証明します。

これが機能するためには、ペギーとビクターは相手が近日中に来ることを信頼し、実際の給与を表明する必要があります。ビクターは、ペギーが他の 3 つの鍵を捨てるだろうと信じる必要があります。ペギーは、ビクターが「+」の付いた伝票を 1 枚だけ箱に入れることを信頼しているはずです。

デジタル証明書には、自己発行の証明書だけで可能な以上の信頼性を確立するために PKI が必要であるのと同様に、ペギーとビクターが自分たちの発言だけでなく、他人の発言から事実を証明できるシステムでは、ZKP がより強力になります。彼ら自身。たとえば、ペギーとビクターが自分の給与を自己主張するのではなく、人事部門からの署名付き文書を信頼して主張できるとします。これにより、相手が自分の本当の給与を述べていることが両者に分かるようになります。 Verifiable Credentials は、 ZKP を使用して多くのさまざまな事実を単独または組み合わせて証明するためのシステムを提供します。方法に信頼性があり、データに信頼性が得られます。

非対話型 ZKP

前の例では、ペギーは一連のやり取りを通じてビクターに物事を証明することができました。 ZKP が実用的であるためには、証明者と検証者の間の対話は最小限である必要があります。幸いなことに、SNARK と呼ばれる技術により、非対話型のゼロ知識証明が可能になります。

SNARK には次の特性があります (名前の由来)。

• 簡潔:メッセージのサイズは、実際の証明の長さに比べて小さいです。
• 非対話型: いくつかの設定を除き、証明者は検証者に 1 つのメッセージだけを送信します。
• 議論:これは実際には何かが正しいという議論であり、数学的に理解しているような証明ではありません。具体的には、十分な計算能力があれば、証明者は理論的には虚偽の陳述を証明できます。つまり、SNARK は「完全に健全」というよりは「計算上健全」です。
• 知識の：証明者は問題の事実を知っています。

通常、先頭に「zk」（ゼロ知識を表す）が付けられており、このプロセス中に検証者が証明される事実以外何も学習しないことを示します。

zkSNARK の基礎となる数学には、高次多項式に対する準同型計算が含まれます。しかし、zkSNARK が健全であることを保証する基礎となる数学を知らなくても、zkSNARK がどのように機能するかを理解することはできます。数学の詳細を知りたい場合は、 Christian Reitwiessner の「zkSNARKs in a Nutshell」をお勧めします。

簡単な例として、Victor に何らかの値のsha256ハッシュHが与えられたとします。ペギーは、 sを Victor に明かさずに、 sha265(s) == Hとなる値sを知っていることを証明したいと考えています。関係を捉える関数Cを定義できます。

 C(x, w) = ( sha256(w) == x )

したがって、 C(H, s) == trueですが、 wの他の値はfalseを返します。

zkSNARK を計算するには、3 つの関数G 、 P 、およびVが必要です。 Gは、 lambdaと呼ばれる秘密パラメータと関数Cを受け取り、証明鍵pkと検証鍵vk 2 つの公開鍵を生成する鍵生成器です。これらは、特定の関数Cに対して 1 回生成するだけで済みます。パラメータlambda再度必要とされず、それを持っている人は誰でも偽の証明を生成できるため、このステップの後に破棄する必要があります。

証明者関数P 、証明鍵pk 、公開入力x 、および私的 (秘密) 証人wを入力として受け取ります。 P(pk,x,w)の実行結果は、証明者がCを満たすwの値を知っているという証明prfになります。

検証関数V 、証明prf正しい場合は true、そうでない場合は false であるV(vk, x, prf)を計算します。

Peggy と Victor に戻ると、Victor は、Peggy に証明してもらいたいことを表す関数Cを選択し、乱数lambdaを作成し、 Gを実行して証明鍵と検証鍵を生成します。

 (pk, vk) = G(C, lambda)

Peggy はlambdaの値を学習してはなりません。 Victor は、 C 、 pk 、およびvkを Peggy と共有します。

ペギーは、 x = Hに対してCを満たす値sを知っていることを証明したいと考えています。彼女は、次の値を入力として使用して証明関数Pを実行します。

 prf = P(pk, H, s)

Peggy は、検証機能を実行する Victor に証明prfを提示します。

 V(vk, H, prf)

結果が true の場合、ビクターはペギーが値sを知っていると確信できます。

この例のように関数Cハッシュに限定する必要はありません。基礎となる数学の制限内で、 C非常に複雑になる可能性があり、Victor が Peggy に証明したいと考えている任意の数の値を一度に含めることができます。

この記事は、O'Reilly Media から出版された私の著書「Learning Digital Identity」からの抜粋です。

ノート

1. キスカエーター、ジャン＝ジャック。ルイ・C・ギユー;バーソン、トーマス A. (1990)。ゼロ知識プロトコルを子供に説明する方法 (PDF)。暗号学の進歩 – CRYPTO '89: 議事録。コンピューターサイエンスの講義ノート。 435。628–631 ページ。土井：10.1007/0-387-34805-0_60。 ISBN 978-0-387-97317-3。