【概述】
在关于单向函数的定义中，负责反演函数的算法通常被限制为概率多项式时间算法。也就是说，安全性要求是：不存在任何高效随机算法能够以不可忽略概率从 $f(x)$ 中恢复出某个原像
在此基础上，考虑更强的安全性定义：不仅要求概率多项式时间算法不能反演函数，还要求即使是非均匀的多项式规模电路族也不能反演函数
需要注意的是，虽然反演困难性被加强为能够抵抗非均匀电路族的反演，但容易计算这一条件仍然使用均匀算法来表述。也就是说，函数 $f$ 本身仍然要求存在一个普通的多项式时间算法能够计算，而不是仅仅存在某个电路族能够计算
非均匀单向函数的定义与通常意义下的单向函数定义的关键区别在于反演者的能力不同：
- 均匀反演算法：由一个统一的概率多项式时间算法处理所有输入长度 $n$，算法不能针对每个长度单独获得额外建议
- 非均匀电路族：对于每个输入长度 $n$，都允许存在一个专门的电路 $C_n$，这些电路不一定由同一个高效算法统一生成，因此能力比普通概率多项式时间算法更强
因此，非均匀单向函数的安全性要求更强，它不仅排除了统一的高效反演算法，还排除了针对每个输入长度专门设计的高效电路反演器
【非均匀强单向函数的定义】
若函数 $f:\{0,1\}^{*} \rightarrow \{0,1\}^{*}$ 满足：
- 容易计算：存在一个多项式时间算法 $A$，使得对任意输入 $x$，算法 $A$ 都能够输出 $f(x)$
- 难以反演：对于任意一个非均匀的多项式规模电路族 $\{C_n\}_{n\in\mathbb{N}}$，任意正多项式 $\mathrm{poly}(\cdot)$，以及所有充分大的 $n$，都有
则函数 $f$ 被称为非均匀单向函数（Non-Uniformly One-Way Function）。其中，$U_n$ 表示在 $\{0,1\}^n$ 上均匀随机选取的输入。这里的概率只针对 $U_n$ 的所有可能取值计算，而不涉及电路内部的随机性，因为$C_n$ 是确定性电路
这个定义的含义是：即使对每个输入长度 $n$，敌手都可以使用一个专门为该长度设计的多项式规模电路 $C_n$，它仍然不能以不可忽略概率从 $f(U_n)$ 中找到一个合法原像
【非均匀单向性蕴含均匀单向性】
如果函数 $f$ 是非均匀单向函数，那么其也是通常意义下的单向函数。也就是说，如果函数 $f$ 能够抵抗所有非均匀多项式规模电路族的反演，那么它必然也能够抵抗所有均匀概率多项式时间算法的反演。因此有如下命题：
Proposition：非均匀单向函数一定是均匀意义下的单向函数。
设 $A’$ 是任意一个概率多项式时间反演算法。由于 $A’$ 是随机算法，它在运行时会使用一串随机比特。记 $r_n$ 为针对输入长度 $n$ 的一串随机比特，并且选择这样一串 $r_n$，使得当算法 $A’$ 固定使用这串随机比特时，其平均反演成功概率最大
也就是说，存在某个 $r_n$ 使得：
其中，左边的概率只对 $U_n$ 的随机选择取概率，右边的概率则同时对 $U_n$ 和算法 $A’$ 的内部随机比特取概率
这个不等式来自平均值思想：如果随机选择比特串时的平均成功概率是某个值，那么一定存在至少一串固定的比特串，使得使用这串比特串时的成功概率不低于平均值
接下来，可以构造一个电路 $C_n$。这个电路将算法 $A’$ 的代码和固定随机串 $r_n$ 都硬编码进去。由于 $A’$ 是多项式时间算法，而 $r_n$ 的长度也是关于 $n$ 的多项式，因此构造出的 $C_n$ 是多项式规模电路
这样一来，原本的随机算法 $A’$ 就被转化成了一个针对长度 $n$ 的确定性电路 $C_n$，并且这个电路的成功概率不低于原随机算法的成功概率
因此，如果存在一个均匀的概率多项式时间算法能够成功反演函数 $f$，那么就可以得到一个非均匀多项式规模电路族成功反演函数 $f$，这与 $f$ 的非均匀单向性矛盾，故非均匀单向函数必然也是通常意义下的单向函数
【非均匀安全性与均匀安全性的关系】
一般来说，通过上述这种平均化论证，可以将概率多项式时间算法转化为非均匀多项式规模电路族。因此，非均匀安全性通常蕴含均匀安全性，即：
但是反过来不一定成立。一个函数可能在均匀意义下是单向函数，也就是说不存在概率多项式时间算法可以有效反演它；但这并不必然排除某些非均匀多项式规模电路族能够反演它
因此：
从理论上说，可能存在这样的情况：普通意义下的单向函数存在，但非均匀单向函数不存在
不过这种情况通常被认为不太可能，密码学中广泛相信，非均匀单向函数是存在的
事实上，常见的单向函数中提到的候选单向函数，通常也被认为是非均匀单向函数
