单向函数和单项置换
如果单项函数存在，则提供了一种构造伪随机发生器和伪随机函数的方案，进而可以用于构造流密码、分组密码以及消息认证码。
单项函数的定义如下:
当一个函数 \( f: \{0,1\}^* \rightarrow \{0,1\}^* \)满足如下条件，则是一个单项函数：
- 存在一个多项式时间算法 \(M_f \) 有 \(M_f(x) = f(x) \)
- \( \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 \)满足如下条件，则是一个单项函数：
- 存在一个多项式时间算法 \(M_{f_n} \) 有 \(M_{f_n}(x) = f_n(x) \)
- \( \forall x \leftarrow \{0,1\}^n s.t. Pr[A(f_n(x)) \in f_n^{-1}(f_n(x))] \le negl(n) \)
目前无法证明任何一个候选函数是单项函数，但是有一些备选函数，包括：
- 大整数的素数分解问题
- 子集求和问题等
单项函数都有一个硬核，我的理解是硬核提供了最原始的函数的单项特性。如果一个单射函数拥有硬核，那么这是一个单项函数。但是这个单项函数可能提供了来自自变量 x 的其他信息。硬核谓词的定义如下：
当一个函数 \( hc: \{0,1\}^n \rightarrow \{0,1\} \)满足如下条件，则称它为函数 f 的
硬核：
- 存在一个多项式时间算法 \(M_{hc} \) 有 \(M_{hc}(x) = hc(x) \)
- \( \forall x \leftarrow \{0,1\}^n s.t. Pr[A(f(x)) = hc(x)] \le negl(n) \)
可以证明如下一系列结论：
- 定理一：如果一个函数 f 是单向函数，那么必然存在一个单项函数 g 及其硬核 gl。此外，如果 f 是单项置换，那么 g 也是单项置换。
- 定理二：如果 f 是一个单向函数，hc 是 f 的硬核。那么\(G(s) = (f(s), hc(s)) \) 构成了 l(n) = n+1 的伪随机发生器。
- 定理三：如果存在一个 l(n) = n+1 的伪随机发生器，那么对于任意多项式 p 存在一个l(n) = p(n) 的伪随机数发生器。
- 定理四：如果存在 l(n) = 2 的伪随机数发生器，那么必然存在伪随机函数。
- 定理五：如果存在伪随机函数，则必然存在强伪随机置换。
也就是说，如果存在单向函数 f ，那么就可以构造出伪随机发生器、伪随机函数以及强伪随机转换。进一步地，就存在 CCA 安全的加密方案和选择消息攻击的安全消息认证码。
反过来也有类似的结论：
- 定理六：如果存在伪随机发生器，那么存在单项函数
- 定理七：如果在敌手 A 存在不可区分的对称秘钥加密方案，则存在单项函数
（证明在书上，太长了，这里就不打一遍了，但是一定要看懂哦~）
本人保留对侵权者及其全家发动因果律武器的权利
版权提醒
如无特殊申明，本站所有文章均是本人原创。转载请务必附上原文链接：https://www.elliot98.top/post/crypto/crypto-cipher/。
如有其它需要，请邮件联系！版权所有，违者必究！