Indistinguishable

不可区分的，描述的对象是某两个分布之间的关系。

注意到对确定的值是不存在是否可区分的问题的。为了解释清楚这个概念，我们引入一个特殊的算法，称为区分器（distinguisher D），它的目标是区分给定的两个分布 $U, V$。为了描述区分的效果，我们引入一个区分实验（experiment E）。

在这个实验 $E$ 中，我们假设区分器是被测试的一方，它能得知的信息是两个公开的随机算法 $U$，$V$（我们认为分布和随机算法的可能输出是等价的）。对于一个输入 $x$，我们（即测试方，Challenger C）随机地选择一个算法然后计算出一个确定的输出值 $y$，并将 $(x, y)$ 发送给 D，让 D 来猜这是哪一个算法对应的输出。

对于 D 猜测的结果的判定，我们也定义一个变量，称为 D 在这个实验中的优势（advantage），这个变量的值就等于 D 猜对的概率（即区分成功的概率）减去 $\frac{1}{2}$（这是因为即使 D 没有任何计算能力它都能以 $\frac{1}{2}$ 的概率瞎猜成功）即：

$$Adv_D^E = |Pr[\mbox{D guess right}] - \frac{1}{2}|$$

按照区分器的计算能力和区分的结果，可以将两个分布之间的关系分为以下三类：

• perfectly indistinguishable 是指即使 D 具有无限的计算能力，也不能区分出 $U$ 和 $V$（即 $Adv_D^E = 0$），此时将两个分布之间的关系记为：

  $$U \simeq ^p V$$

• statistically indistinguishable 是指即使 D 具有无限的计算能力，它也很难区分 $U$ 和 $V$（即 $Adv_D^E \le negl(|x|)$），此时将两个分布之间的关系记为：

  $$U \simeq ^s V$$

• computationally indistinguishable 是指对于任何多项式运行时间的 D，它很难区分 $U$ 和 $V$（即 $Adv_D^E \le negl(|x|)$，虽然这时 $U$ 和 $V$ 可能是完全不一样的），此时将两个分布之间的关系记为：

  $$U \simeq ^c V$$

—- Note on Commitment Schemes and Zero-Knowledge Protocols by Damgard et al. p4-5. pdf: https://users-cs.au.dk/~ivan/ComZK08.pdf