【基本问题】

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

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

一个合理的单向函数候选至少需要满足两个方面的要求：一方面，它必须容易正向计算；另一方面，它必须在平均意义下难以反演。

如果候选对象是一个普通函数，那么应该存在非常高效的算法计算该函数；如果候选对象是一族单向函数，那么定义域采样算法和函数求值算法都应该非常高效。

【反演困难性的核心要求】

在提出候选单向函数时，不能只考虑函数是否在最坏情况下难以反演，而必须考虑它是否在平均情形（Average Case）下难以反演。

这里的平均不是任意意义下的平均，而是相对于候选函数自身诱导出来的实例分布而言的。也就是说，反演算法面对的输入并不是任意构造的困难实例，而是按照候选函数的采样过程自然生成出来的实例。

因此，一个候选单向函数要想合理，必须满足：

最坏情况困难性并不能直接推出平均情形困难性，即使某个问题存在非常困难的实例，也不能说明随机生成的实例通常是困难的。

平均情形困难性和最坏情况分析不同，它对实例分布非常敏感。

如果一个问题在某个分布下平均困难，并不能随意推出它在另一个分布下也平均困难。因此，从一种分布下的平均情形复杂性推导另一种分布下的平均情形复杂性时，必须非常谨慎。

如果忽略这一点，就可能提出不合理的候选单向函数。密码学发展中已经出现过这种情况：研究者只注意到底层问题在最坏情况下可能困难，却没有认真分析候选函数诱导出的实例分布是否也会产生平均困难实例，结果给出了不好的建议。

一个典型的不合理尝试是，基于图同构问题（Graph Isomorphism Problem）的猜想困难性来构造单向函数。

定义候选函数：

$F_{\mathrm{GI}}(G,\pi)=(G,\pi G)$

其中，$G$ 是一个无向图，$\pi$ 是其顶点集合上的一个置换，$\pi G$ 表示将 $G$ 的顶点按照 $\pi$ 重新命名后得到的图。

具体来说，在 $\pi G$ 中，当且仅当 $(u,v)$ 是 $G$ 中的一条边时，$(\pi(u),\pi(v))$ 是 $\pi G$ 中的一条边。

这个函数的正向计算是容易的：给定图 $G$ 和置换 $\pi$，只需要按照 $\pi$ 重命名顶点即可得到 $\pi G$。

但是，问题在于它并不适合作为单向函数候选。虽然人们确实相信图同构问题不能在多项式时间内求解，但这只是关于图同构问题最坏情况困难性的猜想。

对于函数 $F_{\mathrm{GI}}$ 自然生成的大多数实例，反演其实是容易的。例如，可以利用顶点度数统计等信息确定两个图之间的同构关系，从而恢复出对应的置换。

因此，图同构问题的最坏情况困难性，并不能推出 $F_{\mathrm{GI}}$ 在均匀分布下具有平均情形困难性。

即使某个问题在某种分布下确实是平均困难的，也不能只说“存在这样的困难分布”。若要基于它提出候选单向函数，还必须明确指定这个分布，并且给出一个高效采样算法，使得可以按照该分布生成实例。

也就是说，候选单向函数不仅需要依赖一个困难问题，还需要说明：

如果这些内容没有被明确给出，那么即使底层问题在最坏情况下看起来很难，也不足以支撑一个合理的单向函数候选。