【基本问题】

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

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

【无爪函数族】

基本思想

单向函数族的形式化框架，也可以用来定义一类新的函数族，即无爪函数族（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}}$ 就是单向函数。

【归约论证的基本结构】

回顾弱单向函数的存在性定理中的证明结构：给定一个弱单向函数 $f$，首先构造一个多项式时间可计算函数 $g$，然后证明 $g$ 是强单向函数。

证明使用了归约论证（Reducibility Argument），其基本思想是：如果存在一个有效算法能够以不可忽略概率反演函数 $g$，从而否定 $g$ 的强单向性，那么就可以利用这个算法构造出一个有效算法来反演函数 $f$，从而否定 $f$ 的弱单向性。因此，只要 $f$ 的弱单向性成立，$g$ 就必须是强单向的。

【存在性定理】

弱单向函数与强单向函数的关系中函数 $g$ 的构造与证明说明，只要单向函数存在，就可以构造出一个弱单向但不是强单向的函数。因此，不能认为所有单向函数都是强单向函数

但是，也不能认为所有单向函数都只能是弱单向函数。事实上，弱单向函数的存在可以推出强单向函数的存在

【概述】

某些函数虽然在某个不可忽略比例的输入上难以反演，但在大部分输入上可能仍然容易反演，因此它只能满足弱单向性，而不能满足强单向性

但是，从存在性角度看，弱单向函数和强单向函数是等价的，即：

【概述】

在关于单向函数的定义中，负责反演函数的算法通常被限制为概率多项式时间算法。也就是说，安全性要求是：不存在任何高效随机算法能够以不可忽略概率从 $f(x)$ 中恢复出某个原像

在此基础上，考虑更强的安全性定义：不仅要求概率多项式时间算法不能反演函数，还要求即使是非均匀的多项式规模电路族也不能反演函数