識別不能
識別不能(しきべつふのう)とは、二つの確率変数を見分けることができないことを意味する。ただ、これらを「見分けようとする人」がどのようにして見分けるのか、どれだけの能力を持っているかによって、見分けられるか・見分けられないかは異なる。そのため、想定する「見分けるために使う能力」により、三つの定義がある。
情報論的識別不能
編集ある があって任意の に対し の従う確率分布と の従う確率分布が同一である時、族 と は情報論的識別不能であるという。
二つの確率変数(の確率分布)が同一であれば、どんなに計算能力があろうとも見分けることができない。つまり、情報論的識別不能は、「どんなに計算能力があろうとも」見分けることができないことを意味する。
例:
- 確率変数 :公正なコインを 回ふる、という実験の結果。コインの表が出たら1、裏が出たら0、として、 個の0,1列で表現する。
- 確率変数 :公正な2つのコインを 回ふって、各回に同じ面が出るか、という実験の結果。2つのコインで同じ面が出たら1、異なる面が出たら0、として 個の0,1列で表現する。
と は異なる実験によって得られる確率変数であるが、共に、任意の ビット列が確率 で生じる。よって、 と は情報論的識別不能である。
統計的識別不能
編集、 を確率変数とする。 と との統計的距離を により定義する。 と との統計的距離が、 に対して無視できるとき、 すなわち任意の多項式 に対し、ある があって任意の に対し、 となる時、族 と は統計的識別不能であるという。
二つの確率変数を見分けたい人が、いずれかの確率変数(の確率分布)によって選ばれた値を次々に観測し続けて、見分けることを考えよう。二つの確率分布が大きく異なる場合、観測値の頻度分布を求めることで、どちらの確率分布であるのかを見分けることができるだろう。逆に、確率分布がほとんど同じ場合、多くの値を観測したとしても見分けはつきにくい。統計的識別不可能は、多項式個の値を観測しても見分けがつかないことを意味する。
例:
- 確率変数 :公正なコインを 回ふる、という実験の結果。コインの表が出たら1、裏が出たら0、として、 個の0,1列で表現する。
- 確率変数 : と同じ実験をするが、 回続けて裏が出たら、最初からやり直すという実験の結果。
では、0が 個並んだものは生じず( )、それ以外の ビット列が確率 で生じる。よって、 と の統計的距離は である。 よって、 と は統計的識別不能である。
計算量的識別不能
編集任意の多項式時間機械 (識別機(distinguisher)という)と任意の多項式 に対し、ある があって任意の に対し となる時、 と は計算量的識別不能であるという。
定義からわかるように、計算量的識別不能は、計算能力を多項式時間に限定した場合に、見分けることができないことを意味する。
例: 暗号理論の分野では、多くの計算量的識別不能を仮定している。例として以下のものがある.
- 平方剰余と平方非剰余
- ディフィー・ヘルマン鍵共有の鍵と乱数