【基本思想】
计算不可区分性（Computational Indistinguishability）是定义伪随机性的基础，它刻画的不是两个对象在数学上是否完全相同，而是任何高效算法能否发现它们之间的差异。
其基本思想是：如果不存在任何高效算法能够区分两个对象，那么对于一切能够由高效算法描述的实际用途，可以将这两个对象视为等价。
在计算复杂性理论中，通常不研究两个孤立的对象，而是研究由安全参数索引的无限对象序列。考虑两个字符串序列 $\{x_n\}_{n\in\mathbb N}$ 和 $\{y_n\}_{n\in\mathbb N}$，如果不存在任何高效算法能够区分这两个序列，就称它们是计算不可区分的。
设 $D$ 是一个高效算法，对于确定性的字符串序列，当 $n$ 足够大时，如果总有：
那么算法 $D$ 无法区分对应的 $x_n$ 和 $y_n$。其中，$D$ 可以理解为一个区分器（Distinguisher），它接收一个对象作为输入，并通过输出 $1$ 或 $0$ 来尝试判断输入来自哪一个序列。
在密码学中，需要处理的对象通常具有随机性，因此计算不可区分性主要针对概率分布序列进行定义。
【概率系综】
基本定义
在概率环境中，计算不可区分性比较的不是两个固定字符串，而是两个概率分布产生的随机样本。
对于一个高效算法 $D$，分别考虑：
- $D$ 接收从第一个分布采样的字符串时输出 $1$ 的概率
- $D$ 接收从第二个分布采样的字符串时输出 $1$ 的概率
如果这两个概率非常接近，那么就认为算法 $D$ 无法区分这两个分布。但是，计算不可区分性通常不是针对两个固定分布定义的，而是针对两个无限的分布序列定义的，这种分布序列称为概率系综（Probability Ensemble）。
设 $I$ 是一个可数的索引集合，如果 $X=\{X_i\}_{i\in I}$ 中的每一个 $X_i$ 都是一个随机变量，那么称 $X$ 是一个由 $I$ 索引的概率系综。
也就是说，概率系综不是单个随机变量，而是一组由索引参数确定的随机变量。
索引形式
在密码学中，常用的索引集合主要有两类：
- 自然数集合 $\mathbb N$
- 字符串集合 $\{0,1\}^{*}$ 的某个子集
由此，概率系综可分为由自然数索引的概率系综与由字符串索引的概率系综。
对于 $X=\{X_n\}_{n\in\mathbb N}$，通常每个随机变量 $X_n$ 的取值是长度为 $\operatorname{poly}(n)$ 的字符串，即：
则 $X$ 称为由自然数 $n$ 索引的概率系综。其中，$n$ 是安全参数（Security Parameter）。
对于 $X=\{X_w\}_{w\in\{0,1\}^{*}}$，通常每个 $X_w$ 的取值是长度为 $\operatorname{poly}(|w|)$ 的字符串，即：
则 $X$ 称为由字符串索引的概率系综。
这两种形式可以通过自然数的一元表示统一起来，即把自然数 $n$ 表示为由 $n$ 个 $1$ 组成的字符串 $1^n$。
【多项式时间不可区分性】
自然数索引形式
设两个由自然数 $n$ 索引的概率系综分别为 $X\overset{\mathrm{def}}{=}\{X_n\}_{n\in\mathbb N}$ 和 $Y\overset{\mathrm{def}}{=}\{Y_n\}_{n\in\mathbb N}$，如果对于任意概率多项式时间算法 $D$、任意正多项式 $\mathrm{poly}(\cdot)$，以及所有充分大的 $n$，都有：
则称概率系综 $X$ 和 $Y$ 是多项式时间不可区分的（Polynomial-Time Indistinguishable），也通常直接称为计算不可区分性。记为：
其中，符号 $\approx_c$ 表示计算不可区分。
字符串索引形式
设 $S$ 是一个字符串集合，两个由字符串索引的概率系综分别为 $X\overset{\mathrm{def}}{=}\{X_w\}_{w\in S}$ 和 $Y\overset{\mathrm{def}}{=}\{Y_w\}_{w\in S}$，如果对于任意概率多项式时间算法 $D$、任意正多项式 $\mathrm{poly}(\cdot)$，以及所有长度充分大的 $w\in S$，都有：
那么称 $X$ 和 $Y$ 是多项式时间不可区分的。
【区分器与辅助输入】
区分器
算法 $D$ 通常称为区分器（Distinguisher），它接收两个输入 $D(X_n,1^n)$，并输出一个比特。其中：
- $X_n$ 是待判断的样本
- $1^n$ 是安全参数 $n$ 的一元表示
可以约定：
- 输出 $1$：区分器倾向于认为样本来自概率系综 $X$
- 输出 $0$：区分器倾向于认为样本来自概率系综 $Y$
区分器不一定能够对每个样本作出正确判断，因此，不能只根据它对某个样本的一次输出判断其是否具有区分能力，而应比较它在两个概率系综上的整体接受概率。
辅助输入
在自然数索引形式的定义中，区分器接收两个输入 $D(X_n,1^n)$，其中：
- $X_n$ 是待判断的样本
- $1^n$ 是安全参数 $n$ 的一元表示
向区分器提供 $1^n$，主要是为了使自然数索引形式与字符串索引形式保持一致。由于 $1^n$ 的长度恰好为 $n$，区分器的多项式运行时间可以直接以 $n$ 为标准进行度量。
在通常情况下，随机变量 $X_n$ 的输出长度与安全参数 $n$ 之间是多项式相关的，即：
此外，二者通常能够在多项式时间内相互确定。
因此，在这些情况下，额外提供 $1^n$ 实际上是多余的。所以，通常省略该辅助输入，直接写为 $D(X_n)$，并默认可以从 $X_n$ 中高效确定安全参数 $n$。
【接受概率与区分优势】
接受概率
对于每个固定字符串 $\alpha\in\{0,1\}^{*}$，定义：
由于 $D$ 是概率算法，所以即使输入相同，它在不同运行中也可能输出不同结果。因此，概率来自区分器 $D$ 内部的随机性。
当输入不是固定字符串，而是随机变量 $X_n$ 时，需要进一步对 $X_n$ 的所有可能取值取平均。定义：
其中：
- $d_X(n)$ 表示区分器接收来自 $X_n$ 的随机样本时输出 $1$ 的平均概率
- $d_Y(n)$ 表示区分器接收来自 $Y_n$ 的随机样本时输出 $1$ 的平均概率
这两个期望分别等价于：
因此，定义中的概率同时包含两部分随机性：
- 随机变量 $X_n$ 或 $Y_n$ 在生成样本时的随机性
- 区分器 $D$ 在运行过程中使用的内部随机性
区分优势
给定区分器 $D$，它对概率系综 $X$ 和 $Y$ 的区分优势（Distinguishing Advantage）定义为：
利用前面的期望表示，也可以写成：
区分优势衡量的是：区分器在两个概率系综上的接受概率相差多大。
- 如果区分优势较大，说明区分器能够利用样本中的某些特征区分 $X_n$ 和 $Y_n$
- 如果区分优势是可忽略的，说明区分器无法有效区分二者
因此，概率系综 $X$ 和 $Y$ 计算不可区分的核心要求是：对于任意概率多项式时间区分器 $D$，其区分优势 $\delta(n)$ 都是关于安全参数 $n$ 的可忽略函数。
【实例】
随机输出的区分器
考虑算法 $D_1$，它完全忽略输入，只考虑算法内部随机性。
对于任意输入 $\alpha$，都有：
因此，对于任意两个概率系综 $X$ 和 $Y$，都有：
所以：
因此，$D_1$ 无法区分任何一对概率系综。也就是说，区分器必须真正利用输入中存在的某种特征，才能产生区分能力。
比较 0 和 1 数量的区分器
考虑算法 $D_2$，当且仅当输入字符串中 0 的数量多于 1 的数量时输出 $1$。
设 $\operatorname{wt}(\alpha)$ 表示字符串 $\alpha$ 的汉明重量，即字符串中比特 $1$ 的数量。如果字符串长度为 $n$，那么 0 的数量多于 1 的数量等价于：
由于计算一个字符串中 1 的数量可以在线性时间内完成，因此 $D_2$ 是一个多项式时间算法。
所以，如果 $X$ 和 $Y$ 是计算不可区分的，那么：
必须是关于 $n$ 的可忽略函数。
也就是说，计算不可区分的概率系综，在 0 和 1 数量这一可高效计算的统计特征上，必须表现得几乎相同。
【可高效计算的统计特征】
如果两个概率系综是计算不可区分的，那么对于任何能够在多项式时间内计算的字符串统计量，它们都必须具有几乎相同的统计表现。例如，字符串中 $1$ 的数量、字符串是否以 $0$ 开头、字符串是否包含某个固定模式等。
如果某个多项式时间算法能够在这些特征上发现不可忽略的概率差异，那么它就可以被用作区分器，从而证明两个概率系综不是计算不可区分的。
但是，计算不可区分性并不要求两个概率系综在所有性质上都相似。对于无法在多项式时间内计算的量，即使两个概率系综表现出巨大差异，也不一定违反计算不可区分性。例如，Kolmogorov 复杂度、某些计算上难以求解的函数等。
因此，计算不可区分性只隐藏高效算法能够检测的差异，而不要求两个概率系综在数学结构上完全相同。
