識別不能のソースを表示

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

==情報論的識別不能==
<math>\{ X_k \}_{k\in N}, \{ Y_k \}_{k\in N}</math>を[[確率変数]]の[[族 (数学)|族]]とする。

ある<math>k_0</math>があって任意の<math> k>k_0</math>に対し<math>X_k</math>の従う[[確率分布]]と<math>Y_k</math>の従う確率分布が同一である時、族<math>\{ X_k \}_{k\in N}</math>と<math>\{ Y_k \}_{k\in N}</math>は'''情報論的識別不能'''であるという。

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

例：
* 確率変数<math> X_k </math> ：[[公正なコイン]]を<math>k</math>回ふる、という実験の結果。コインの表が出たら1、裏が出たら0、として、<math>k</math>個の0,1列で表現する。
* 確率変数<math> Y_k </math> ：公正な2つのコインを<math>k</math>回ふって、各回に同じ面が出るか、という実験の結果。2つのコインで同じ面が出たら1、異なる面が出たら0、として<math>k</math>個の0,1列で表現する。

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

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

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

例：
* 確率変数<math> X_k </math> ：公正なコインを<math>k</math>回ふる、という実験の結果。コインの表が出たら1、裏が出たら0、として、<math>k</math>個の0,1列で表現する。
* 確率変数<math> Z_k </math> ：<math> X_k </math>と同じ実験をするが、<math>k</math>回続けて裏が出たら、最初からやり直すという実験の結果。

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

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

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

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

例：
[[暗号理論]]の分野では、多くの計算量的識別不能を仮定している。例として以下のものがある．
* [[平方剰余]]と平方非剰余
* [[ディフィー・ヘルマン鍵共有]]の鍵と乱数


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

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