読者です 読者をやめる 読者になる 読者になる

WHの定義

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が存在することも要求している.

>