この記事の由来はこの記事の由来はアンビ研究室（ID:SECBIT）
、著者Guo Yu、許可を得てOdailyによって複製されました。
https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/4/zkp-rom.md
この記事はGithubに更新されました
「挑戦は、時には、あなたに対する主の信頼の表れです。」 挑戦は、時には、あなたに対する神の信頼の表れです。 ― D. トッド・クリストファーソン
シリーズ３：「知」を求めて
交流と挑戦
以前に紹介したゼロ知識証明システムはすべて「対話型」であり、検証者ボブは対話中に挑戦する 1 つまたは複数の「乱数」を提供する必要があります (「地図の 3 色問題」など) (「シリーズ 2」を参照) )、検証者ボブは、ボブが満足するまでアリスの答えに異議を唱える側を「常に」ランダムに選択する必要があり、アリスの不正確率は「指数関数的に」減衰します。そして、ボブがその証明を信じる「根拠」は、ボブが選んだ乱数が十分にランダムであるかどうかによって決まります。アリスがボブの乱数を事前に予測できた場合、大惨事が起こり、現実世界は「理想世界」に変質し、アリスは即座に「シミュレーター」にアップグレードして超能力でボブをだますことができます。
「シリーズ 3」では、シュノア プロトコルを分析しました。このプロトコルでは、検証者ボブは乱数 c を選択してアリスに挑戦し、値 z を計算するよう依頼するだけで済みますが、ボブはアリスに予測能力を持たせてはなりません。 c の値 知識がなければ、アリスもシミュレーターに変身します。
乱数の重要性は自明です。
乱数チャレンジは、インタラクティブなゼロ知識証明の「信頼の根幹」です。
ただし、「インタラクションプロセス」により適用シナリオが制限されます。インタラクティブなゼロ知識証明を「非インタラクティブ」に変えることができたらどうなるでしょうか?とてもとてもエキサイティングなものになるでしょう。いわゆる非対話型は、「1 ラウンド」証明プロセスとみなすことができます。つまり、アリスは検証のために証明をボブに直接送信します。
非対話型ゼロ知識証明、英語はNon-Interactive Zero Knowledge、略してNIZKです。つまり、証明全体が「文字列」にエンコードされ、紙に書いて電子メールやチャット ツールなどのさまざまな方法で任意の検証者に送信できます。文字列は Github に公開して誰でも閲覧できるようにすることもできます。いつでもダウンロードして確認できます。
ブロックチェーンの世界では、「NIZK」をコンセンサスプロトコルの一部として使用できます。トランザクションには複数のマイナーが検証する必要があるためです。想像してみてください。トランザクションの送信者と各マイナーが対話してマイナーにチャレンジさせる必要がある場合、コンセンサスプロセスは非常に遅くなります。非インタラクティブなゼロ知識証明は、すべてのマイナー ノードに直接ブロードキャストでき、マイナー ノードが自身を検証できるようになります。
友人の中には、「マイナーが 1 人だけ挑戦するだけでは十分ではないのですか?」と尋ねる人もいるかもしれません。マイナーとトランザクション送信者の間の対話スクリプトをプルーフにエンコードし、それを他のマイナーにブロードキャストすると、他のマイナーはチャレンジプロセスが信頼できるものであると直接信じるでしょう。それは可能ではないでしょうか?ただし、最初の対話型マイナーは、信頼できるサードパーティ、サードパーティとして信頼される必要があることは明らかです。良いアイデアとは思えません...
インタラクティブなゼロ知識証明ではなく、以下では直接「NIZK」と言うことにします。これは理想的と思われますが、違いを生み出すサードパーティはありません。
「非インタラクティブ」が引き起こす混乱
非対話型ゼロ知識証明 NIZK が存在する場合、対話型証明よりもはるかに強力です。
インタラクティブ証明は 1 人の検証者のみが信頼できますが、NIZK は複数の検証者、さらには全員が信頼できます。
インタラクティブ証明はインタラクションの瞬間にのみ有効ですが、NIZK は常に有効です。
NIZK は空間だけでなく時間もまたがることができます
美しいですね。しかし、……
前のセクションの結論を繰り返します。
乱数チャレンジは、インタラクティブなゼロ知識証明の「信頼の根幹」です。
しかし、NIZKが異議申し立てプロセスに負けた場合、どのような結果が生じるでしょうか?
すでに「ゼロ知識」証明を思い出しました (「シリーズ 2」を参照)。証明プロセスでは、理想的な世界の検証者 (ボブ) と対話するシミュレーター (アルゴリズム) を構築する必要があります。相手が本物のアリスなのかシミュレーターなのかを区別する能力はありません。
ここで、NIZK の非インタラクティブ性を考慮すると、「私」が「真実の」証明 X が書かれた紙を「あなた」に見せ、そして「あなた」がこの論文を読んだ後で本当に私を信じたとします。プロトコルが「ゼロ知識」である場合、「私」をシミュレータに置き換えると、シミュレータは偽証Yを「偽造」することもでき、それによって「あなた」を説得することもできます。
さて、ここで問題が発生します。
X と Y、どちらが真実でどちらが偽であるかをどのように区別しますか?もちろん、違いはわかりません。プロトコルは知識がゼロなので、違いが分からないはずです。
同じようにYさんに見せられるということは、「私」はあなたを騙せるということではないでしょうか？
不調和ですか？ここで2分間考えてください。
(2分後…)
NIZK にはインタラクションがないため、チャレンジプロセスはありません。すべての証明プロセスでは、アリスが計算して書く必要があります。理論上、アリスは好きなものを書くことができ、誰も彼女を止めることはできません。たとえば、アリスは「理想世界」を偽と書きましたYの証拠。
おそらく、シミュレーターを深く理解している友人は、ここで重要なポイントを見つけるでしょう。シミュレーターは「理想世界」でのみ Y を構築する必要があります。つまり、Y と同じくらい邪悪なものは「理想世界」でのみ存在することができます。 「現実世界」は世界にとって災難だ。
考え続ける...
さらに深い問題があります。「地図の三色問題」を思い出してください。シミュレーターが「現実世界」で悪を行えない根本的な理由は、シミュレーターが理想世界では「時間を巻き戻す」という超能力を持っているからです。 「現実世界」にはそのような黒魔術は存在しません。現実世界の「非存在」が鍵となる。
さらに、NIZKでは相互作用が存在しないため、重大な結果につながりますが、シミュレータには「時間を巻き戻す」という超能力を使う方法はなく、当然、2つの世界における証明者の行動を区別することもできないようです。
言い換えれば、NIZKシステムに直面した場合、「シミュレーター」は地上に立つことが難しく、世界に落ちて普通の人間になることしかできないようです。この推論に従って、シミュレーターがもはや超能力を持たないと仮定すると、それはアリスとシミュレーターに何の違いもないことを意味し、アリスもシミュレーターになることができ、そして推測を続けると、アリスは「」になれると私が言いました。ボブがその過程で恣意的にだまされる場合、この証明システムはその「信頼性」を失うため、もはや価値がありません。結論: どの NIZK も信頼できません。
ここで何か問題があるはずです...
上記の分析の過程で、インタラクティブな課題が欠如していることについて言及しました。実際、ボブがアリスの証明生成プロセスに参加しない場合、証明に含まれるすべてのビットはアリスによって提供され、「証明」自体にはボブが信頼できる「ルート」がないようです。これは「直感的に」意味がわからないようです。
ということは、ボブの参加がなければ「信頼のルート」を確立する方法は「完全に」ないということなのでしょうか？信頼の基盤は他にどこから来るでしょうか?
答えは「サードパーティ」です！
待ってください...プロトコルの対話には 2 つの当事者だけが存在するのではありませんか?アリスとボブ、第三者はどこですか?
サードパーティを導入するには特殊な方法が必要であり、方法は複数ありますので、最初の方法から検討してみましょう。
（涙：言い方が悪かったですね、第三者を導入しないんですか？）
Schnorr プロトコルのレビュー
私たちの古い友人である Schnorr プロトコルを見てみましょう。これは 3 ステップのプロトコルです。最初のステップでアリスが Promise を送信し、次に 2 番目のステップでボブが乱数チャレンジを送信し、3 番目のステップでアリスが送信します。挑戦に応えます。
3 ステップの Schnorr プロトコルを 1 ステップに変える方法を見てみましょう。
c = Hash(PK, R)
Schnorr プロトコルの 2 番目のステップを見てください。ボブはランダムなチャレンジ番号 c を与える必要があります。ここでは、プロトコルの 2 番目のステップを省略するという目的を達成するために、アリスに次の式を使用してチャレンジ番号を計算させることができます。
ここで、R はアリスがボブに送信した楕円曲線点、PK は公開鍵です。ハッシュ アルゴリズムを使用して c を計算するこの式をよく見ることができます。この式は次の 2 つの目的を果たします。
アリスがコミットメント R を生成する前に、たとえ変装したアリスによって最終的に c が選ばれたとしても、c を予測する方法はありません。
c ハッシュ関数によって計算され、整数フィールドに均等に分散され、乱数として使用できます (注: ここではこれを理解してください。後で詳しく説明します)
注意してください: アリスは R を生成する前に c を予測することはできません。そうでない場合、アリスは変装した「時間を逆転する」という超能力を持っているので、ボブを任意に騙すことができます。
また、暗号的に安全なハッシュ関数は、SHA256、SHA3、blake2 などの「一方向」です。このように、c はアリスによって計算されますが、アリスには c を選択することで不正を行う能力はありません。なぜなら、アリスが R を生成するとすぐに、c は固定されるのと同じだからです。人間であるアリスには、「現実世界」ではハッシュを逆計算する能力がないと仮定します。
上の図を見ると、ハッシュ関数を使用して 3 ステップの Schnorr プロトコルを 1 つのステップに結合しています。アリスは、(R、c、z) を直接送信できます。そして、ボブは PK を持っているため、ボブは自分で c を計算できるため、アリスは (R, z) を送信するだけで済みます。
上記のスキームを少し変形して、「デジタル署名」スキームを取得しました。いわゆるデジタル署名とは、「太陽は山の果てにあり、黄河は海に流れ込む」などの文字列を「私」が「あなた」に提示し、この詩が正しいことを証明することを意味します。私から提示されたので、何かに署名する必要があります。このことは、私のアイデンティティがこの詩と関係していることを証明することができます。
NIZK の視点から見たデジタル署名
大まかに言えば、デジタル署名スキームは、(1) 私が秘密鍵を持っていること、および (2) 秘密鍵とメッセージが計算に関連付けられていることを証明することに相当します。
まず自分の身元を証明する必要があります。これは簡単です。これが Schnorr プロトコルの機能で、「私は秘密鍵を持っています」という発言を相手に証明できます。そして、この証明プロセスはゼロ知識です。つまり、「秘密鍵」に関する知識は明らかにされません。
m = "それでは、この唐の詩とどのように関係するのでしょうか？ c を計算するプロセスを変更します。"
c = Hash(m, R)
太陽は山の端にあり、黄河は海に流れ込む
ここでは、攻撃者が任意に署名を偽造できないようにするために、離散対数問題（DLP）とハッシュ関数が二次プリイメージ耐性（Secondary Preimage Resistance）を満たすことを前提としています。
注: 厳密に言えば、デジタル署名の偽造不可能性を保証するには、Schnorr プロトコルが「シミュレーションの健全性」というより強力な特性を満たすことを証明する必要があります。これについては、[2]を参照してください。
上の図は、よく知られているデジタル署名スキーム、Schnorr 署名スキーム [1] です。ここには別の最適化があり、R は c, z を通じて計算できるため、アリスがボブに送信するのは (R, z) ではなく (c, z) です。
注: なぜこれが「最適化」なのでしょうか?現在、楕円曲線を攻撃するアルゴリズムとしてはシャンクスアルゴリズム、ラムダアルゴリズム、ポラードのローアルゴリズムがありますが、アルゴリズムの複雑さは[3]程度であり、nは有限体のサイズの桁数であることを覚えておいてください。 2^256 に非常に近い有限体を使用すると仮定します。つまり、z が 256 ビットであれば、楕円曲線グループのサイズはほぼ 256 ビットに近いため、2^256 の平方根は 2^ になります。 128 なので、256 ビット楕円曲線グループのセキュリティは 128 ビットのみです。すると、チャレンジ番号 c は 128bit だけで十分です。このように、アリスは R を送信するよりも c を送信する方がスペースを節約でき、後者には少なくとも 256 ビットが必要です。 c と z の 2 つの値を合計すると、合計 384 ビットになります。一般的な ECDSA 署名スキームと比較して、貴重なスペースの 1/4 を節約できます。現在、ビットコイン開発チームは、ECDSA 署名スキームを、マルチ署名と集約をより柔軟にサポートできる Schnorr のような署名スキーム、muSig[4] に変更する準備ができています。
ハッシュ関数を使用して対話型証明システムを非対話型手法に変更する方法は、フィアット・シャミア変換 [5] と呼ばれ、暗号学のベテランであるアモス・フィアットとアディ・シャミアによって 1986 年に提案されました。
信頼の再構築 - ランダム予言ウィザード
前述したように、異議申し立てがなければ、証拠の「信頼基盤」が失われているように見えます。 Schnorr 署名スキームでは、ハッシュ関数が「チャレンジャー」の役割を果たしており、この役割には「Random Oracle」(ランダム オラクル) という非常に学術的な名前が付けられています [6]。
しかし、なぜここでハッシュを使用するのでしょうか?実際、アリスが公開乱数を生成したい場合、「ランダム オラクル」と呼ばれるものが必要になります。
ブレーンストーミングの時間です!
「現実世界」では、空に「エルフ」がいて、左の列が文字列、右の列が数字である 2 列のフォームを持っていると想像します。あなたと私、アリスとボブを含む誰もが「エルフ」に文字列を送信できます。
エルフは文字列を取得した後、テーブルの左の列をチェックして、テーブルにそのような文字列があるかどうかを確認します。次の 2 つの状況があります。
状況 1: 左の列に文字列が見つからない場合、エルフは「真の乱数」を生成し、その文字列と乱数をテーブルに書き込み、その乱数を地上の人間に返します。
ケース 2: 左の列にこの文字列レコードがある場合、エルフは右の列の数値を直接地面に返します。
このスプライトは乱数生成器のように動作することがわかりますが、それは大きく異なり、同じ文字列を送信すると同じ数値を返すという点が異なります。このエルフは伝説の「ランダム神託者」です。
Schnorr プロトコルをマージするプロセスで、実際に必要なのは、ハッシュ関数ではなく、このようなランダム オラクル ウィザードです。両者の違いは何ですか?違いは次のとおりです。
ランダムオラクルは、新しい文字列に対して毎回一貫した分布を持つ「真の」乱数を返します。
ハッシュ関数によって計算された結果は、一貫した分布を持つ真の乱数ではありません
では、なぜ以前はハッシュ関数が使用されていたのでしょうか?現実の世界では、真のランダムな神託は存在しないからです。なぜ？実際、ハッシュ関数が真の乱数を生成することは不可能です。これは、ハッシュ関数が「決定論的」アルゴリズムであり、パラメーター以外に他の乱数が導入されないためです。
そして、暗号化セキュリティ強度を備えたハッシュ関数は、「疑似」ランダムオラクルとして機能できる「ようです」。次に、結合されたセキュリティ プロトコルには、次のような強力なセキュリティの前提条件を追加する必要があります。
仮説: 暗号的に安全なハッシュ関数は伝説的な「ランダムオラクル」に近似できる
この仮定は証明できないため、この仮定を信頼するか、公理として使用することしかできません。余談ですが、ハッシュ関数の一般化された衝突防止プロパティにより、その出力が乱数をシミュレートできることが決まりますが、同時に、多くの場合 (すべてではありません) ハッシュ関数を攻撃することは非常に困難であるため、多くの暗号作成者が大胆に使っています。
この前提を用いないセキュリティモデルを「標準モデル」と呼び、この前提を用いたセキュリティモデルを「非標準モデル」とは当然言えませんが、「ランダムオラクルモデル」という素敵な言葉があります。
世の中には豆腐が好きな人とそうでない人の二種類がいます。同様に、世界には 2 つのタイプの暗号作成者がいます。ランダム オラクル モデルを好む人と、ランダム オラクル モデルを好まない人です [6]。
構造基盤 - 誘拐されたエルフ
Schnorr プロトコルは Fiat-Shamir 変換を受けると、NIZK プロパティを持ちます。これは私たちが証明した SHVZK とは異なります。SHVZK は検証者に正直であることを要求しますが、NIZK では検証者が対話に参加しないため、検証者に非現実的な要件はありません。正直者を要求するといういわゆる問題が発生します。検証者はもう存在しません。
注: 検証者ボブが不正な場合はどうなりますか?そうすれば、ボブはアリスの知識を引き出すことが可能になります。しかし、3 ステップの Schnorr プロトコルの場合、それが「ゼロ知識」を満たすかどうかはまだ不明です。シリーズ 3: SHVZK の比較的弱い特性を満たすことを証明しただけです。
しかし、Schnorr プロトコルが非対話型のゼロ知識証明システムに変換されると、それは真の「ゼロ知識」になります。
しかし、この主張はもっともだと思われますが、証明できますか?という質問もあるかもしれません。
時間切れです、「翠華、シミュレータに乗って」
シミュレーター手法を使って「理想の世界」を構築するには ？考えてみてください。私たちは以前に「過去に戻る」を使用し、「乱数ベルトコンベア」の超能力を改造して「シミュレータ」に不正行為をさせました。しかし、相互作用はありません。つまり、「時間を戻す」という超能力は使用できません。ボブの乱数コンベア ベルトは存在せず、「コンベア ベルトを改ざんする」という超能力も使用できません。
しかし、シミュレーターは信頼の「根」を構築できるように、常にある種の「スーパーパワー」を備えていなければなりません。
(もしシミュレーターが超能力なしで不正行為を行う能力を持っているなら、それはプロトコルの信頼性が低いことを証明することと同じです)。
おそらく誰もがもうお気づきかと思いますが、シミュレーターは「ランダム オラクル」に基づいて何かを行う必要があります。まず「知識ゼロ」を証明するために「理想世界」を構築することを考えます。理想的な世界では、シミュレーターは予言を提供した責任のある「エルフ」を「誘拐」しました。ボブがエルフに乱数を要求したとき、エルフは実際の乱数を与えず、それをズリスに与えました（シミュレーターはそのふりをします）アリス） 事前に用意された数値（これも一貫した分布に準拠し、区別不能性が保証されています）、「魔神」はランダムに見えるが実際にはバックドアを備えた数値をボブに返す以外に選択肢はありません。
いわゆるバックドアとは、この番号がZlice自身によって事前に選択されることを意味します。
ステップ 1: Zlice は z をランダムに選択し、c をランダムに選択し、R'=z*G - c*PK を計算します。
ステップ 2: Zlice は c と (m, R') をスプライトのテーブルに書き込みます。
ステップ 3: Zlice は署名 (c, z) を Bob に送信します。
ステップ 4: ボブは R=z*G - c*PK を計算し、(m, R) をエルフに送信し、エルフは c' を返します。ここで、Bob の計算された R と Zlice の計算された R' が等しいことに注意してください。
ステップ 5: ボブは、エルフから返された乱数が相手から送信された乱数と等しいかどうかを確認するために、c ?= c' であることを確認します。それらが等しい場合、検証署名は合格しますが、そうでない場合、検証は失敗します。
ズリスは「エルフ」を誘拐することで、乱数を事前に予測することもでき、過去に戻ったのと同じ効果を得ることができる。
シミュレータ Zlice の「存在」を証明したので、上記で NIZK を証明しました。
sk = (z1 - z2)/(c1 - c2)
次に、このプロトコルの「信頼性」を証明します。別の「理想の世界」でも、「エクストラクター」と呼ばれるものがエルフを誘拐したと想像してください。無実のアリスが「エルフ」に乱数を求めると、「エルフ」は c1 を返し、「エクストラクター」はエルフのテーブルから c1 を覗き見しました。アリスが z1 を計算した後、「エクストラクター」はまだスーパーをアクティブにすることができます。 「時間逆行」の力で、アリスを 2 番目のステップに戻し、再び「エルフ」に乱数を要求します。アリスによって送信された文字列は、明らかに最初に送信された文字列と同じです (R, m ）。論理的には、(R, m) はスプライト シートの「左列」にすでに書き込まれているため、正直な「スプライト」は c1 を返すはずです。しかし、「抽出者」はスプライトを誘拐し、テーブルの行 (R, m) に対応する「右列」を別の番号 c2 に変更しました。アリスが別の z2 を計算した後、抽出者はタスクを完了し、次の方程式を通じてアリスの秘密鍵 sk を計算します。
フィアット・シャミールの変革 - パブリックコインからNIZKへ
Schnorr プロトコルだけでなく、あらゆる「Public-Coin プロトコル」でも、Fiat-Shamir 変換を使用してプロトコル全体を 1 ステップの対話、つまり非対話型証明システムに「圧縮」できます。変換技術は、Amos Fiat と Adi Shamir による論文「How to Prove Yourself: Practical Solutions to Identification and Signature Questions.」に最初に由来し、1986 年の暗号会議で発表されました [5]。この手法はマヌエル・ブルムから来たとも言われている[6]。
繰り返しますが、パブリックコインプロトコルでは、バリデーターのボブは、乱数を生成してアリスに挑戦するという 1 種類のことだけを行います。フィアット・シャミア変換を通じて、ボブのそれぞれの「挑戦的な行動」を「ランダムな予言」に置き換えることができます。
特定の実装では、ランダム オラクルは暗号セキュリティ強度を持つハッシュ関数を使用する必要があり (ランダムに選択することはできません。暗号的に安全なハッシュを使用する必要があります)、ハッシュ関数のパラメータはすべて以前のコンテキスト入力である必要があります。以下は図の例であり、このフィアット シャミール変換の実践をすぐに理解することができます。
前述したように、非対話型証明システムでは、ボブがアリスによって構築された証明を完全に信頼できるように、信頼の「ルート」を構築するために第三者を導入する必要があります。ここでの第三者とは「エルフ」であり、学術用語では「ランダム・オラクル」と呼ばれます。このエルフは現実の第三者ではなく、「現実世界」と「理想世界」の両方に存在する仮想的な第三者である。 「現実世界」では責任感があり物静かな美男子のエルフだが、「理想世界」では「シミュレーター」に誘拐されてしまう。
Public-Coin プロトコルには、「Arthur-Merlin Game」という素敵な名前も付いています...
上の写真を見てください、左側の「白いローブ」がマーリン（魔術師マーリン）、真ん中の剣を持ったハンサムな男がアーサー王（キング・アーサー）です。この二人のキャラクターは、中世ヨーロッパの伝説に由来しています。アーサー王の円卓の騎士。
アーサーはコインを持ち歩くせっかちな王であり、マーリンは無限の計算能力を持つ魔法の魔術師です。対話にはなりますが、王は怠け者なので、一度にコインを投げるだけで、その後「挑戦」します。魔術師は時間内に応答する必要があり、k ラウンド後に王に自分の判断を信じさせる必要があります。マーリンは魔法を持っているため、アーサー王が投げたコインはすべてマーリンに見ることができます[7]。これは私たちと一緒です「シリーズ１」
で説明されている Interactive Proof System (略して IP) は似ていますが、異なります。 IP は 1985 年に Goldwasser、Micali、Rackoff (略して GMR) によって正式に提案され、その証明能力は大規模な計算複雑性問題をカバーします。違いは、IP の定義では、Prover と Verifier は両方ともコインを投げることができるチューリング マシンであり、Verifier は秘密裏にコインを投げて Prover から隠すことができるのに対し、アーサーとマーリンのゲームでは、王は A コイン トスしかできないことです。それだけでなく、マーリンはコイントスの結果を常に知っています。
しかし、フィアット・シャミア変換は「ランダムオラクルモデル」の下でのみ安全性を証明でき、ハッシュ関数を使用してランダムオラクルを実現するプロセスが安全かどうかは、セキュリティ証明に欠けています。それだけでなく、「ランダム オラクル モデル」に基づく安全なプロトコルは安全ではない可能性があり、いくつかの反例が見つかっています [8]; さらに残念なことに、S. Goldwasser と Y. Tauman は 2003 年に、Fiat-Shamir 変換には安全性があることを証明しました。それ自体の反例[9]。ただし、これは Fiat-Shamir 変換を使用できないという意味ではありませんが、使用中は十分に注意する必要があり、やみくもに適用することはできません。
それでも、非常に広く使用されているフィアット-シャミール変換の誘惑に抵抗することはできません。 Fiat-Shamir 変換は、最も注目されている汎用の非対話型ゼロ知識証明 zkSNARK のさまざまなスキームに豊富に含まれていることは言及する価値があります。たとえば、Bulletproofs (防弾) はよく知られているかもしれませんが、Hyrax、Ligero、Supersonic、Libra など、今のところあまり知られていない汎用のゼロ知識証明スキームがいくつかあります。 （順を追って説明していきます）。
注意: Fiat-Shamir 変換におけるセキュリティへの影響
Fiat-Shamir 変換では、ハッシュ関数に指定するパラメータに特に注意してください。実際のコード実装では、ハッシュ関数の一部のパラメータが省略される場合があります。
たとえば、A, Hash(A), B, Hash(B) では、2 番目のハッシュ関数にパラメーター A がありません。正しい方法は A, Hash(A), B, Hash(A,B) である必要があります。このタイプのアプローチは、重大なセキュリティの抜け穴を引き起こす可能性があります。たとえば、スイスの電子投票システム SwissPost-Scytl では、フィアット シャミア変換の実装コードが、存在するはずのパラメータを繰り返し欠落しており、攻撃者は投票用紙を無効にするだけでなく、投票用紙を無効にすることもできます。投票用紙は不正の目的を達成するために自由に偽造できます [10]。したがって、エンジニアリング実装では注意してください。
注意深い読者は Schnorr 署名を振り返ると、Schnorr 署名のハッシュ アルゴリズムがパラメーター PK を見逃しているように見えることがわかります。これは厳密な Fiat-Shamir 変換ではなく、弱い Fiat-Shamir 変換と呼ばれます [11]ただし、この特殊な場合にはセキュリティ上の問題はありません[3]ので、未成年者は勝手に真似をしないでください。
最近、一部の学者は、標準モデルに基づいてフィアット・シャミア変換の安全性を厳密に証明する方法を研究し始めており、現在、追加の強力な安全性の仮定を導入するか、特定のプロトコルに対してそれを証明するかのどちらかですが、あまり確立されていないようです。進捗。
インタラクションの力
1985年、GMRトリオの論文が何度も却下された後、STOC'85に受理されたとき、別の同様の論文も同時にSTOC'85に受理されたと言われている（ハンガリー、ローランド大学のラースロー・ババイ氏）イスラエル工科大学の Shlomo Moran によって書かれた論文「Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes」[7] では、パブリックコイン対話型プロトコル (名前が示すように、Verifier のみ) が導入されました。公にコインを投げる）。
アーサー王の手法は非常にシンプルで、マーリンの主張は繰り返しの「ランダムな」チャレンジによってテストされますが、これは前述した、信頼の「根」を構築するためにランダムなチャレンジを使用するという直観と一致しています。 Babai は論文の中で、AM[k]=AM[2] という興味深い結論を証明しました。ここで、k は相互作用の数を表し、複数の相互作用の効果は 2 つの相互作用に相当します。いわゆるインタラクション 2 回とは、アーサーがチャレンジ番号を送信し、マーリンが応答することを意味します。
注: MA に属する別のタイプの問題があります。このタイプの問題のインタラクティブな順序は AM のものとは異なります。MA では、マーリンが最初に証明を行い、次にアーサーが検査のためにコインを投げます。 MA が処理できる問題は AM のサブセットであることが証明されています。
それだけでなく、ババイ氏は大胆にも、AM[poly] は IP に相当すると推測しました。これは魔法の主張です。王は怠け者で、魔術師に挑戦するためには多項式コインを投げるだけで十分です。この方法の表現力は、GMR によって記述された対話型証明システム IP と完全に同等です。案の定、STOC'86 会議で、S. Goldwasser と M. Sipser の論文が、AM[poly] == IP[12] を証明しました。
これは、繰り返し公開される「ランダムなチャレンジ」が無限に強力であり、あらゆる対話型証明システムと同等であることを意味します。ただし、AM[poly] と他の計算複雑性クラスとの関係は、次の研究のホットスポットです。
AM[poly] == IP == PSPACE
3 年後、ちょうど 30 年前の 1989 年 11 月末に、若い暗号学者のノーム ニサンは電子メールを送信し、暫定的な学術的結論を数人の暗号学者に送り、その後休暇中の南米へ向かいました。しかし彼は、この電子メールが、M. ブルーム、S. カナン、D. リプトン、D. ビーバー、J. ファイゲンバウム、H. カーロフ、C. ルンドなどの大規模なグループとの歴史上熾烈な学術競争を引き起こすことになるとは思いもしませんでした。 . エリートたちは戦いに参加し始めました. 彼らは昼夜を問わず互いに議論し、研究結果を発表するために競争しました. 最後に、ちょうど 1 か月である 12 月 26 日に、アディ シャミールは次の結論を証明しました。
「効果的な証明」という概念の計算理論的特徴を説明し、「対話型証明システム」という概念がカバーする計算能力を説明します。
注: NP クラスは PSPACE クラスのサブセットです。前者は誰にとってもよく知られており、後者はゲームやチェスの勝利戦略に関連しています [13]。
そして、L. Babai は、「電子メールとインタラクションの予期せぬ力」 (電子メールとインタラクションの予期せぬ力) [14] という記事を書きました。この記事では、この 1 か月間を「電子メール インタラクション」で詳しく説明しています。 「インタラクティブ証明」。
パブリック参照文字列 - もう 1 つの「信頼のルート」
はい、お読みのとおり、ここにも「第三者」が存在します。第三者は証明に直接参加しませんが、ランダム文字列生成プロセスの信頼性を保証する必要があります。 CRS を生成するプロセスは「信頼できるセットアップ」とも呼ばれますが、これは誰もが好き嫌いが分かれるものです。明らかに、現実世界のシナリオにサードパーティを導入するのは頭の痛い問題になる可能性があります。 CRS は具体的に何に使用されますか? Trusted Setup の信頼はここからどこへ行くのでしょうか?この部分は、このシリーズの次の記事のために予約されています。
つづく
つづく
非インタラクティブなゼロ知識は、NIZK の "信頼のルート" にも何らかの形式のランダムな "チャレンジ" が必要であることを証明しています。" チャレンジ" の 1 つの形式は "ランダムな予言のエルフ" に渡され、ランダムな文字列を共有して達成されます。どちらの形式のチャレンジも基本的に第三者を導入し、どちらも「シミュレータ」が悪用できる「バックドア」を提供する必要があります。その結果、シミュレータは「理想的な世界」において何らかの「利点」を得ることができ、この利点は必ず必要です。 「現実世界」では失敗する。
過去30年間、先駆者たちはその微妙な結論を探求してきましたが、同時に非常に多くの未知の部分があり、インスピレーションの光を待っています。この一連の記事は Github にありますプロジェクトリポジトリ
Jingyu Hu (colortigerhu) さんから最初のプルリクエストを受け取り、少し言葉を変えただけでしたが、その瞬間に生命力を感じました。知識の交換、アイデアの衝突は興味深いですね。
「私たちが対話するすべての人は、私たちの一部になります。」 私たちが対話するすべての人は、私たちの一部になります。 ―ジョディ・アマン
文章
参考文献
[1] Schnorr, Claus-Peter. "Efficient signature generation by smart cards." Journal of cryptology 4.3 (1991): 161-174.
[2] Paillier, Pascal, and Damien Vergnaud. "Discrete-log-based signatures may not be equivalent to discrete log." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2005.
[3] Pointcheval, David, and Jacques Stern. "Security arguments for digital signatures and blind signatures." Journal of cryptology 13.3 (2000): 361-396.
[4] Maxwell, Gregory, Andrew Poelstra, Yannick Seurin, and Pieter Wuille. "Simple schnorr multi-signatures with applications to bitcoin." Designs, Codes and Cryptography 87, no. 9 (2019): 2139-2164.
[5] Fiat, Amos, and Adi Shamir. "How to prove yourself: Practical solutions to identification and signature problems." Conference on the Theory and Application of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1986.
[6] Bellare, Mihir, and Phillip Rogaway. "Random Oracles Are Practical: a Paradigm for Designing Efficient Protocols." Proc. of the 1st CCS (1995): 62-73.
[7] László Babai, and Shlomo Moran. "Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes." Journal of Computer and System Sciences 36.2 (1988): 254-276.m
[8] Canetti, Ran, Oded Goldreich, and Shai Halevi. "The random oracle methodology, revisited." Journal of the ACM (JACM)51.4 (2004): 557-594.
[9] Shafi Goldwasser, and Yael Tauman . "On the (in) security of the Fiat-Shamir paradigm." 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.. IEEE, 2003.
[10]Lewis, Sarah Jamie, Olivier Pereira, and Vanessa Teague. "Addendum to how not to prove your election outcome: The use of nonadaptive zero knowledge proofs in the ScytlSwissPost Internet voting system, and its implica tions for castasintended verifi cation." Univ. Melbourne, Parkville, Australia (2019).
[11] Bernhard, David, Olivier Pereira, and Bogdan Warinschi. "How not to prove yourself: Pitfalls of the fiat-shamir heuristic and applications to helios." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2012.
[12] Goldwasser, Shafi, and Michael Sipser. "Private coins versus public coins in interactive proof systems." Proceedings of the eighteenth annual ACM symposium on Theory of computing. ACM, 1986.
[13] Papadimitriou, Christos H. "Games against nature." Journal of Computer and System Sciences 31.2 (1985): 288-301.
[14] Babai, László. "E-mail and the unexpected power of interaction." Proceedings Fifth Annual Structure in Complexity Theory Conference. IEEE, 1990.
[15] Yi Deng. "参考文献" https://zhuanlan.zhihu.com/p/29491567
IOS
Android