アーギュメント
アーギュメントとは
対話型証明システムにおいて、健全性の定義は統計的なもの、すなわち統計的健全性でした。その統計的健全性を緩和して計算量的健全性に置き換えたものをアーギュメント（argument）と呼びます。アーギュメントは、計算量的健全証明（computationally sound proof）とも呼ばれます。この資料では様々な文献と同様に、アーギュメントシステムの文脈で「証明」と書いてある場合、暗にアーギュメントを指していることがあります。
アーギュメントを考える嬉しさの一つは、対話型証明システムの健全性を緩和することで、任意のNPの言語に対してパーフェクトゼロ知識性を持つ、より広い意味での対話型証明システムを構築できることです。前に述べたように、任意のNPの言語に対してパーフェクトゼロ知識証明システムは構築できる可能性が低いため、アーギュメントシステムは非常に有用です。
また、単に証明者の能力が制限されることで、安全性を満たすために必要だった時間計算量や通信量が削減できるため、現実のシステムではアーギュメントシステムがよく利用されます。
形式的にはアーギュメントシステムを次のように定義します。
アーギュメントシステム
多項式時間対話型マシンの組 \((P,V)\) は、以下の完全性と計算量的健全性を満たすならば、言語 \(\mathcal{L}\) のアーギュメントシステムであるという。
完全性: 任意の文字列 \(w \in \mathcal{L}\) に対して、次の式が成り立つ。
計算量的健全性: 任意の文字列 \(w \in \mathcal{L}\) と任意の多項式時間対話型マシン \(P^*\) に対して、次の式が成り立つ。
計算量的ゼロ知識証明とパーフェクトゼロ知識アーギュメントのトレードオフ
計算量的ゼロ知識証明とパーフェクトゼロ知識アーギュメントの間には、健全性とゼロ知識性のどちらを優先するかというトレードオフがあります。
自分のアプリケーションにどちらのゼロ知識証明システムを採用するかは、そのアプリケーションの目的次第です。例えば、とてつもない計算資源を有するパーティーが存在して、そのパーティーによる証明の偽造を危惧するのであれば、健全性を重視したほうが良いでしょう。
また一方で、将来的に証明から一つの知識も流出したくないのであれば、パーフェクトゼロ知識性を重視したほうが良いでしょう。特にTornado Cashのような匿名化アプリケーションであれば、ユーザーは匿名化を最も重視していると予想できるので、将来強力な計算機が登場したとき計算量的ゼロ知識性のせいで匿名化が暴かれてしまうことがないように、パーフェクトゼロ知識アーギュメントを選択すべきでしょう。実際、Groth16はパーフェクトゼロ知識アーギュメントです。
パーフェクト秘匿コミットメントスキーム
パーフェクトゼロ知識アーギュメントを構築するためには、パーフェクト秘匿コミットメントスキームが必要です。パーフェクト秘匿コミットメントスキームとは、前に定義したコミットメントスキームにおいて、計算量的な秘匿性をパーフェクトな定義にし、パーフェクトな束縛性を計算量的な定義に変えたものです。パーフェクトゼロ知識アーギュメントにおいて、証明者の計算能力に制限を加えて計算量的な健全性を考えるのだから、束縛性も計算量的にしても問題ないということです。
パーフェクト秘匿コミットメントスキームの構成の例として一方向性置換を用いた構成を紹介します。
パーフェクト秘匿ビットコミットメントスキームの構成例
\(f\) を一方向性置換とし、 \(b(x,y)\) を \(x\) と \(y\) の内積を \(2\) で割った余りとする。ただし、バイナリ列をベクトルとして捉えて関数 \(b\) の入力とできるものとする。つまり、入力にバイナリ列を使用するとき、 \(b(x,y)\) は形式的には \(x=(x_1,x_2,\cdots,x_n) \in \lbrace 0,1 \rbrace ^n,\ y=(y_1,y_2,\cdots,y_n) \in \lbrace 0,1 \rbrace ^n\) として、次の式で表される。
確率的多項式時間対話型マシンの組 \((S,R)\) であり、以下で定義するコミットフェーズとオープンフェーズの2段階に分かれている2者間プロトコルはパーフェクト秘匿ビットコミットメントスキームである。
コミットフェーズ
- ローカルでの準備:
- 受信者は、 \(n-1\) 個の線形独立なベクトル \(r^1,\ldots,r^{n-1} \in \lbrace 0,1\rbrace^n\) をランダムに選びます。ここでの \(r^i\) の添字は \(i\) 番目のベクトルということを表している。
- 送信者は、ランダムに \(s \in \lbrace 0,1 \rbrace^n\) を選び、 \(y=f(s)\) を計算する。
- 対話での準備:
- \(n-1\) 回の対話を行う。 \(i\) 回目において、受信者は \(r^i\) を送信者に送る。送信者はそれを受けて、 \(c^i \coloneqq b(y,r^i)\) を計算して送る。
- \(n-1\) 回目の対話が終わった後、連立方程式 \(\lbrace b(y,r^i) - c^i \rbrace_i\) の解は2つ存在する（未知数が \(n\) 個あり、 \(n-1\) 個の式があり、ベクトル \(r^i\) は線形独立であるため）。この2つの解をそれぞれ \(y^1,y^2\) とする。このとき、辞書順で最初であるほうを \(y^1\) とする。送信者は \(y\) が \(y^1\) であれば、 \(\pi=1\) とし、そうでなければ \(\pi=0\) とする。
- コミット:
- 送信者は、受信者に値 \(v\in \lbrace 0,1 \rbrace\) をコミットするために、 \(c^n \coloneqq \pi \oplus v\) を送る。
オープンフェーズ
- 送信者は \((v,s)\) を公開する。
- 受信者は \(\pi\) を求めた後、次の2つの条件が成立する場合にのみ値 \(v\) を受け入れる。
- 全ての \(1 \le i \le n-1\) に対して \(b(f(s),r^i)=c^i\) が成り立つこと。
- \(v = c^n \oplus \pi\) が成り立つこと。
このパーフェクト秘匿ビットコミットメントスキームは、パーフェクト秘匿性と計算量的束縛性を満たします。証明は割愛しますが、これら性質に関して簡単に確認します。
パーフェクト秘匿性: \(n-1\) 回の対話が終わった時点で、受信者は \(y^1,y^2\) を求めることができます。しかし、受信者は1回の対話で1ビットの情報を得ることしか出来ないので、 \(n-1\) 回対話しても最大 \(n-1\) ビットの情報しか得られず、情報理論的にどちらであるかを確定できません。受信者はせいぜい \(O(2^n)\) の時間計算量で \(y^1 = f(s^1),y^2=f(s^2)\) を満たすような \(s^1,s^2\) を見つけられるだけで、どちらの確率も \(\frac{1}{2}\) ずつです。
計算量的束縛性: 送信者は明らかに \(O(2^n)\) の時間計算量で、もう一つの解を \(y'\) として、 \(y'=f(s')\) となるような \(s'\) を計算でき、任意の値でオープンできます。そのため、前に定義したビットコミットメントスキームとは異なり、パーフェクト束縛性は満たさなくなっています。この時間計算量が多項式時間に落ちると、計算量的束縛性を満たさなくなってしまいますが、落とすことが不可能であることを証明できます。
パーフェクトゼロ知識アーギュメントの構築
「NPに対するゼロ知識証明」で構築したグラフ三彩色の計算量的ゼロ知識証明システムにおいて、利用したコミットメントスキームをパーフェクト秘匿コミットメントスキームに置き換えるだけで、グラフ三彩色のパーフェクトゼロ知識アーギュメントシステムを構築できます。
束縛性が計算量的になっているため、悪意ある送信者は時間計算量 \(O(2^n)\) で常に異なる色をオープンできます。そのため、証明者がグラフの三彩色を知っていなかったり、そもそもグラフが三彩色不可能であったりする場合でも、計算量に制限がない送信者はグラフが三彩色可能であると検証者に納得させることができます。