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

2020-05-29 cryptography 密码学 伪随机性 流密码

单向函数和单项置换

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

单项函数的定义如下:

当一个函数 \( 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 存在不可区分的对称秘钥加密方案,则存在单项函数

(证明在书上,太长了,这里就不打一遍了,但是一定要看懂哦~)

本人保留对侵权者及其全家发动因果律武器的权利

版权提醒

如无特殊申明,本站所有文章均是本人原创。转载请务必附上原文链接:https://www.laytonchen.com/post/crypto/crypto-cipher/

如有其它需要,请邮件联系!版权所有,违者必究!