【】

【基本思想】

计算不可区分性（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$ 的所有部分信息都难以获得，即单向性只保证整体反演困难，不保证原像的每一部分信息都被隐藏。

【基本问题】

虽然通常相信单向函数是存在的，但是仅仅知道存在某个单向函数并不足以支持实际应用，实际应用通常需要指定一个具体的函数，作为候选单向函数使用。

因此，提出合理的单向函数候选是一个具有实际意义的问题。

【无爪函数族】

基本思想

单向函数族的形式化框架，也可以用来定义一类新的函数族，即无爪函数族（Claw-Free Functions Collection）。