識別しきべつ不能ふのう

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

情報じょうほう論ろん的てき識別しきべつ不能ふのう

$\{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}$は計算けいさん量的りょうてき識別しきべつ不能ふのうであるという。

定義ていぎからわかるように、計算けいさん量的りょうてき識別しきべつ不能ふのうは、計算けいさん能力のうりょくを多項式たこうしき時間じかんに限定げんていした場合ばあいに、見分みわけることができないことを意味いみする。

例れい： 暗号あんごう理論りろんの分野ぶんやでは、多おおくの計算けいさん量的りょうてき識別しきべつ不能ふのうを仮定かていしている。例れいとして以下いかのものがある．

• 平方へいほう剰余じょうよと平方へいほう非ひ剰余じょうよ
• ディフィー・ヘルマン鍵かぎ共有きょうゆうの鍵かぎと乱数らんすう

関連かんれん項目こうもく

• 暗号あんごう理論りろん