密码学专题| 五、基于单项函数的伪随机性构造

单向函数和单项置换

如果单项函数存在，则提供了一种构造伪随机发生器和伪随机函数的方案，进而可以用于构造流密码、分组密码以及消息认证码。

单项函数的定义如下:

当一个函数 \( f: \{0,1\}^* \rightarrow \{0,1\}^* \)满足如下条件，则是一个单项函数：

1. 存在一个多项式时间算法 \(M_f \) 有 \(M_f(x) = f(x) \)
2. \( \forall x \leftarrow \{0,1\}^* s.t. Pr[A(f(x)) \in f^{-1}(f(x))] \le negl(n) \)

如果将函数 f 的定义域和值域修改为 \( \{0,1\}^n \) 则定义了单项置换：

当一个函数 \( f_n: \{0,1\}^n \rightarrow \{0,1\}^n \)满足如下条件，则是一个单项函数：

1. 存在一个多项式时间算法 \(M_{f_n} \) 有 \(M_{f_n}(x) = f_n(x) \)
2. \( \forall x \leftarrow \{0,1\}^n s.t. Pr[A(f_n(x)) \in f_n^{-1}(f_n(x))] \le negl(n) \)

目前无法证明任何一个候选函数是单项函数，但是有一些备选函数，包括：

1. 大整数的素数分解问题
2. 子集求和问题等

单项函数都有一个硬核，我的理解是硬核提供了最原始的函数的单项特性。如果一个单射函数拥有硬核，那么这是一个单项函数。但是这个单项函数可能提供了来自自变量 x 的其他信息。硬核谓词的定义如下：

当一个函数 \( hc: \{0,1\}^n \rightarrow \{0,1\} \)满足如下条件，则称它为函数 f 的硬核：

1. 存在一个多项式时间算法 \(M_{hc} \) 有 \(M_{hc}(x) = hc(x) \)
2. \( \forall x \leftarrow \{0,1\}^n s.t. Pr[A(f(x)) = hc(x)] \le negl(n) \)

可以证明如下一系列结论：

1. 定理一：如果一个函数 f 是单向函数，那么必然存在一个单项函数 g 及其硬核 gl。此外，如果 f 是单项置换，那么 g 也是单项置换。
2. 定理二：如果 f 是一个单向函数，hc 是 f 的硬核。那么\(G(s) = (f(s), hc(s)) \) 构成了 l(n) = n+1 的伪随机发生器。
3. 定理三：如果存在一个 l(n) = n+1 的伪随机发生器，那么对于任意多项式 p 存在一个l(n) = p(n) 的伪随机数发生器。
4. 定理四：如果存在 l(n) = 2 的伪随机数发生器，那么必然存在伪随机函数。
5. 定理五：如果存在伪随机函数，则必然存在强伪随机置换。

也就是说，如果存在单向函数 f ，那么就可以构造出伪随机发生器、伪随机函数以及强伪随机转换。进一步地，就存在 CCA 安全的加密方案和选择消息攻击的安全消息认证码。

反过来也有类似的结论：

1. 定理六：如果存在伪随机发生器，那么存在单项函数
2. 定理七：如果在敌手 A 存在不可区分的对称秘钥加密方案，则存在单项函数

（证明在书上，太长了，这里就不打一遍了，但是一定要看懂哦~）