5 伪随机对象的理论构造

本节学习如何设计基于单向函数存在的假设从理论上构造PRG、PRF、PRP这三个伪随机对象。
目录：单向函数（One-Way Function），从OWF到PRP
概览
- 现代密码学的贡献之一是，单向函数的存在等价于所有（有意义的）私钥密码学的存在；
- 我们学习一系列密码学对象的构造过程：从OWF构造核心断言（HCP），构造RPG，构造PRF，构造PRP，构造安全私钥加密方案，而安全私钥加密方案就是一个OWF，从而形成一个闭环；
单向函数（One-Way Functions (OWF)）

单向函数是一个正向易于计算（多项式时间），而逆向难以计算（无多项式时间）；
下面的单向函数定义是由姚期智提出的；
求逆实验 $\mathsf{Invert}_{\mathcal{A},f}(n)$:
1. 随机产生输入 $x \gets {0,1}^n$. 计算 $y := f(x)$. 注：挑战$y$是由随机产生的$x$得到的，而不是直接随机挑选一个$y$；
2. $\mathcal{A}$ 以 $1^n$ 和 $y$ （挑战）作为输入，并输出 $x'$.
3. 实验成功 $\mathsf{Invert}_{\mathcal{A},f}(n) = 1$ ，如果 $f(x')=y$，否则 0. 注：这里不需要$x'= x$；

乘法与分解（Multiplication and factoring）：$f_{\mathsf{mult}}(x,y)=(xy,|x|,|y|)$, $x$ 和 $y$ 是相同长度的质数；注：后面会学习RSA问题
模平方和平方根（Modular squaring and square roots）：$f_{\mathsf{square}}(x)=x^2\bmod N$；注：也被应用于公钥密码学
离散指数与对数（Discrete exponential and logarithm）：$f_{g,p}(x)=g^x\bmod p$；注：后面将学习DH密钥交换协议
子集和问题（Subset sum problem）：$f(x_1,\dotsc,x_n,J)=(x_1,\dotsc,x_n,\sum_{j \in J} x_j)$；注：子集和问题判定是否存在一个子集中元素之和为给定的值
密码学安全哈希函数（Cryptographically secure hash functions）：稍后会学习；

一个函数 $\mathsf{hc}; : ; {0,1}^* \to {0,1}$ 是一个函数$f$的核心断言（ hard-core predicate），如果
- (1) $\mathsf{hc}$ 可在多项式时间计算；
- (2) $\forall$ 概率多项式时间 $\mathcal{A}$， $\exists; \mathsf{negl}$ 使得 $ \Pr_{\substack{x \gets {0,1}^n}}[\mathcal{A}(f(x)) = \mathsf{hc}(x)] \le \frac{1}{2} + \mathsf{negl}(n). $
注：核心断言可以理解为根据函数的输出最难推断的关于输入的一个比特信息，任意敌手算法与随机猜测相比几乎没有差异。

定理：$f$是一个OWF。那么，存在一个OWF $g$ 并与 $g$ 伴随着一个HCP $gl$。
问题： $\mathsf{gl}(x) = \bigoplus^{n}_{i=1} x_i$ 是任意OWF的HCP吗? 答案是否定的，例如一个单向函数输出的最后一个比特就是输入按位异或的结果；
证明：$g(x,r) \overset{\text{def}}{=} (f(x), r)$, for $|x| = |r|$, 并定义 $ \mathsf{gl}(x,r) \overset{\text{def}}{=} \bigoplus^{n}_{i=1} x_i \cdot r_i $。其中，$r$ 是一个随机串。
说明：$\mathsf{gl}$就是从$x$中随机选择若干比特异或结果作为核心断言。即便敌手根据输出推断出$x$中若干比特的信息，但仍不能推断出（由$r$来）随机挑选的任意若干比特信息（核心断言），否则意味着敌手可以求出整个$x$。

定理：$f$ 是一个OWP并且 $\mathsf{hc}$ 是一个 $f$ 的 HCP 。那么，$G(s) \overset{\text{def}}{=} (f(s), \mathsf{hc}(s))$ 构造了一个 PRG 带有扩展因子 $\ell(n) = n+1$，并且 $\forall$ 多项式 $p(n) > n$, $\exists$ 一个 PRG 带有扩展因子 $\ell(n) = p(n)$。
定理成立的理由有两点：
- 因为$f$为排列，那么当$s$随机生成时，$f(s)$也是均匀随机的，$G(s)$的头部也就是随机的；
- 根据$f(s)$难以推断核心断言$\mathsf{hc}(s)$，这正是伪随机生成器的伪随机性的判断依据：下一比特不可预测性。

定理：如果存在一个PRG带有扩展因子$\ell(n) = 2n$，那么存在一个PRF。
$F_k(x_1x_2\cdots x_n) = G_{x_n}(\cdots(G_{x_2}(G_{x_1}(k)))\cdots), G(s)=(G_0(s),G_1(s)).$
以密钥$k$为PRG的种子生成随机串，并将该随机串对半分为两个子串$G_0(s),G_1(s)$；再以每个子串作为种子分别生成两个新的子串；由此，构造一个以密钥（种子）为根的二叉树，每个叶子节点对应伪随机函数的一个输出，从输入到输出的映射就是从根到叶子的一条分支，根据输入每个比特值来选择分叉：0为左，1为右；
例如，$F_k(011) = G_1(G_1(G_0(k)))$；以$k$为根，根据第一个比特选择左分支，接着选择右分支，右分支。
PRF随机性来自于PRG的随机性。

Feistel网络可以将一个$n$比特的PRF转变为一个$2n$比特的PRP，有以下定理
定理：一个3轮的Feistel网络可将一个PRF转变为一个PRP。
定理：一个4轮的Feistel网络可将一个PRP转变为一个strong PRP。
说明：
- 首先，Feistel网络本身特性是排列，因此证明上述定理成立的关键在于，证明伪随机性；伪随机性来自与每轮的mangler函数是PRF，其输出是一个独立的随机值。
- 对于为什么至少需要3轮？首先可以观察到如果只有1轮，则不是伪随机的，因为$R_0$被直接输出为$L_1$；如果只有2轮，也不是随机的，因为只改变$L_0$来翻转1个比特，那么$R_2$也只翻转1个比特。当3轮时，上述两个情况不会发生，并且输出结果$L_3, R_3$都是经过了PRF结果得到的。

前面的理论说明OWP的存在是安全加密方案的充分条件，同时我们还可以证明OWP的存在也是安全加密方案的必要条件。
定理：假设存在OWP，那么存在PRG，PRF，PRP和CCA安全私钥加密方案。
- 如何构造CCA安全的加密方案将在后面学习。
命题：如果存在窃听者不可区分私钥加密方案，那么存在一个OWF。
证明：$f(k,m,r) \overset{\text{def}}{=} (\mathsf{Enc}_k(m,r),m)$，其中 $\abs{k}=n, \abs{m}=2n, \abs{r}=\ell(n)$。
- 从破解加密方案问题$\mathcal{A}'$规约到单向函数求逆问题$\mathcal{A}$。规约的关键之一在于将挑战密文和一个明文 $c|m_0$ 作为$\mathcal{A}$求逆的输入。当求拟成功时，$\mathcal{A}'$输出0；否则，输出1。当$m_0$被加密，则破解加密方案意味着可求逆；当$m_1$被加密，则破解加密方案意味着没有成功求逆，概率为$1-1/2^n$。

Provide feedback