知識の証明

暗号学における知識の証明とは、証明者が検証者に対して自分が何かを知っていることを「納得させる」ことに成功する対話型の証明である。機械が「何かを知っている」とは、計算の観点から定義される。機械が「何かを知っている」とは、機械に入力を与えてその何かを計算できる場合である。証明者のプログラムは必ずしも知識そのものを吐き出すとは限らないため（ゼロ知識証明^{[1]の場合のように）、この考え方を捉えるために、知識抽出器と呼ばれる異なるプログラムを持つ機械が導入されている。我々は主に、}多項式時間制限のある機械によって何が証明できるかに興味がある。この場合、知識要素の集合は、 NPにおける何らかの言語の証人の集合に限定される。

NP の言語のステートメントを とし、証明で受け入れられるべき x の証拠の集合を とします。これにより、次の関係を定義できます。 ${\displaystyle x}$${\displaystyle L}$${\displaystyle W(x)}$${\displaystyle R=\{(x,w):x\in L,w\in W(x)\}}$

知識エラーとの関係に関する知識の証明は、次の 2 つの特性を持つ 証明者と検証者による 2 者間プロトコルです。${\displaystyle R}$${\displaystyle \kappa}$${\displaystyle P}$${\displaystyle V}$

1. 完全性: の場合、 の証人を知っている証明者は、検証者に自分の知識を納得させることに成功します。より正式には、 、つまり、証明者 P と検証者 V の相互作用が与えられた場合、検証者が納得する確率は 1 です。${\displaystyle (x,w)\in R}$${\displaystyle P}$${\displaystyle w}$${\displaystyle x}$${\displaystyle V}$${\displaystyle \Pr(P(x,w)\leftrightarrow V(x)\rightarrow 1)=1}$
2. 有効性: 有効性では、悪意のある可能性のある証明者へのオラクル アクセスを与えられた場合に、知識抽出者が証人を抽出する成功確率が、証明者が検証者を説得する成功確率と少なくとも同じくらい高くなければなりません。このプロパティにより、証人を知らない証明者は検証者を説得できないことが保証されます。${\displaystyle E}$${\displaystyle {\tilde {P}}}$${\displaystyle {\tilde {P}}}$

これは妥当性のより厳密な定義である: ^[2]

を証人関係、公開値 のすべての証人の集合、および知識エラーとします。知識の証明は、へのオラクルアクセスが与えられた多項式時間マシンが存在し、任意の に対して、かつ が成り立つ場合、 -妥当です。${\displaystyle R}$${\displaystyle W(x)}$${\displaystyle x}$${\displaystyle \kappa}$${\displaystyle \kappa}$${\displaystyle E}$${\displaystyle {\tilde {P}}}$${\displaystyle {\tilde {P}}}$${\displaystyle E^{{\tilde {P}}(x)}(x)\in W(x)\cup \{\bot \}}$${\displaystyle \Pr(E^{{\tilde {P}}(x)}(x)\in W(x))\geq \Pr({\tilde {P}}(x)\leftrightarrow V(x)\rightarrow 1)-\kappa (x).}$

この結果は、チューリングマシンが結論に達しなかったことを意味します。 ${\displaystyle \bot}$${\displaystyle E}$

知識エラーは、証明者が実際には証人を知らないにもかかわらず、検証者が を受け入れる可能性を表します。知識抽出器は、チューリングマシンの知識が意味するものを表現するために使用されます。が から を抽出できる場合、は の値を知っていると言えます。 ${\displaystyle \kappa (x)}$${\displaystyle V}$${\displaystyle x}$${\displaystyle w}$${\displaystyle E}$${\displaystyle E}$${\displaystyle w}$${\displaystyle {\tilde {P}}}$${\displaystyle {\tilde {P}}}$${\displaystyle w}$

この妥当性の定義は、妥当性と強い妥当性を組み合わせたものです。^[2]例えばやなどの小さな知識エラーの場合、それは通常の対話型証明の健全性よりも強いと見なすことができます。 ${\displaystyle \kappa (x)}$${\displaystyle 2^{-80}}$${\displaystyle 1/\mathrm {poly} (|x|)}$

特定の知識の証明を定義するには、言語を定義するだけでなく、検証者が知っておくべき証拠も定義する必要があります。言語のメンバーシップを証明するのは簡単な場合もありますが、特定の証拠を計算するのは難しい場合があります。これは、例を使用して説明するのが最も適切です。

を生成元を持つ巡回群とし、その中で離散対数問題を解くことは困難であると考えられています。言語のメンバーシップを決定することは、すべてのが に含まれるため簡単です。ただし、 が成り立つような証拠を見つけることは、離散対数問題を解くことに対応します。 ${\displaystyle \langle g\rangle }$${\displaystyle g}$${\displaystyle L=\{x\mid g^{w}=x\}}$${\displaystyle x}$${\displaystyle \langle g\rangle }$${\displaystyle w}$${\displaystyle g^{w}=x}$

最も単純で頻繁に使用される知識証明の1つである離散対数の知識証明は、シュノアによるものです。^[3]このプロトコルは、生成元を持つ順序の巡回群 に対して定義されます。 ${\displaystyle G_{q}}$${\displaystyle q}$${\displaystyle g}$

の知識を証明するために、証明者は検証者と次のように対話します。 ${\displaystyle x=\log_{g}y}$

1. 最初のラウンドでは、証明者はランダム性にコミットします。そのため、最初のメッセージはコミットメントとも呼ばれます。${\displaystyle r}$${\displaystyle t=g^{r}}$
2. 検証者はランダムに選択されたチャレンジ で応答します。${\displaystyle c}$
3. を受け取った後、証明者はグループの順序を法として縮小された3 番目で最後のメッセージ (応答)を送信します。${\displaystyle c}$${\displaystyle s=r+cx}$

検証者は、次の場合に受け入れます。 ${\displaystyle g^{s}=ty^{c}}$

次のように動作する抽出器があるため、これが有効な知識証明であることがわかります。

1. 証明器をシミュレートして を出力します。証明器は現在状態 にあります。${\displaystyle t=g^{r}}$${\displaystyle Q}$
2. ランダムな値を生成し、証明器に入力します。出力は です。${\displaystyle c_{1}}$${\displaystyle s_{1}=r+c_{1}x}$
3. 証明器を の状態に戻します。次に、異なるランダム値を生成し、それを証明器に入力して を取得します。${\displaystyle Q}$${\displaystyle c_{2}}$${\displaystyle s_{2}=r+c_{2}x}$
4. 出力.${\displaystyle (s_{1}-s_{2})(c_{1}-c_{2})^{-1}}$

なので、抽出器の出力は正確に になります。 ${\displaystyle (s_{1}-s_{2})=(r+c_{1}x)-(r+c_{2}x)=x(c_{1}-c_{2})}$${\displaystyle x}$

このプロトコルはゼロ知識ですが、その特性は知識の証明に必須ではありません。

上記の 3 つの動作構造 (コミットメント、チャレンジ、レスポンス) を持つプロトコルは、シグマ プロトコルと呼ばれます。^[4] この名前は、プロトコルの 3 つの動作を象徴するジグザグを指す Sig と、「Merlin-Arthur」の略語である MA に由来しています。^[5]シグマ プロトコルは、離散対数に関連するものなど、さまざまなステートメントを証明するために存在します。これらの証明を使用して、証明者は離散対数の知識を証明できるだけでなく、離散対数が特定の形式であることを証明することもできます。たとえば、およびを底とする との2 つの対数が等しいか、他の何らかの線形関係を満たすことを証明できます。のa 元とb元について、証明者はおよびについての知識を証明し、 および を満たすと言います。等式は、 a  = 1 かつb  = 0の特殊なケースに対応します。これから簡単に計算できることは、となるxに関する知識を証明することと同等です。 ${\displaystyle y_{1}}$${\displaystyle y_{2}}$${\displaystyle g_{1}}$${\displaystyle g_{2}}$ ${\displaystyle Z_{q}}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle y_{1}=g_{1}^{x_{1}}\land y_{2}=g_{2}^{x_{2}}}$${\displaystyle x_{2}=ax_{1}+b}$${\displaystyle x_{2}}$${\displaystyle x_{1}}$${\displaystyle y_{1}=g_{1}^{x}\land y_{2}={(g_{2}^{a})}^{x}g_{2}^{b}}$

これは、知識の証明によって正確に何が証明されるかを表現するために一般的に使用される 次の表記法^[6]の背後にある直感です。

${\displaystyle PK\{(x):y_{1}=g_{1}^{x}\land y_{2}={(g_{2}^{a})}^{x}g_{2}^{b}\},}$

証明者は上記の関係を満たす x を知っていると述べています。

知識の証明は、識別プロトコルの構築、および非対話型の署名スキームの構築に役立つツールです。このようなスキームは次のとおりです。

• シュノア署名

グループ署名や匿名デジタル認証システムの構築にも使用されます。

• 暗号化プロトコル
• ゼロ知識証明
• インタラクティブ証明システム
• 暗号に関するトピック
• ゼロ知識パスワード証明
• 健全性（インタラクティブな証明）