【引入】

计算不可区分性，是基于概率多项式时间算法来定义的，即如果不存在任何 PPT 区分器能够有效区分两个概率系综，就称它们是计算不可区分的。

考虑一个更强的不可区分性概念：多项式规模电路意义下的不可区分性（Indistinguishability by Polynomial-Size Circuits）。其不只考虑统一的多项式时间算法，而是允许对每个输入长度 $n$，都有一个专门设计的电路 $C_n$ 作为区分器。

【基本问题】

根据计算不可区分性的定义，两个概率系综 $X=\{X_n\}_{n\in\mathbb N}$ 和 $Y=\{Y_n\}_{n\in\mathbb N}$ 被认为是计算不可区分的，是指任何高效算法都无法根据单个样本区分它们。

也就是说，区分器只能拿到一个样本 $X_n$ 或 $Y_n$，然后判断这个样本来自哪个分布。但是在很多密码学应用中，敌手往往不止看到一个样本，而是可能看到多个独立样本。

【统计距离】

对于每个可能的字符串 $\alpha$，分别比较 $P[X_n=\alpha]$ 和 $P[Y_n=\alpha]$，两者的差值表示两个分布在字符串 $\alpha$ 上分配的概率相差多少，将所有可能字符串上的概率差取绝对值后相加，再乘以 $\frac12$，就得到两个分布之间的整体差异。

设两个概率系综分别为 $X=\{X_n\}_{n\in\mathbb N}$，$Y=\{Y_n\}_{n\in\mathbb N}$，对于每个安全参数 $n$，随机变量 $X_n$ 和 $Y_n$ 之间的统计距离（Statistical Distance）定义为：

【基本思想】

计算不可区分性（Computational Indistinguishability）是定义伪随机性的基础，它刻画的不是两个对象在数学上是否完全相同，而是任何高效算法能否发现它们之间的差异。

其基本思想是：如果不存在任何高效算法能够区分两个对象，那么对于一切能够由高效算法描述的实际用途，可以将这两个对象视为等价。

【基本概念】

伪随机生成器

伪随机生成器（Pseudorandom Generator，PRG）是一类高效的确定性程序，它能够将一个较短的、随机选取的种子（Seed）扩展为一个长度更长的伪随机序列（Pseudorandom Sequence）。

【基本思想】

弱单向函数的存在定理中，已经讨论过如何把弱单向函数放大强单向函数，但是，这种构造方法实际效率很差，只有理论意义。

原来的放大方式是：如果一个函数 $f$ 在长度为 $n$ 的输入上，有至少 $\frac{1}{\mathrm{poly}(n)}$ 比例的输入难以反演，那么可以构造一个新函数 $g$，使得 $g$ 在几乎所有输入上都难以反演。

【硬核函数的定义】

基本思想

在强单向函数的内积硬核谓词定理中，证明了每一个单向函数都可以经过简单修改，从而具有一个硬核谓词。硬核谓词本质上是关于原像 $x$ 的一比特信息，即使已经知道函数值 $f(x)$，也无法高效预测这一比特。

【强单向函数的内积硬核谓词定理】

定理

设 $f$ 是任意强单向函数，定义函数：

【引入】

单向函数 $f$ 的含义是：给定 $y=f(x)$，想要找到 $y$ 在 $f$ 下的某个原像 $x$ 是计算上困难的。

但是，这并不意味着给定 $f(x)$ 后，关于 $x$ 的所有部分信息都难以获得，即单向性只保证整体反演困难，不保证原像的每一部分信息都被隐藏。