【基本思想】

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

原来的放大方式是：如果一个函数 $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）。

【基本思想】

考虑一个函数族 $\{f_i\}$，其中每个索引 $i$ 对应一个具体函数 $f_i$。如果这些函数不仅是单向的，而且每个 $f_i$ 还是定义域上的置换，那么它们就构成一族单向置换（One-Way Permutations）。

与索引 $i$ 对应的一段辅助信息 $t(i)$，称为陷门（Trapdoor）。仅凭 $i$，无法高效计算出这个陷门，但是可以高效生成相互匹配的一对 $(i,t(i))$。

【概述】

在单向函数族中已经将单向函数表述为函数族的形式，从而更方便地描述一些自然的单向函数候选对象。

下面节介绍几个基于计算数论的常见候选函数族，包括：

【动机】

在之前讨论单向函数时，均把单向函数看作定义在无限集合 $\{0,1\}^*$ 上的一个函数，这种表述适合抽象讨论，但在描述许多自然的单向函数候选对象时并不方便。

原因在于，很多实际候选对象并不是一个单独定义在所有二进制串上的函数，而更像是有限函数族。例如，对于每个索引 $i$，都有一个对应的有限定义域 $D_i$，并且有一个函数 $f_i$ 作用在这个有限定义域上。

【通用单向函数】

利用通用机（Universal Machine）的概念，以及弱单向函数可以转化为强单向函数的命题，可以证明存在一种通用单向函数（Universal One-Way Function）。

通用不是指它无条件单向，而是指存在一个固定的、多项式时间可计算的函数 $f_{\mathrm{uni}}$，只要世界上存在单向函数，那么这个固定函数 $f_{\mathrm{uni}}$ 就是单向函数。