拟随机和之前理论密码学的伪随机其实原理一样，只是有些细微处的差别，首先伪随机听起来不像是真正的随机，像是人为构造的假的随机一样，但拟随机内容多一点，像是模拟一个真随机，所以真随机也可以叫成拟随机，但把伪随机叫成真随机是有些奇怪的，后面我们均考虑拟随机。另外无论是拟随机函数还是拟随机置换都是对一个函数族来说的，并不是一个单个的函数是拟随机。

函数族

    设$l_1,l_2>0$是正整数，是安全参数$\lambda$的多项式，函数族$\mathcal{F}$的定义如下：

$$\mathcal{F}:=\{F_s\}_{s\in S(1^\lambda)} \subseteq \Gamma_{l_1,l_2}$$ $$\Gamma_{l_1,l_2}:=\{f|f:\{0,1\}^{l_1} \rightarrow \{0,1\}^{l_2}\}$$

其中$\Gamma_{l_1,l_2}$是从$\{0,1\}^{l_1}$到$\{0,1\}^{l_2}$的所有函数构成的集合，$S$是一个下标集合。
    需要注意的是，这里$l_1,l_2$都是安全参数$\lambda$的多项式，所以不同的$\lambda$，$\Gamma_{l_1,l_2}$里的函数的定义域和值域都会发生变化，当然函数的个数也会发生变化，$\{0,1\}^{l_1} \rightarrow \{0,1\}^{l_2}$上的函数一共有$2^{l_22^{l_1}}$个。另外函数族$\mathcal{F}$的下标集合$S$必然也是与$\lambda$相关的，记为$S(1^\lambda)$，所以$\lambda$变化时，$\{F_s\}_{s\in S(1^\lambda)}$里函数的个数也在发生变化，当然，$S$与$\lambda$到底是什么关系就与具体的函数族的构造相关。

拟随机函数族

    一个函数族$\mathcal{F}:=\{F_s\}_{s\in S(1^\lambda)} \subseteq \Gamma_{l_1,l_2}$称为是拟随机函数族，如果对于任意$PPT$敌手$\mathcal{A}$，存在可忽略函数$negl$，使得：

$$Adv_{\mathcal{A},\mathcal{F}}^{PRF}=|Pr[ s\leftarrow S:\mathcal{A}^{F_S}(1^\lambda)=1]-Pr[ f\leftarrow \Gamma_{l_1,l_2}:\mathcal{A}^{f}(1^\lambda)=1]| \leq negl(\lambda)$$

这里的$\mathcal{A}^{F_S}$和$mathcal{A}^f$是说算法$\mathcal{A}$黑盒地调用函数$F_S$和$f$，即$oracle$形式的调用，算法$\mathcal{A}$给函数$oracle$一个自变量，函数$oracle$返回一个函数值，且相同的询问回复相同的值。这个是非常显然的，因为$F_S$和$f$都是$\{0,1\}^{l_1} \rightarrow \{0,1\}^{l_2}$上的函数，光自变量的值就有$2^{l_1}$个，$PPT$的算法$\mathcal{A}$根本无法完整存储这个函数，只能以$oracle$形式进行调用。

置换族

    置换族的定义和函数族的定义完全类似，首先整数$l=l_1=l_2$，是安全参数$\lambda$的多项式，置换族$\mathcal{P}$的定义如下：

$$\mathcal{P}:=\{P_t\}_{t\in T(1^\lambda)} \subseteq \Pi_l$$ $$\Pi_l:=\{\pi|\pi:\{0,1\}^l \rightarrow \{0,1\}^l\}$$

其中$\pi$是置换，$T$与$S$一样是有效抽样的集合，或者说下标的集合，其余关于安全参数$\lambda$的东西都完全类似。

拟随机置换族

    一个置换族$\mathcal{P}:=\{P_t\}_{t\in T(1^\lambda)} \subseteq \Pi_l$称为是$\{0,1\}^{l}$上的拟随机置换族，如果对于任意的$PPT$敌手$\mathcal{A}$，存在可忽略函数$negl$，使得：

$$Adv_{\mathcal{A},\mathcal{P}}^{PRF}=|Pr[ t\leftarrow T:\mathcal{A}^{P_t}(1^\lambda)=1]-Pr[ \pi \leftarrow \Pi_l:\mathcal{A}^{\pi}(1^\lambda)=1]| \leq negl(\lambda)$$

    由此我们给出了拟随机置换族和拟随机函数族的定义，实际上这两个概念是存在一定联系的，集中表现在下面的定理中。

对任意整数$l>0$，$l$是安全参数$\lambda$的一个多项式，集合$\{0,1\}^{l}$上的拟随机置换族一定是拟随机函数族

    接下来的主要工作就是证明这个定理，这个定理看起来也比较直观，本身置换就是函数的一种，那这个定理就是说当安全参数$\lambda$逐渐变大时，即使我们仅仅考虑置换函数构成的拟随机置换族，它也可以看成是一个拟随机的函数族，也就是说仅仅是占函数总量很少的置换构成的函数族，$PPT$的算法就已经无法有效分辨了它是置换还是普通函数了，$PPT$的算法能力还是太弱了。
    首先对任意一个$PPT$的算法$\mathcal{A}$，有下式成立：

$$|Pr[t\leftarrow T :\mathcal{A}^{P_t}(1^\lambda)=1]-Pr[ f\leftarrow \Gamma_l:\mathcal{A}^{f}(1^\lambda)=1]|\\ \leq |Pr[t\leftarrow T :\mathcal{A}^{P_t}(1^\lambda)=1]-Pr[ \pi \leftarrow \Pi_l:\mathcal{A}^{\pi}(1^\lambda)=1]|+|Pr[ \pi \leftarrow \Pi_l:\mathcal{A}^{\pi}(1^\lambda)=1]-Pr[ f\leftarrow \Gamma_l:\mathcal{A}^{f}(1^\lambda)=1]| \\$$

根据拟随机置换族的定义，必有$|Pr[t\leftarrow T :\mathcal{A}^{P_t}(1^\lambda)=1]-Pr[ \pi \leftarrow \Pi_l:\mathcal{A}^{\pi}(1^\lambda)=1]| \leq negl_1(\lambda)$，代入上式就有：

$$|Pr[t\leftarrow T :\mathcal{A}^{P_t}(1^\lambda)=1]-Pr[ f\leftarrow \Gamma_l:\mathcal{A}^{f}(1^\lambda)=1]|\\ \leq |Pr[t\leftarrow T :\mathcal{A}^{P_t}(1^\lambda)=1]-Pr[ \pi \leftarrow \Pi_l:\mathcal{A}^{\pi}(1^\lambda)=1]|+|Pr[ \pi \leftarrow \Pi_l:\mathcal{A}^{\pi}(1^\lambda)=1]-Pr[ f\leftarrow \Gamma_l:\mathcal{A}^{f}(1^\lambda)=1]| \\ \leq negl_1(\lambda)+|Pr[ \pi \leftarrow \Pi_l:\mathcal{A}^{\pi}(1^\lambda)=1]-Pr[ f\leftarrow \Gamma_l:\mathcal{A}^{f}(1^\lambda)=1]$$

所以只需要证明有可忽略函数$negl_2(\lambda)$使得$|Pr[ \pi \leftarrow \Pi_l:\mathcal{A}^{\pi}(1^\lambda)=1]-Pr[ f\leftarrow \Gamma_l:\mathcal{A}^{f}(1^\lambda)=1] |\leq negl_2(\lambda)$成立即可，可以发现，这个式子代表着集合$\{0,1\}^{l}$上的函数族和置换族是不可区分的，接下来就证这个式子。

    要证明这个式子，就要用到实验序列的方法，首先算法$\mathcal{A}$是多项式时间的算法，所以可以假设$\mathcal{A}$至多询问$q$次$oracle$，$q$是一个多项式，因为用相同的值询问时，$oracle$必然返回相同的值，所以可以提前假设算法$\mathcal{A}$的$q$次询问必不重复。由此我们给出实验序列如下：

$$Exp_1(\lambda): \\ \pi \leftarrow \Pi_l \\ r \leftarrow R \\ x_i \leftarrow \mathcal{A}(1^\lambda,r,Y_{1 \cdots i-1}) \in \{0,1\}^{l}(i=1\cdots q) \\ Y_i \leftarrow \pi(x_i)(i=1\cdots q) \\ b \leftarrow \mathcal{A}(1^\lambda,r,Y_{1 \cdots q}) \in \{0,1\} \\ output \quad b$$

$$Exp_2(\lambda): \\ Y_1 \cdots Y_q \leftarrow \{0,1\}^{l} \\ r \leftarrow R \\ x_i \leftarrow \mathcal{A}(1^\lambda,r,Y_{1 \cdots i-1}) \in \{0,1\}^{l}(i=1\cdots q) \\ if Y_i \notin Y_{ 1 \cdots i-1} then Y_i to \mathcal{A}, else Y_i \leftarrow \{0,1\}^{l} \backslash Y_{1\cdots i-1}(i=1\cdots q)\\ b \leftarrow \mathcal{A}(1^\lambda,r,Y_{1 \cdots q}) \in \{0,1\} \\ output \quad b$$

$$Exp_3(\lambda): \\ \pi \leftarrow \Pi_l \\ r \leftarrow R \\ x_i \leftarrow \mathcal{A}(1^\lambda,r,Y_{1 \cdots i-1}) \in \{0,1\}^{l}(i=1\cdots q) \\ Y_i to \mathcal{A} \\ b \leftarrow \mathcal{A}(1^\lambda,r,Y_{1 \cdots q}) \in \{0,1\} \\ output \quad b$$

$$Exp_4(\lambda): \\ f \leftarrow \Gamma_l \\ r \leftarrow R \\ x_i \leftarrow \mathcal{A}(1^\lambda,r,Y_{1 \cdots i-1}) \in \{0,1\}^{l}(i=1\cdots q) \\ Y_i \leftarrow f(x_i) (i=1\cdots q) \\ b \leftarrow \mathcal{A}(1^\lambda,r,Y_{1 \cdots q}) \in \{0,1\} \\ output \quad b$$

    这四个实验是相互联系的，首先$Exp_1(\lambda)$是从$\Pi_l$里随机挑选了一个置换作为$oracle$回复算法$\mathcal{A}$的询问，因为假设算法$\mathcal{A}$的询问不相同，根据置换的特点，可知$oracle$的回复必然也互不相同。然而$Exp_2(\lambda)$是将挑选置换作为$oracle$这一步省略掉了，直接随机挑选了多项式个函数值$Y_1 \cdots Y_q \leftarrow \{0,1\}^{l}$，这些函数值可能有相同的，但$Exp_2(\lambda)$里做了特殊处理，它在$oracle$的回复做了手脚，一般是直接以$Y_i$回复$x_i$的询问，但$Exp_2(\lambda)$里会先比较$Y_i$跟前$i-1$次的回复有没有重复的，如果有重复，就再重新随机挑选一个跟前$i-1$次回复不重复的$Y_i$回复$\mathcal{A}$，如果不重复，就直接回复原$Y_i$。
    所以$Exp_2(\lambda)$最终得到的$q$次回复完全就是$q$个互不相同的随机串，这与$Exp_1(\lambda)$实际上得到的结果是相同的，首先$Exp_1(\lambda)$得到的结果必不相同，这是由置换的性质决定的，但为什么是随机的呢？因为在$Exp_1(\lambda)$的$oracle$里，置换$\pi \leftarrow \Pi_l$是随机选的，那$\mathcal{A}$得到任何一个随机串$r$的概率都是等可能的:

$$Pr[r]=Pr[\pi_1]Pr[r=\pi(x)|\pi=\pi_1]+\cdots+Pr[\pi_n]Pr[r=\pi(x)|\pi=\pi_n]=\frac{1}{2^n}(Pr[\pi_1]+\cdots+Pr[\pi_n])=\frac{1}{2^n}$$

所以$Exp_2(\lambda)$与$Exp_1(\lambda)$这两个实验里算法$\mathcal{A}$能见到的东西是一模一样的，所以必有：

$$\color{red}{Pr[Exp_1(\lambda)=1]=Pr[Exp_2(\lambda)=1]}$$

    再考虑$Exp_3(\lambda)$，实际上$Exp_3(\lambda)$和$Exp_2(\lambda)$是非常相似的，$Y_1 \cdots Y_q$都是随机取的，但$Exp_3(\lambda)$并没有考虑里面有重复的情况，直接以$Y_i$回复$x_i$的询问，而$Exp_2(\lambda)$却对出现重复时给了一个新的要求。所以，如果$Y_1 \cdots Y_q$里面不出现重复，$Exp_3(\lambda)$和$Exp_2(\lambda)$是完全一样的，都直接以$Y_i$回复$x_i$的询问，设事件$F$表示：存在$i\neq j, Y_i=Y_j$，即$F=\cup_{i\neq j}(Y_i=Y_j)$，则有：

$$(Exp_2(\lambda)=1)\land \neg F=(Exp_3(\lambda)=1)\land \neg F$$

根据概率差引理有：

$$\color{red}{|Pr[Exp_2(\lambda)=1]-Pr[Exp_3(\lambda)=1]| \leq Pr[F]}$$

这里的三个事件$Exp_2(\lambda)=1,Exp_3(\lambda)=1,F$确实是在同一个概率空间里的，因为底层都是$Y_1 \cdots Y_q$和随机数$r$的选择，在这些选择的基础下，$Exp_2(\lambda)=1$与$Exp_3(\lambda)=1$可能发生也可能不发生，事件$F$也是可能发生或者不发生。

    再考虑$Exp_4(\lambda)$，实际上$Exp_4(\lambda)$和$Exp_3(\lambda)$是非常相似的，$Exp_3(\lambda)$里的$Y_1 \cdots Y_q$是随机取的，但$Exp_4(\lambda)$只是随机从$\Gamma_l$里挑选了一个函数$f$，直接以$f(x_i)$回复$x_i$的询问。我们如果能证明对任意的$x_i$，$oracle$的回复$f(x_i)$都是一个随机值，那$Exp_4(\lambda)$和$Exp_3(\lambda)$本质上就完全没有区别，只是随机回复选取的方式不同，一个是直接选，一个是利用函数族，先随机挑选函数，再计算回复(函数值)。首先对任意的$y \in {0,1}^{l}$：

$$\begin{aligned} Pr[y=f(x_i)]&=Pr[f_1]Pr[y=f(x_i)|f=f_1]+\cdots +Pr[f_n]Pr[y=f(x_i)|f=f_n] \\ &=Pr[f_1]\color{blue}{Pr[y=f_1(x_i)]}+\cdots +Pr[f_n]\color{blue}{Pr[y=f_n(x_i)]} \\ &=Pr[f_1]+ \cdots Pr[f_{2^{l2^l-l}}] \\ &=\frac{2^{l2^l-l}}{2^{l2^l}} \\ &=\frac{1}{2^l} \end{aligned}$$

所以显然$oracle$的回复$f(x_i)$是一个随机值，$Exp_4(\lambda)$和$Exp_3(\lambda)$就是一模一样的，也就是：

$$\color{red}{Pr[Exp_3(\lambda)=1]=Pr[Exp_4(\lambda)=1]}$$

另外为什么有：

$$Pr[f_1]\color{blue}{Pr[y=f_1(x_i)]}+\cdots +Pr[f_n]\color{blue}{Pr[y=f_n(x_i)]} =Pr[f_1]+ \cdots Pr[f_{2^{l2^l-l}}]$$

此式成立呢？实际上也非常简单，因为$f_1 \cdots f_n$是函数族$\Gamma_l$里的所有元素，可以想象成一个函数对应着一个长为$l2^{l}$的二进制串，而上面的式子就是说$x_i$固定，$f_i$固定，$y$固定，则此时的$Pr[y=f(x_i)]$要么等于0，要么等于1，什么时候等于1呢？就是$f$对应的这个二进制串在$x_i$处对应的$l$个比特必须是$y$，因为$y$是固定的，这样的比特串一共有$2^{l2^l-l}$个，所以就对应着$2^{l2^l-l}$个1，另外$f$是随机选取的函数，所以一定有$Pr[f]=\frac{1}{2^{l2^l}}$，进而就有上面的等式成立了。其实这些在之前的理论密码学里老师也讲到过一些，只是没有给出标准的证明而已。

    所以根据上面标红的几个概率等式，我们可以得到下面的概率等式：

$$|Pr[Exp_1(\lambda)=1]-Pr[Exp_4(\lambda)=1]| \leq Pr[F]$$

另外显然有：

$$Pr[ \pi \leftarrow \Pi_l:\mathcal{A}^{\pi}(1^\lambda)=1]=Pr[Exp_1(\lambda)=1] \\ Pr[ f\leftarrow \Gamma_l:\mathcal{A}^{f}(1^\lambda)=1]=Pr[Exp_4(\lambda)=1]$$

带入上式既有：

$$|Pr[ \pi \leftarrow \Pi_l:\mathcal{A}^{\pi}(1^\lambda)=1]-Pr[ f\leftarrow \Gamma_l:\mathcal{A}^{f}(1^\lambda)=1]| \leq Pr[F]$$

这就非常接近我们的目标了，只要我们能证明$Pr[F]$是一个可忽略的函数就可以了，实际上有：

$$\begin{aligned} Pr[F]&=Pr[\cup_{i\neq j}(Y_i=Y_j)] \leq \sum_{i\neq j}Pr[(Y_i=Y_j)] \\ &=\sum_{i\neq j} 2^{-l}=C_q^2 \cdot 2^{-l} \leq \frac{q^2}{2^{l+1}} \end{aligned}$$

这里$q$是多项式大小的，则显然$\frac{q^2}{2^{l+1}}$是关于安全参数$\lambda$的可忽略函数，至此，全部证毕。

总结

    这个定理看上去非常简单，实际上理论密码学课上老师也证明过，但是老师并没有详细的证明，但现在我明白了这个定理的详细证明，也是利用了实验序列的思想，并没有那么的直白。本质上是利用了不可区分的传递性搭建了桥梁，但困难的地方在于，如何把一个模糊的认为正确的证明过程用标准的密码学语言和数学语言表述出来，这也是需要慢慢培养的。