【动机】
在之前讨论单向函数时，均把单向函数看作定义在无限集合 $\{0,1\}^*$ 上的一个函数，这种表述适合抽象讨论，但在描述许多自然的单向函数候选对象时并不方便。
原因在于，很多实际候选对象并不是一个单独定义在所有二进制串上的函数，而更像是有限函数族。例如，对于每个索引 $i$，都有一个对应的有限定义域 $D_i$，并且有一个函数 $f_i$ 作用在这个有限定义域上。
因此，与其把单向函数看作一个无限定义域上的函数，不如把它看作一个函数族（Collection of Functions）。
在这种表述下，一个函数族由无限多个函数组成，每个函数都作用在一个有限定义域上。族中的函数共享一个统一的求值算法：给定某个函数的简洁表示以及定义域中的一个元素，该算法可以输出这个函数在该点的取值。
这种函数族的表述虽然更繁琐，但更适合描述自然的单向函数候选对象。
【单向函数族的基本定义】
索引集合与有限函数族
一个函数族由两部分组成：
一个无限的索引集合 $\bar I$
一组由索引指定的有限函数 $\{f_i\}_{i\in \bar I}$
即对于每个索引 $i\in \bar I$，都有一个对应的函数 $f_i$，该函数的定义域为有限集合 $D_i$。
索引集合的稠密性
为了能够有效随机选出合法索引，索引集合 $\bar I$ 通常不能过于稀疏。因此，通常要求 $\bar I$ 是所有二进制串集合中的一个稠密子集。
这里的稠密性是指，在所有长度为 $n$ 的二进制串中，属于 $\bar I$ 的字符串比例是可察觉的，即：
这说明，合法索引不能过于稀少，否则很难有效随机选出一个合法索引。
单向函数族的定义
密码学所需的三个算法
为了让函数族能够用于密码学应用，还需要能够高效完成三件事：
- 高效选择索引：需要能够随机选出一个索引 $i$，从而指定集合中的某个函数 $f_i$
- 高效选择定义域元素：给定索引 $i$ 后，需要能够随机选出一个元素 $x\in D_i$
- 高效计算函数值：给定索引 $i$ 和输入 $x\in D_i$，需要能够高效计算 $f_i(x)$
因此，引入三个概率多项式时间算法：
- 索引采样算法 $I$：输入 $1^n$，随机输出一个索引
- 定义域采样算法 $D$：输入索引 $i$，随机输出一个定义域元素 $x\in D_i$
- 函数求值算法 $F$：输入 $i$ 和 $x\in D_i$，输出 $f_i(x)$
这里索引采样算法 $I$ 的输入写成 $1^n$，是用一元形式表示整数 $n$，这样做是为了符合复杂性理论中的标准约定：高效算法的运行时间应当是其输入长度的多项式。如果直接用二进制表示 $n$，输入长度只有 $\log n$，就会改变多项式时间的含义。
正式定义
如果存在三个概率多项式时间算法 $I,D,F$，并满足以下两个条件，则函数集合 $\{f_i:D_i\to \{0,1\}^{*}\}_{i\in \bar I}$，称为强单向函数族（Strongly One-Way Collection）。
（1）容易采样和计算：函数族必须必须能够高效采样索引、高效采样输入，并且高效计算函数值
索引采样算法 $I$ 在输入 $1^n$ 时，输出一个随机变量，其取值属于 $\bar{I}\cap \{0,1\}^n$
定义域采样算法 $D$ 在输入 $i\in \bar{I}$ 时，输出一个随机变量，其取值属于 $D_i$
- 函数求值算法 $F$ 在输入 $i\in \bar{I}$ 和 $x\in D_i$ 时，输出 $f_i(x)$
由此可以看出，$D_i$ 中元素的长度至多是 $|i|$ 的某个多项式，即可以不失一般性地假设：
（2）难以反演：函数族必须满足单向性要求
对于任意概率多项式时间算法 $A’$，任意正多项式 $\mathrm{poly}(\cdot)$，以及所有充分大的 $n$，都有：
其中，$I_n$ 是算法 $I$ 在输入 $1^n$ 时输出的随机变量，$X_n$ 是在给定随机索引 $I_n$ 后算法 $D$ 在输入 $I_n$ 时输出的随机变量。
这一定义的含义是，先通过 $I$ 随机选出一个函数索引 $I_n$，再通过 $D$ 随机选出一个输入 $X_n\in D_{I_n}$，然后给反演算法 $A’$ 输入 $(I_n,f_{I_n}(X_n))$，如果 $A’$ 能输出某个属于 $f^{-1}_{I_n}(f_{I_n}(X_n))$ 的元素，那么它就成功反演了 $f_{I_n}$ 在该输出值上的某个原像。强单向性要求这种成功概率必须小于任意多项式倒数，即只能是可忽略的。
弱单向函数族的定义与此类似，只是把反演成功概率可忽略替换为弱单向性对应的失败概率要求。
输入分布的重要性
在函数族的定义中，需要特别注意，单向性并不是相对于均匀分布在所有合法索引和所有定义域元素上定义的，而是相对于采样算法 $I$ 和 $D$ 诱导出的分布定义的。
也就是说，算法 $I(1^n)$ 的输出不一定均匀分布在 $\bar I\cap \{0,1\}^n$ 上，甚至不要求它在所有合法索引上分散。类似地，算法 $D(i)$ 的输出也不一定均匀分布在 $D_i$ 上。
但是，如果 $D(i)$ 的输出几乎总是集中在少量输入上，那么反演算法就可以通过枚举或记忆这些高概率输入来提高反演成功率，从而破坏单向性。这使得难反演条件本身会限制 $D(i)$ 的分布不能主要集中在多项式多个输入上。
因此，函数族的单向性同时依赖两部分：
- 函数映射本身是否难以反演
- 采样算法 $I$ 和 $D$ 诱导出的输入分布是否使得反演问题足够困难
【单向函数族的三元组表示】
由于一个单向函数族的实际使用方式完全由索引采样、定义域采样和函数求值这三个过程决定，因此可以用一个三元组 $(I,D,F)$ 来描述一个单向函数族。
也就是说，如果存在某个函数族，使得这三个概率多项式时间算法满足容易采样和计算以及难以反演两个条件，那么就可以说 $(I,D,F)$ 构成了一个单向函数族。
从表达能力上看，普通单向函数和单向函数族可以相互表示，因此二者在理论上是等价的。但是，普通单向函数适合抽象理论讨论，而函数族更适合描述自然的候选单向函数。
【单向函数族的高概率定义】
为了更方便地描述自然候选对象，对单向函数族的严格定义进行了两个放宽：
- 索引采样算法 $I$ 在输入 $1^n$ 时，不一定必须输出长度为 $n$ 的索引，也可以输出长度为 $\mathrm{poly}(n)$ 的索引
- 允许所有算法以可忽略概率失败。特别地，可以允许索引采样算法 $I$ 以可忽略概率输出不属于 $\bar I$ 的字符串
也就是说，在严格定义中，算法 $I(1^n)$ 应当总是输出合法索引，而在放宽定义中，只要求它输出非法索引的概率是可忽略的。
【额外性质】
索引集合与定义域
一些候选单向函数族还具有额外的性质，常见的额外性质有两类：
- 索引集合可高效识别：存在一个高效算法，可以判断某个字符串 $i$ 是否属于索引集合 $\bar I$
- 定义域可高效识别：存在一个高效算法，给定 $i\in \bar I$ 和字符串 $x$，可以判断 $x$ 是否属于 $D_i$
这两个性质不是单向函数族定义中的必要条件。定义本身只要求能够通过采样算法生成合法索引和合法输入，并不要求存在一个公开的判定算法来检查合法性。但是，在很多自然候选构造中，如果索引集合和定义域都可以高效识别，那么使用和分析都会更方便。
采样证据与 NP 见证
需要注意的是，可高效采样本身确实能给出某种合法性证据。例如，如果索引 $i$ 是由采样算法 $I$ 使用随机选择生成的，那么这些随机选择可以作为证明 $i\in \bar I$ 的证据；类似地，如果 $x$ 是由定义域采样算法 $D$ 在输入 $i$ 后生成的，那么生成 $x$ 时使用的随机选择也可以作为证明 $x\in D_i$ 的证据。
从复杂性理论角度看，这类随机选择相当于一个 NP 见证（NP-Witness）。给出它之后，可以重新运行采样过程，从而验证对应对象确实是合法生成的。
但是，这种证据通常不能直接公开给反演算法，因为生成索引或输入时使用的随机选择可能包含额外信息，而这些额外信息可能帮助反演 $f_i$。尤其是对于定义域元素 $x\in D_i$，如果把生成 $x$ 的随机选择交给反演算法，那么反演算法可能可以直接恢复出 $x$，这就等于把原像泄露出去了。
因此，需要着重区分两件事：函数族定义要求的是合法对象可以高效生成，额外性质讨论的是合法对象是否可以被高效识别。前者并不自动推出后者，而且即使采样过程的随机性可以作为合法性证据，这种证据也未必适合公开，因为它可能破坏单向性。
