WHの定義 - 186 @ hatenablog

Feige-Shamirの論文とGoldreichの教科書で定義が違うことに気付いた.
ともに任意のnの多項式程度の長さのz, 任意のPPTM V^*について下記を満たすある無視できる関数 ε が存在することとなっている.
Goldreichの方だと, D_nを{0,1}^n上の分布, XをD_nに従う確率変数, YをR(X)上の任意の確率変数として,
$\Pr[\lt P(Y),V^*(z) \gt(X) \in R(X)] < \epsilon(n)$ .

Feige-Shamirの方だと, インスタンス生成器 G を用いて,
$\Pr[(x,w)\leftarrow G(1^n;R);\lt P(w),V^*(z) \gt(x) \in R(x)] < \epsilon(n)$ .

Feige-Shamirの方だと, インスタンス生成器 G を想定する. あるwitness extractor Mが存在して,
$\Pr[(x,w)\leftarrow G(1^n;R);\lt P(w),V^*\gt(x) \in R(x)] < \Pr[(x,w)\leftarrow G(1^n;R);M^{V^*,G}(x) \in R(x)] + \epsilon(n)$ .

Goldreichの方はいかにも基礎的な分野をやっている人の定義. Feige-Shamirの方はいかにも暗号的な要請に合わせた定義だ. 効率的なGが存在することも要求している.