非対話型ゼロ知識証明
非対話型ゼロ知識証明とは
対話型ゼロ知識証明システムにおいて、証明者と検証者が参照できるランダムな文字列を新たに導入することで、相互作用を無くすことができます。すなわち、相互作用が証明者から検証者に送られるメッセージ1つだけにできるということです。このようなゼロ知識証明システムを非対話型ゼロ知識証明システムと呼びます。
ここで、使用するランダムな文字列が、一様分布から生成されたものなら共通ランダム文字列（common random string）と呼び、任意の分布から生成されたものなら共通参照文字列（common reference string; CRS）と呼びます。なので、共通参照文字列は共通ランダム文字列を一般化したものとなります。どちらも略すとCRSでややこしいですが、通常CRSと表記する場合は共通参照文字列を指します。
プロトコルの全てのパーティーがある分布から生成した文字列（すなわち共通参照文字列）を利用できるモデルのことを共通参照文字列モデルと言います。
共通参照文字列は、プロトコルのパーティーが生成することも可能ですが、生成者に悪意がある場合、証明の偽造を容易できるように共通参照文字列を構築できてしまいます。そのため、共通参照文字列は信頼できるサードパーティーが生成するか、Multi-Party Computation (MPC)で非中央集権的に生成することが多いです。
非対話型ゼロ知識証明システムを次のように定義します。
非対話型ゼロ知識証明システム
確率的マシンの組 \((P,V)\) は、 \(V\) が多項式時間で動作し、以下の完全性と健全性が成り立つなら、言語 \(\mathcal L\) の非対話型証明システムという。ここで \(\sigma\) は \(\lbrace 0,1 \rbrace ^{\operatorname{poly}(|x|)}\) に一様に分布する確率変数であり、共通参照文字列と呼ばれる。
完全性: 任意の \(x\in \mathcal L\) に対して、次の式が成り立つ。
健全性: 任意の \(x\notin \mathcal L\) と任意のアルゴリズム \(B\) に対して、次の式が成り立つ。