識別不可能（識別不能）とは、2つの入力値を与えた確率的アルゴリズムが出力する結果から、どの出力がどの入力に対応するのか見分けることができないことです。
識別不可能性
関数 $f$ が確率的アルゴリズム（与えられた入力に対してアルゴリズムを実行した結果が確率的に変化するアルゴリズム）のとき、その出力は確率分布となります。 識別不可能性とは、2つの異なる値 $x, x'$ (ただし、$x \ne x'$) を入力し、2つの $f$ の出力の確率分布 $f(x), f(x')$ を見分けることの困難さを定義するものです。 もし、2つの確率分布を見分けることができないのであれば、その入力が $x$ だったのか $x'$ であったのか見分けがつかないということです。 その場合は、$f$ の出力は、入力の秘匿性を守っていることになります。
識別不可能性は、2つの確率分布を識別しようとする攻撃者の性質に基づいて、以下に分類されます。
- 情報論的識別不可能性（一切区別できない）
- 計算量的識別不可能性（効率的には区別できない）
情報論的識別不可能性
2つの確率分布が一切区別できないことを情報論的識別不可能性といいます。
任意の $n \in \mathbb{N}$ について、確率変数 $X_k, X'_k$ の定義域を $\lbrace 0,1 \rbrace^n$ とし、$X_k, X'_n$ はそれぞれ確率分布 $d_n, d'_n$ に従うとします。 このとき、任意の $n \in \mathbb{N}$ と $x \in \lbrace 0,1 \rbrace^n$ において、以下の式が成り立つとき（確率分布が同一であるとき）情報理論的識別不可能であるといいます。
\[\Pr_{X_n \sim d_n} \left( X_n = x \right) - \Pr_{X'_n \sim d'_n} \left( X'_n = x \right) = 0\]※補足：確率分布 $d$ に従う確率変数を $X$ とし、これを $X \sim d$ と書くことにします。 そのため、確率変数 $X$ の値が $x$ となる確率は \(\Pr_{X \sim d} (X = x)\) と書きます。
計算量的識別不可能性
2つの確率分布が効率的には区別できないことを計算量的識別不可能性といいます。
まず、あるサンプル $x$ が確率分布 $d$ から生成されたのか確率分布 $d'$ から生成されたのかを識別する以下のような確率的多項式アルゴリズムを定義します。
\[\mathcal{A}(x) = \begin{cases} 1 &\text{if } x \text{ が } d \text{ から生成されたと判断} \\ 0 &\text{otherwise } \end{cases}\]任意の $n \in \mathbb{N}$ について、確率変数 $X_k, X'_k$ の定義域を $\lbrace 0,1 \rbrace^n$ とし、$X_k, X'_n$ はそれぞれ確率分布 $d_n, d'_n$ に従うとします。 このとき、任意の $n \in \mathbb{N}$ と 任意の $x \in \lbrace 0,1 \rbrace^n$ において、全ての確率的多項式時間アルゴリズム $\mathcal{A}$ について、以下の式が成り立つとき（正しく当てることができる確率が無視できるほど小さい時）、確率分布 $d_n, d'_n$ は計算量的識別不可能であるといいます。
\[\bigg\lvert \Pr_{X_n \sim d_n } \left( \mathcal{A}(x) = 1, X_n = x \right) - \Pr_{X'_n \sim d'_n} \left( \mathcal{A}(x) = 1, X'_n = x \right) \bigg\rvert \lt \mathrm{negl}(n)\]※補足：$\mathrm{negl}(n)$ は暗号でよく使われる関数で、無視できる (negligible) という意味です。
以上です。