識別不能

識別不能（しきべつふのう）とは、二つの確率変数を見分けることができないことを意味する。ただ、これらを「見分けようとする人」がどのようにして見分けるのか、どれだけの能力を持っているかによって、見分けられるか・見分けられないかは異なる。そのため、想定する「見分けるために使う能力」により、三つの定義がある。

情報論的識別不能

$\{X_{k}\}_{k\in N},\{Y_{k}\}_{k\in N}$を確率変数の族とする。

ある$k_{0}$があって任意の$k>k_{0}$に対し$X_{k}$の従う確率分布と$Y_{k}$の従う確率分布が同一である時、族$\{X_{k}\}_{k\in N}$と$\{Y_{k}\}_{k\in N}$は情報論的識別不能であるという。

二つの確率変数（の確率分布）が同一であれば、どんなに計算能力があろうとも見分けることができない。つまり、情報論的識別不能は、「どんなに計算能力があろうとも」見分けることができないことを意味する。

例：

• 確率変数$X_{k}$ ：公正なコインを$k$回ふる、という実験の結果。コインの表が出たら1、裏が出たら0、として、$k$個の0,1列で表現する。
• 確率変数$Y_{k}$ ：公正な2つのコインを$k$回ふって、各回に同じ面が出るか、という実験の結果。2つのコインで同じ面が出たら1、異なる面が出たら0、として$k$個の0,1列で表現する。

$X_{k}$と$Y_{k}$は異なる実験によって得られる確率変数であるが、共に、任意の$k$ビット列が確率$1/2^{k}$で生じる。よって、$X=\{X_{k}\}_{k}$と$Y=\{Y_{k}\}_{k}$は情報論的識別不能である。

統計的識別不能

$A$、$B$を確率変数とする。 $A$と$B$との統計的距離を$\sum _{x\in \{0,1\}^{k}}|Pr(A=x)-Pr(B=x)|$　により定義する。 $X_{k}$と$Y_{k}$との統計的距離が、$k$に対して無視できるとき、 すなわち任意の多項式$P$に対し、ある$k_{0}$があって任意の$k>k_{0}$に対し、$\sum _{x\in \{0,1\}^{k}}|Pr(X_{k}=x)-Pr(Y_{k}=x)|<1/P(k)$となる時、族$\{X_{k}\}_{k\in N}$と$\{Y_{k}\}_{k\in N}$は統計的識別不能であるという。

二つの確率変数を見分けたい人が、いずれかの確率変数（の確率分布）によって選ばれた値を次々に観測し続けて、見分けることを考えよう。二つの確率分布が大きく異なる場合、観測値の頻度分布を求めることで、どちらの確率分布であるのかを見分けることができるだろう。逆に、確率分布がほとんど同じ場合、多くの値を観測したとしても見分けはつきにくい。統計的識別不可能は、多項式個の値を観測しても見分けがつかないことを意味する。

例：

• 確率変数$X_{k}$ ：公正なコインを$k$回ふる、という実験の結果。コインの表が出たら1、裏が出たら0、として、$k$個の0,1列で表現する。
• 確率変数$Z_{k}$ ：$X_{k}$と同じ実験をするが、$k$回続けて裏が出たら、最初からやり直すという実験の結果。

$Z_{k}$では、0が$k$個並んだものは生じず（$Pr[Z_{k}=0000...0]=0$）、それ以外の$k$ビット列が確率$1/(2^{k}-1)$で生じる。よって、$X_{k}$と$Y_{k}$の統計的距離は$(2^{k}-1)\times |1/2^{k}-1/(2^{k}-1)|+|1/2^{k}-0|=1/2^{k-1}$である。 よって、$X=\{X_{k}\}_{k}$と$Z=\{Z_{k}\}_{k}$は統計的識別不能である。

計算量的識別不能

任意の多項式時間機械$D$ （識別機(distinguisher)という）と任意の多項式$P$に対し、ある$k_{0}$があって任意の$k>k_{0}$に対し $|Pr(D(X_{k})=1)-Pr(D(Y_{k})=1)|<1/P(k)$となる時、$\{X_{k}\}_{k\in N}$と$\{Y_{k}\}_{k\in N}$は計算量的識別不能であるという。

定義からわかるように、計算量的識別不能は、計算能力を多項式時間に限定した場合に、見分けることができないことを意味する。

例： 暗号理論の分野では、多くの計算量的識別不能を仮定している。例として以下のものがある．

• 平方剰余と平方非剰余
• ディフィー・ヘルマン鍵共有の鍵と乱数

関連項目

• 暗号理論