識別不能のソースを表示

'''識別不能'''（しきべつふのう）

==情報論的識別不能==
{X<sub>k</sub>}<sub>k∈N</sub>、{Y<sub>k</sub>}<sub>k∈N</sub>を[[確率変数]]の[[族 (数学)|族]]とする。

あるk<sub>0</sub>があって任意のk>k<sub>0</sub>に対しX<sub>k</sub>の従う[[確率分布]]とY<sub>k</sub>の従う確率分布が同一である時、族{X<sub>k</sub>}<sub>k∈N</sub>と{Y<sub>k</sub>}<sub>k∈N</sub>は'''情報論的識別不能'''であるという。

==統計的識別不能==
A、Bを確率変数とする。
AとBとの'''統計的距離'''を∑<sub>xはkビットのビット列</sub>|Pr(A=x)-Pr(B=x)|　により定義する。
X<sub>k</sub>とY<sub>k</sub>との統計的距離がkに対して[[negligible|無視できる]]とき、
すなわち任意の多項式Pに対し、あるk<sub>0</sub>があって任意のk>k<sub>0</sub>に対し、∑<sub>xはkビットのビット列</sub>|Pr(X<sub>k</sub>=x)-Pr(Y<sub>k</sub>=x)|<1/P(k)となる時、族{X<sub>k</sub>}<sub>k∈N</sub>と{Y<sub>k</sub>}<sub>k∈N</sub>は'''統計的識別不能'''であるという。

==計算量的識別不能==

任意の[[多項式時間機械]]D （'''識別機'''(distinguisher)という）と任意の多項式Pに対し、あるk<sub>0</sub>があって任意のk>k<sub>0</sub>に対し
|Pr(D(X<sub>k</sub>)=1)-Pr(D(Y<sub>k</sub>)=1)|<1/P(k)となる時、X<sub>k</sub>とY<sub>k</sub>は'''計算量的識別不能'''であるという。


==関連項目==
* [[暗号理論]]

[[category:暗号技術|しきへつふのう]]