PRG的扩展

本文主要是介绍PRG的扩展，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

PRG的并行扩展

PRG可以通过一个较短的输入得到一个较长的输出，但是如果这个输出的长度仍然达不到我们的要求怎么办呢？一个很自然的想法是将多个PRG拼起来，假设有 $n$ 个PRG拼到了一起，那么我们便可以得到 $nL$ 长的输出。那么这个新的 $\mathcal{G}^\prime$ 的安全性怎么样呢？直观来看，似乎只要 $n$ 不是很大， $\mathcal{G}$ 是安全的就可以保证 $\mathcal{G}^\prime$ 安全的。事实上，我们有如下定理：

定理1：如果存在一个安全的PRG $\mathcal{G}$ ，那么 $n$ 个 $\mathcal{G}$ 拼起来得到的新的PRG $\mathcal{G}^\prime$ 就是安全的，即 $\mathcal{G}^\prime(s_1,\cdots,s_n):=(\mathcal{G}(s_1),\cdots,\mathcal{G}(s_n))$ 是安全的。其中 $s_1,\cdots,s_n$ 从输入空间中独立随机选取， $n$ 是一个不超过关于安全参数的多项式界的一个参数。

证明：这个定理的证明用到了密码学中一个非常重要的证明方法就是混合论证（hybrid argument）。为了证明这个定理，我们可以先考察 $n=2$ 时的情况。当 $n=2$ 时，类似于前面定义PRG的安全性（https://blog.csdn.net/pllt1991/article/details/103915625），我们定义下面两个experiment：

$PPrgExp_0^{\mathcal{G}^\prime,\mathcal{A}}$ ：

$\mathcal{C}$ 以 $(s_1,s_2)$ 作为 $\mathcal{G}^\prime$ 的输入得到一个 $2L$ 比特长的输出 $(r_1,r_2)$ 并发送给 $\mathcal{A}$ ;

$\mathcal{A}$ 向 $\mathcal{C}$ 返回一个比特 $b^\prime$ $\in\{0,1\}$ ；

输出 $b^\prime$

$PPrgExp_1^{\mathcal{G}^\prime,\mathcal{A}}$ ：

$\mathcal{C}$ 随机选取 $(r_1,r_2)\in\{0,1\}^L\times\{0,1\}^L$ 并发送给 $\mathcal{A}$ ;

$\mathcal{A}$ 向 $\mathcal{C}$ 返回一个比特 $b^\prime$ $\in\{0,1\}$ ；

输出 $b^\prime$

那么我们的目标就是证明敌手 $\mathcal{A}$ 在这两个experiment上的优势是可忽略的。现在我们定义3个attack game如下：

Game 0：

$\mathcal{C}$ 以 $(s_1,s_2)$ 作为 $\mathcal{G}^\prime$ 的输入得到一个 $2L$ 比特长的输出 $(r_1,r_2)$ 并发送给 $\mathcal{A}$ ;

$\mathcal{A}$ 向 $\mathcal{C}$ 返回一个比特 $b^\prime$ $\in\{0,1\}$ ；

Game 1：

$\mathcal{C}$ 选取 $r_1\xleftarrow{R}\{0,1\}^L$ 以及 $r_2=\mathcal{G}(s_2)$ 组成 $(r_1,r_2)$ 并发送给 $\mathcal{A}$ ;

$\mathcal{A}$ 向 $\mathcal{C}$ 返回一个比特 $b^\prime$ $\in\{0,1\}$ ；

Game 2：

$\mathcal{C}$ 随机选取 $(r_1,r_2)\in\{0,1\}^L\times\{0,1\}^L$ 并发送给 $\mathcal{A}$ ;

$\mathcal{A}$ 向 $\mathcal{C}$ 返回一个比特 $b^\prime$ $\in\{0,1\}$ ；

可以看出，Game 0实际上就是 $PPrgExp_0^{\mathcal{G}^\prime,\mathcal{A}}$ ，Game 2实际上就是 $PPrgExp_1^{\mathcal{G}^\prime,\mathcal{A}}$ ，而Game 1则混合了Game 0和Game 2中的挑战串来源，这也是这种证明方法被称为混合论证的原因。现在，令 $p_i(i=0,1,2)$ 分别代表 $\mathcal{A}$ 返回1（即敌手认为它收到的挑战是随机串）的概率，然后我们还是按照通过PRG的安全性来论证流密码语义安全性的思路将对于 $\mathcal{G}^\prime$ 的敌手 $\mathcal{A}$ 作为子程序来调用对于 $\mathcal{G}$ 的敌手 $\mathcal{B}$ 。需要注意的是，由于 $\mathcal{A}$ 接受的挑战是两个串，而 $\mathcal{B}$ 接受的挑战是一个串，因此 $\mathcal{B}$ 需要“分裂成”两个 $\mathcal{B}_1$ 和 $\mathcal{B}_2$ 才能完成对 $\mathcal{A}$ 。对 $\mathcal{B}_1$ 来说，它首先接受它自己的挑战 $r_1$ ，然后通过 $\mathcal{G}$ 自己生成另一个比特串 $r_2$ ，组合成 $(r_1,r_2)$ 以后作为 $\mathcal{A}$ 挑战发送，然后 $\mathcal{B}_1$ 返回 $\mathcal{A}$ 返回的比特。显然，当 $\mathcal{B}_1$ 处于 $PrgExp_0^{\mathcal{G},\mathcal{B}}$ 的时候，就相当于在执行Game 0；当 $\mathcal{B}_1$ 处于 $PrgExp_1^{\mathcal{G},\mathcal{B}}$ 的时候，就相当于在执行Game 1，而因为 $\mathcal{G}$ 是安全的，即敌手优势是可忽略的，因此 $|p_0-p_1|$ 是可忽略的。同样的，可以证明 $|p_1-p_2|$ 是可忽略的，而 $\mathcal{G}^\prime$ 的敌手优势其实就是 $|p_0-p_2|(=|p_0-p_1+p_1-p_2|\le|p_0-p_1|+|p_1-p_2|)$ 也是可忽略的，从而证明了 $\mathcal{G}^\prime$ 是安全的。这种方法虽然可以证明 $n=2$ 时的情况，但对于一般的 $n$ 证明起来比较麻烦，因此还有另外一种证明方法。

我们在 $\mathcal{B}_1$ 和 $\mathcal{B}_2$ 的基础上再包上一层，即现在再构造一个 $\mathcal{G}$ 的新的敌手 $\mathcal{B}$ 来调用 $\mathcal{B}_1$ 和 $\mathcal{B}_2$ 。具体来说， $\mathcal{B}$ 接受到挑战 $r$ 以后随机选取 $\omega\in\{1,2\}$ 并将 $r$ 发送给 $\mathcal{B}_{\omega}$ 来调用，那么可以看出对于 $\mathcal{B}$ 来说有 $\begin{align*}P(W_0)=P(\omega=1)P(W_0|\omega=1)+P(\omega=2)P(W_0|\omega=2)=\frac{1}{2}(P(W_0|\omega=1)+P(W_0|\omega=2))=\frac{1}{2}(p_0+p_1) \end{align*}$

$\begin{align*}P(W_1)=P(\omega=1)P(W_1|\omega=1)+P(\omega=2)P(W_1|\omega=2)=\frac{1}{2}(P(W_1|\omega=1)+P(W_1|\omega=2))=\frac{1}{2}(p_1+p_2) \end{align*}$

因此 $\mathcal{B}$ 的优势为 $PrgAdv[\mathcal{B},\mathcal{G}]=\frac{1}{2}|p_0-p_2|$ ，从而同样有 $\mathcal{G}^\prime$ 的敌手优势是可忽略的。现在将情况扩展到一般的 $n$ 上，我们定义 $n+1$ 个attack game，Game i( $0\le\up{i}\le n$ )如下定义：

Game i：

$\mathcal{C}$ 分别选取 $r_1\xleftarrow{R}\{0,1\}^L,\cdots,r_i\xleftarrow{R}\{0,1\}^L$ 以及 $r_{i+1}=\mathcal{G}(s_{i+1}),\cdots,r_n=\mathcal{G}(s_n)$ 组成 $(r_1,\cdots,r_n)$ 发送给敌手 $\mathcal{A}$ ；

$\mathcal{A}$ 向 $\mathcal{C}$ 返回一个比特 $b^\prime$ $\in\{0,1\}$ ；

有了attack game的定义以后，令 $p_0,\cdots,p_n$ 分别代表 $n+1$ 个game中敌手返回1的概率，那么显然 $\mathcal{G}^\prime$ 的敌手优势为 $|p_0-p_n|$ 。还是通过上面的论证思路，在 $\mathcal{B}_1,\cdots,\mathcal{B}_n$ 再包上一层 $\mathcal{B}$ ，通过随机选取 $\omega\in\{1,\cdots,n\}$ 来决定使用哪个真正的敌手，那么我们就有

$\begin{align*} P(W_0)=\sum\limits_{i=1}^n P(W_0|\omega=i)P(\omega=i)=\frac{1}{n}\sum\limits_{i=1}^n P(W_0|\omega=i)=\frac{1}{n}\sum\limits_{i=1}^np_{i-1} \end{align*}$

$\begin{align*} P(W_1)=\sum\limits_{i=1}^n P(W_1|\omega=i)P(\omega=i)=\frac{1}{n}\sum\limits_{i=1}^n P(W_1|\omega=i)=\frac{1}{n}\sum\limits_{i=1}^np_{i} \end{align*}$

从而我们有 $\mathcal{G}$ 的敌手优势为 $PrgAdv[\mathcal{B},\mathcal{G}]=\frac{1}{n}|p_0-p_n|$ 。而因为 $n$ 有一个关于安全参数的多项式上界，因此 $\mathcal{G}^\prime$ 的敌手优势为 $n\cdot PrgAdv[\mathcal{B},\mathcal{G}]$ 依然是可忽略的，从而得到 $\mathcal{G}^\prime$ 还是安全的。 $\blacksquare$

PRG的串行扩展

上面展示的是PRG的一种并行扩展方式，不过这种方式需要 $n$ 个输入种子，因此其扩展率（输出比特长度与输入比特长度之比）与原始的PRG是一样的，并未得到提高。Blum和Micali提出了一种PRG的串行扩展方式，它把 $\mathcal{G}$ 扩展为一个如下工作的 $\mathcal{G}^\prime$ ：从最初输入 $s_0$ 开始，得到 $\mathcal{G}$ 的输出 $(r_1,s_1)$ ，然后用 $s_1$ 作为 $\mathcal{G}$ 新的输入，得到新的输出后和上一个输出拼到一起得到 $(r_1,r_2,s_2)$ ，以此类推， $n$ 步之后得到最终的输出 $(r_1,\cdots,r_n,s_n)$ ，那么 $(r_1,\cdots,r_n)$ 就是最终生成的伪随机串。注意这里的 $\mathcal{G}$ 和原始的PRG有所不同，原来的PRG输入空间为 $\mathcal{S}$ 输出空间为 $\mathcal{R}$ ，而这里的 $\mathcal{G}$ 输出空间为 $\mathcal{R}\times\mathcal{S}$ 。有了这种串行构造方式以后， $\mathcal{G}^\prime$ 的安全性是怎样的呢？我们可以看出，并行和串行最主要的区别实际上就是每一轮的输入产生方式不同，但是如果假设 $\mathcal{G}$ 安全的话，这个区别是可忽略的，因此从直观上来看，串行构造的 $\mathcal{G}^\prime$ 的安全性应该和并行构造差不多。事实上，我们有如下定理：

定理2：如果存在一个安全的PRG $\mathcal{G}$ ，那么由此串行构造的 $\mathcal{G}^\prime$ 也是安全的。

证明：这个定理的证明和定理1的证明是很类似的，都是通过在一系列attack game中不断将一个输出替换为真正的随机串，从而得到最终结果。具体来说，第i个game如下定义：

Game i：

$\mathcal{C}$ 分别选取 $r_1\xleftarrow{R}\{0,1\}^L,\cdots,r_i\xleftarrow{R}\{0,1\}^L,s_i\xleftarrow{R}\{0,1\}^l$ 以及 $(r_{i+1},s_{i+1})=\mathcal{G}(s_i),\cdots,(r_{i+1},\cdots,r_n,s_n)=\mathcal{G}(s_{n-1})$ 组成 $(r_1,\cdots,r_n)$ 发送给敌手 $\mathcal{A}$ ；

$\mathcal{A}$ 向 $\mathcal{C}$ 返回一个比特 $b^\prime$ $\in\{0,1\}$ ；