基于置换集合的伪随机生成器构造

【基本思想】

基于置换集合的伪随机生成器构造，是在基于单向置换的伪随机生成器的基础上的推广，其不再使用固定的单个置换 $f$，而是从一个单向置换集合（Collection of One-way Permutations）中随机选择一个置换，然后进行迭代。

这种构造可以直接应用于多个经典密码学假设，例如：

• 离散对数问题
• RSA 求逆困难性
• Blum 整数分解困难性

【构造】

定义单向置换集合的三个算法分别为索引生成算法 $I$、定义域采样算法 $D$、置换计算算法 $F$，$I$ 负责生成随机索引 $i$，对于每个索引 $i$，$D(i)$ 在置换 $f_i$ 的定义域 $D_i$ 上均匀分布。

设多项式 $\mathrm{poly}’(n)$ 是算法 $I$ 和 $D$ 使用随机比特数量的多项式上界，对于种子 $r\in\{0,1\}^{\mathrm{poly}’(n)}$，用 $I(1^n,r)$ 表示算法 $I$ 在输入 $1^n$ 时的输出 $i$。类似的，对于种子 $s\in \{0,1\}^{\mathrm{poly}’(n)}$，用 $D(i,s)$ 输出 $D_i$ 中的随机元素。

由此，有如下构造：

Construction：设 $(I,D,F)$ 是一个单向置换集合，$B$ 是该集合对应的硬核谓词，$\mathrm{poly}(\cdot)$ 是任意多项式。对于 $n\in\mathbb{N}$，种子 $r,s\in\{0,1\}^{\mathrm{poly}’(n)}$，定义：

$$G(r,s)=\sigma_1\cdots\sigma_{\mathrm{poly}(n)}$$

索引 $i=I(1^n,r)$ 通过索引生成算法 $I$ 与种子 $r$ 生成，初始点 $s_0=D(i,s)$ 通过定义域采样算法 $D$ 与种子 $s$ 生成，并且对于每一个 $1\leq j\leq \mathrm{poly}(|s|)$ 都有：

$$\sigma_j=B(i,s_{j-1}),\quad s_j=f_i(s_{j-1})$$

具体来说，对于置换计算算法 $F(i,x)=f_i(x)$，算法 $G$ 的操作如下：输入 $(r,s)$，选择生成索引 $i=I(1^n,r)$ 与初始点 $s_0=D(i,s)$，对于 $j=1,\cdots,\mathrm{poly}(n)$，计算 $\sigma_j=B(i,s_{j-1}),s_j=f_i(s_{j-1})$，最后输出 $\sigma_1\sigma_2\cdots\sigma_{\mathrm{poly}(n)}$

该构造包含两个随机过程：

1. 随机选择置换：利用种子 $r$ 计算索引 $i=I(1^n,r)$，并从置换集合中选择 $f_i$，因此不同随机种子对应不同置换
2. 随机选择初始状态：利用种子 $s$ 计算 $s_0=D(i,s)$，得到 $D_i$ 中的随机起点

算法 $G$ 的核心是函数 $f_i$ 在起始点 $s_0$ 上重复引用以及为每个结果元素输出一个硬核谓词。也就是说，在每一步 $\sigma_j=B(i,s_{j-1})$ 中，如果知道 $s_{j-1}$，那么就可以计算 $\sigma_j$，但是攻击者只能看到 $s_j=f_i(s_{j-1})$，如果 $B$ 是 $f_i$ 的硬核谓词，那么给定 $f_i(s_{j-1})$ 无法预测 $B(i,s_{j-1})$，因此输出序列具有伪随机性。

此外，算法 $G$ 输出 $\mathrm{poly}(n)$ 个比特，但是种子长度为 $2\mathrm{poly}’(n)$，因为输入 $r,s\in\{0,1\}^{\mathrm{poly}’(n)}$，所以种子长度为 $2\mathrm{poly}’(n)$。因此，为了保证真正扩展，需要满足：$\mathrm{poly}(n)>2\mathrm{poly}’(n)$

【命题与定理】

基于置换集合的伪随机生成器构造有如下命题与定理。

Proposition：设 $n,t$ 为整数，对于 $i\in I(1^n)$ 以及 $x\in D_i$，定义

$$G_i^t(x) = B(i,x) \cdot B(i,f_i(x)) \cdots B(i,f_i^{t-1}(x))$$

其中，对于任意 $j>0$，满足 $f_i^0(x)=x$，并且 $f_i^{j+1}(x) = f_i^j(f_i(x))$

令 $I_n$ 表示随机变量 $I(1^n)$，$X_n=D(I_n)$ 表示均匀分布在 $D_{I_n}$ 的随机变量，则对于每个多项式 $\mathrm{poly}(n)$，以下两个系综在多项式时间不可区分

$$\{(I_n, G_{I_n}^{\mathrm{poly}(n)}(X_n), f_{I_n}^{\mathrm{poly}(n)}(X_n)) \}_{n\in N},\quad \{ (I_n, U_{\mathrm{poly}(n)}, f_{I_n}^{\mathrm{poly}(n)}(X_n)) \}_{n\in N}$$

该命题说明，判别算法除了要考虑 $\mathrm{poly}(n)$ 位长序列外，还要得到 $G$ 的置换索引 $i$ 和最终状态 $f_i^{\mathrm{poly}(n)}(X_n)$，即使攻击者得到这些额外的信息，也无法区分真正输出 $G_i^{\mathrm{poly}(n)}(X_n)$ 和随机 $\mathrm{poly}(n)$ 位字符串。

该命题可以直接推出以下定理

Theorem：设 $(I,D,F),B,\mathrm{poly}(n),\mathrm{poly}’(n),G$，满足上述构造，同时 $\mathrm{poly}(n)>2\mathrm{poly}’(n)$，并且对于 $I$ 生成的每个索引 $i$，随机变量 $D(i)$ 在 $D_i$ 上均匀分布，那么 $G$ 是一个伪随机生成器。

简单来说，索引 $i=I(1^n,r)$ 通过索引生成算法 $I$ 与种子 $r$ 生成，初始点 $s_0=D(i,s)$ 通过定义域采样算法 $D$ 与种子 $s$ 生成，由于 $D(i)$ 均匀分布于 $D_i$，因此 $s_0$ 等价于 $X_n=D(I_n)$，随后经过 $G(r,s)$ 的迭代，输出 $G_{I_n}^{\mathrm{poly}(n)}(X_n)$，因此构造实际产生的系综是 $\{(I_n,G_{I_n}^{\mathrm{poly}(n)}(X_n))\}$

而命题证明的是更强的结论，即使泄漏索引 $i$ 与最终状态 $f_i^{\mathrm{poly}(n)}(X_n)$，系综 $\{(I_n, G_{I_n}^{\mathrm{poly}(n)}(X_n), f_{I_n}^{\mathrm{poly}(n)}(X_n)) \}_{n\in N}$ 和 $\{ (I_n, U_{\mathrm{poly}(n)}, f_{I_n}^{\mathrm{poly}(n)}(X_n)) \}_{n\in N}$ 仍然是不可区分的。

因此，即使去掉最终状态 $f_i^{\mathrm{poly}(n)}(X_n)$，仍然是安全的，所以 $\{G_{I_n}^{\mathrm{poly}(n)}(X_n)\}$ 与 $U_{\mathrm{poly}(n)}$ 不可区分，即 $G$ 是伪随机的。

此外，上述命题与定理可以进一步放宽：

1. 不要求 $D(i)$ 完全均匀，只需要 $D(i)$ 与均匀分布 $U(D_i)$ 在统计距离上接近
2. 不要求所有 $i$ 都满足条件，只需要除了一个可忽略比例的索引之外成立即可。

【命题证明】

基本思路

该命题的证明与基于单向置换的伪随机生成器构造中的构造命题类似。

首先反转输出顺序，定义 $\bar G_i^t(x)$ 为 $G_i^t(x)$ 的逆序，即：

$$\bar G_i^t(x)=B(i,f_i^{t-1}(x)) \cdot B(i,f_i^{t-2}(x)) \cdots B(i,x)$$

由于只是改变比特顺序，所以当且仅当 $\bar G_i^t(x)$ 是伪随机时，$G_i^t(x)$ 是伪随机的。因此，只需要证明即使给定 $I_n$ 和 $f_{I_n}^{\mathrm{poly}(n)}(X_n)$，$\bar G_{I_n}^{p(n)}(X_n)$ 在多项式时间内不可预测，即可证明命题。

反证假设

假设存在概率多项式时间算法 $A’$ 可以预测 $\bar G_{I_n}^{\mathrm{poly}(n)}(X_n)$ 的下一位，即存在多项式 $\mathrm{poly}’(n)$ 对于无限多个 $n$ 满足：

$$P[ A'(1^{\mathrm{poly}(n)},\bar G_{I_n}^{\mathrm{poly}(n)}(X_n)) = \mathrm{next}_{A'} (\bar G_{I_n}^{\mathrm{poly}(n)}(X_n)) ] > \frac12+\frac{1}{\mathrm{poly}'(n)}$$

那么，只需要构造算法 $A’’$，在给定 $(i,f_i(x))$ 以不可忽略的高于 $\frac{1}{2}$ 的概率预测 $B(i,x)$ 即可得到矛盾。

具体来说，令算法 $A’’$ 输入 $y=f_i(x)\in D_i$，执行以下步骤：

1. 随机选择 $j\in\{0,1,\cdots,t-1\}$
2. 计算 $\alpha = B(i,f^{j-1}_i(y)) \cdots B(i,y)$，其中 $|\alpha|=j$
3. 随机选择 $\beta\in\{0,1\}^{t-j}$
4. 输入 $(1^t,\alpha\beta)$，调用 $A’$，并记录 $A’$ 读取输入前缀的长度 $l$、$A’$ 的输出 $\tau$
5. 如果 $l=j$，输出 $\tau$，否则随机输出一个比特

前缀分布

当输入 $X_n$ 时，对于任意选择的 $j$，算法 $A’’$ 计算

$$\alpha = B(i,f_i^{j-1}(y)) \cdots B(i,y)$$

令 $y=X_n$，则：

$$\alpha = B(i,f_i^{j-1}(X_n)) \cdots B(i,X_n)$$

由于 $f_i$ 是 $D_i$ 上的置换，因此如果 $X_n\sim D_i$，那么 $f_i(X_n)$ 仍然服从 $D_i$。所以 $B(i,f_i^{j-1}(X_n)) \cdots B(i,X_n)$ 和 $B(i,f_i^{t-1}(X_n)) \cdots B(i,f_i^{t-j}(X_n))$ 具有相同分布。而后者正是 $\bar G_i^t(X_n)$ 的前 $j$ 位。

因此，$\alpha$ 和 $\bar G_i^t(X_n)$ 的前 $j$ 位分布一致。

成功概率分析

设 $R_j(y)$ 是一个随机过程，给定输入 $(i,y)$，输出 $B(i,f_i^{j-1}(y)) \cdots B(i,y)\cdot r$，其中 $r$ 在 $U_{t-j}$ 中均匀分布。

令 $L_{A’}(\gamma)$ 表示算法 $A’$ 输入 $(1^t,\gamma)$ 时读取的前缀长度，由于 $A’$ 只依赖它读取的部分，因此 $\mathrm{next}_{A’}(\gamma)$ 等于第 $L_{A’}(\gamma)+1$ 位。

令 $J$ 表示算法 $A’’$ 中第一步随机选择的 $j$，$U_1$ 表示第五步中随机输出的比特。如果 $L_{A’}(\gamma)=J$，那么 $A’’$ 输出 $A’(1^t,\gamma)$，否则输出随机比特。

因此，有：

$$\begin{aligned} P[ A''(f_{I_n}(X_n)) = B(I_n,X_n) ] =& P[ A'(1^t,R_J(f_{I_n}(X_n))) = B(I_n,X_n) \\ &\land L_{A'}(R_J(f_{I_n}(X_n)))=J ] \\ &+ P[ U_1=B(I_n,X_n) \land L_{A'}(R_J(f_{I_n}(X_n)))\neq J ] \end{aligned}$$

由于 $R_J(f(U_n))$ 的前 $J$ 位与 $G’(U_n)$ 的前 $J$ 位分布相同，因此上式可化简为：

$$\begin{aligned} P[ A''(f_{I_n}(X_n)) = B(I_n,X_n) ] =& P[ A'(1^t,\bar G_{I_n}^{t}(X_n)) = \mathrm{next}_{A'} (\bar G_{I_n}^{t}(X_n)) \\ &\land J=L_{A'}(\bar G_{I_n}^{t}(X_n)) ] \\ &+ \frac{1}{2}P[ J\neq L_{A'}(\bar G_{I_n}^{t}(X_n)) ] \end{aligned}$$

考虑到事件 $A’(1^t,G’(U_n)) = \mathrm{next}_{A’}(G’(U_n))$ 与 $J$ 独立，因此对于上式中的第一项，有：

$$\begin{aligned} & P[ A'(1^t,\bar G_{I_n}^{t}(X_n)) = \mathrm{next}_{A'} (\bar G_{I_n}^{t}(X_n)) \land J=L_{A'}(\bar G_{I_n}^{t}(X_n)) ] \\ = & P[ A'(1^t,\bar G_{I_n}^{t}(X_n)) = \mathrm{next}_{A'} (\bar G_{I_n}^{t}(X_n)] \cdot P[J=L_{A'}(\bar G_{I_n}^{t}(X_n)) ] \end{aligned}$$

进一步，假设 $A’$ 不会读取全部 $t$ 位输入。因此：

$$L_{A'}(\bar G_{I_n}^{t}(X_n)) \in \{0,1,\cdots,t-1\}$$

而 $J$ 均匀随机选择 $0,\cdots,t-1$，所以有：

$$P[J=L_{A'}(\bar G_{I_n}^{t}(X_n))] = \frac{1}{t}$$

因此，成功概率可化简为：

$$\begin{align*} P[ A''(f_{I_n}(X_n)) = B(I_n,X_n) ] =& \frac{1}{t} P[ A'(1^t,\bar G_{I_n}^{t}(X_n)) = \mathrm{next}_{A'} (\bar G_{I_n}^{t}(X_n)] \\ &+ \frac{1}{2} \cdot (1-\frac{1}{t}) \\ \end{align*}$$

将 $t=\mathrm{poly}(n)$ 与反证假设代入，有：

$$\begin{aligned} P[A''(f_{I_n}(X_n)) = B(I_n,X_n)] &\geq \frac{1}{\mathrm{poly}(n)} \left( \frac{1}{2}+\frac{1}{\mathrm{poly}'(n)} \right) + \frac{1}{2}\left( 1-\frac{1}{\mathrm{poly}(n)} \right) \\ &= \frac{1}{2}+ \frac{1}{\mathrm{poly}(n)\mathrm{poly}'(n)} \end{aligned}$$

矛盾推出

因此，算法 $A’’$ 可以根据 $f_i(x)$ 预测 $B(i,x)$，成功概率为至少为 $\frac{1}{2}+ \frac{1}{\mathrm{poly}(n)\mathrm{poly}’(n)}$，即比随机猜测 $\frac{1}{2}$ 高出不可忽略优势。

但是，根据假设 $B$ 是硬核谓词，任何多项式时间算法都不能做到这一点。

产生矛盾。因此，不存在预测算法 $A’$，所以 $\bar G_i^t(x)$ 不可预测。

而 $\bar G_i^t(x)$ 是伪随机生成器，且 $G_i^t(x)$ 和 $\bar G_i^t(x)$ 只是输出顺序不同。因此，$G_i^t(x)$ 也是伪随机生成器。

【伪随机生成器的具体实例】

上述构造给出了一个基于单向置换集合的通用伪随机生成器构造。

该构造的核心形式为：

1. 随机选择一个置换 $f_i$
2. 从随机起点开始不断迭代 $x,\ f_i(x),\ f_i^2(x),\cdots$
3. 在每个状态上输出硬核谓词 $B(i,x)$

因此，只要某个密码学困难问题能够提供一个单向置换集合与对应的硬核谓词，就可以得到伪随机生成器。

基于离散对数困难性

基础假设

假设离散对数集合是单向的，即 $G^x\bmod P$ 无法有效求出 $x$，其中 $P$ 是素数，$G$ 是模 $P$ 乘法群中的生成元。

在该假设下，存在一个硬核谓词 $B_P$，其对应问题为给定素数 $P$、模 $P$ 乘法群中的生成元 $G$、群中的元素 $Y$，判断是否存在 $0\leq x\leq \frac{P}{2}$，满足：

$$Y\equiv G^x\pmod P$$

换句话说，对于 $Y=G^x\bmod P$，攻击者无法判断 $x$ 是否位于 $[0,\frac{P}{2}]$ 范围内。

因此，$B_P(Y)$ 构成离散对数集合的硬核谓词。

生成器构造

随机种子用于选择素数 $P$、生成元 $G$、群元素 $Y$，然后不断迭代：

$$Z=G^Z\bmod P$$

最后输出序列：

$$B_P(Y),B_P(G^Y\bmod P),B_P(G^{G^Y\bmod P}\bmod P),\cdots$$

即：

$$B_P(Y), B_P(f(Y)), B_P(f^2(Y)), \cdots$$

其中，$f(Z)=G^Z\bmod P$

每一步的状态更新 $Z= G^Z\bmod P$ 容易计算，但是如果攻击者只能看到 $G^Z\bmod P$，则无法预测 $B_P(Z)$，否则可以解决离散对数相关困难问题。

因此，输出的 $B_P(Z)$ 具有伪随机性。

基于 RSA 求逆困难性

基础假设

假设 RSA 集合是单向的，即给定 $X^e\bmod N$，无法有效求出 $X$，其中，$N=P\cdot Q$

在 RSA 单向假设下，最低有效位构成 RSA 集合的硬核谓词，即给定 $X^e\bmod N$，无法预测 $X$ 的最低有效位。

生成器构造

随机种子选择 $P,Q$ 两个素数，计算 $N=P\cdot Q$，RSA 公钥指数选择 $e$，满足：

$$\gcd(e,\phi(N))=1$$

其中，$\phi(N) = (P-1)(Q-1)$

初始元素选择 $X\in\mathbb{Z}_N^{*}$，然后不断迭代：

$$Z= Z^e\bmod N$$

有状态序列：

$$X,X^e\bmod N,X^{e^2\bmod\phi(N)}\bmod N,X^{e^3\bmod\phi(N)}\bmod N,\cdots$$

最后输出：

$$\mathrm{lsb}(X),\mathrm{lsb}(X^e\bmod N),\mathrm{lsb}(X^{e^2\bmod\phi(N)}\bmod N),\mathrm{lsb}(X^{e^3\bmod\phi(N)}\bmod N),\cdots$$

其中，$\mathrm{lsb}(\cdot)$ 为最低有效位。

每一步 RSA 计算 $Z^e\bmod N$ 容易，但是由 $Z^e\bmod N$ 无法恢复 $Z$，因此无法预测 $\mathrm{lsb}(Z)$，所以输出序列具有伪随机性。

基于 Blum 整数分解困难性

基础假设

假设 Blum 整数分解困难，即给定 $N=P\cdot Q$，$P,Q$ 均为大素数，并且 $P\equiv Q\equiv3\pmod4$，攻击者无法恢复 $P,Q$

对于 $N=P\cdot Q$，其中 $P,Q\equiv3\pmod4$，平方函数 $Z = Z^2\bmod N$，在二次剩余集合 $QR_N$ 上形成一个置换。

在该假设下最低有效位构成模平方函数 $Z= Z^2\bmod N$ 的硬核谓词。

生成器构造

随机种子选择 $P,Q$ 两个素数，满足 $P,Q\equiv3\pmod4$，模数为 $N=P\cdot Q$

初始元素选择 $X\in\mathbb{Z}_N^{*}$，然后不断迭代：

$$Z= Z^2\bmod N$$

有状态序列：

$$X,X^2\bmod N,X^{2^2\bmod\phi(N)}\bmod N,X^{2^3\bmod\phi(N)}\bmod N,\cdots$$

最后输出：

$$\mathrm{lsb}(X),\mathrm{lsb}(X^2\bmod N),\mathrm{lsb}(X^{2^2\bmod\phi(N)}\bmod N),\mathrm{lsb}(X^{2^3\bmod\phi(N)}\bmod N),\cdots$$

每一步的平方运算 $Z^2\bmod N$ 容易计算，但是如果不知道 $P,Q$，则无法有效反平方。因此，无法预测 $\mathrm{lsb}(Z)$，所以输出序列是伪随机的。

随机素数生成问题

以上三个实例都需要随机生成大素数，因此生成素数算法使用的随机比特数量越少越好。

传统方法生成 $n$ 位随机素数需要 $O(n^3)$ 个随机比特，而目前更加随机高效的算法只需要 $O(n)$ 个随机比特。

因此，在实际实现伪随机生成器时，随机素数生成过程本身的随机性消耗也是需要考虑的问题。