科普文章 - 从 Discrete Log Assumption 到 Pseudorandom Generator

从 Discrete Log Assumption 到 Pseudorandom Generator

预备知识

• 定义 1（Computational Indistinguishability）：令 $\mathcal X=\{X_n\}_{n\in\mathbb N}, \mathcal Y=\{Y_n\}_{n\in\mathbb N}$，其中 $X_n,Y_n\subseteq \{0,1\}^n$。称 $\mathcal X,Y$ 是不可区分的（记为 $X\approx_c Y$），如果对于任意 p.p.t. $A$，存在 negligible 函数 $\varepsilon(\cdot)$ 使得对于任意 $n$ 有

$$\left|\Pr_{x\leftarrow X_n}[A(1^n,x)=1]-\Pr_{y\leftarrow Y_n}[A(1^n,y)=1]\right|\leq\varepsilon(n).$$

• 定义 2（Pseudorandom Generator, PRG）：函数 $G:\{0,1\}^n\to\{0,1\}^m$ 被称为一个伪随机数生成器，如果：
  • $m>n$；
  • 存在确定性多项式算法 $A$ 计算 $G$；
  • $G(\mathcal U(\{0,1\}^n))\approx_c\mathcal U(\{0,1\}^m)$，其中 $\mathcal U$ 表示均匀分布。

注意，在使用 indistinguishability 的记号时，我们往往只会说某一组 $X_n,Y_n$ 而不是整个 $\mathcal X,\mathcal Y$。但这只是一个符号滥用，事实上由于 indistinguishability 是一个渐进概念，$\mathcal X,\mathcal Y$ 还是存在的。例如在 PRG 的定义中，我们实际上应该说：存在一组函数 $\{G_n:\{0,1\}^n\to\{0,1\}^{m(n)}\}$，其中每个函数都满足 $m(n)>n$，可以被多项式计算，且整个 $\{G_n\}$ 的输出作为一个 Ensemble 和随机数不可区分。

• 定义 3（Discrete Log Problem）：令 $p$ 是一个素数，$g$ 是 $\mathbb Z^_p$ 的一个生成元。以 $p,g$ 为参数的离散对数问题 $\text{DL}_{p,g}$ 输入为 $y\in\mathbb Z^_p$，输出为 $x\in[0,p-1]$，使得 $g^x=y$。

• 假设 4（Discrete Log Assumption）：令 $P_n$ 是 $n$ 位素数的集合。对于任何 p.p.t. $A$，存在 negligible 函数 $\varepsilon(\cdot)$ 使得对于任意 $n$ 有

$$\Pr_{p\in P_n,g}\left[\Pr_{y\in \mathbb Z_p^*}[A(1^n,p,g,y)=\text{DL}_{p,g}(y)]>\frac{1}{2}\right]<\varepsilon(n)$$

我不知道假设 4 是不是标准的表述，但是这个不影响后面的内容。

问题描述

我们希望基于 Discrete Log Assumption 构造一个 PRG。历史上已经有很多成功的构造，但我们考察下列构造：

• 对于给定的素数 $p$ 和 $\mathbb Z^_p$ 的生成元 $g$，$G:\left[0,\frac{p-1}{2}\right)\cap\mathbb Z\to \mathbb Z^_p$ 定义为 $G(a)=g^a$。这里我们不拘泥于 $G:\{0,1\}^n\to \{0,1\}^m$ 的要求，认为只要到达域比定义域大一倍就是成功。

接下来我们要证明这个构造是正确的，即 $G$ 的输出和 $\mathbb Z^*_p$ 的随机数不可区分。令 $n$ 是 $p$ 的（二进制）位数，$S^-=\left[0,\frac{p-1}{2}\right)\cap\mathbb Z, S^+=\left[\frac{p-1}{2},p-1\right)\cap\mathbb Z, T^-=\{g^a\mid a\in S^-\}, T^+=\{g^a\mid a\in S^+\}$。证明的思路基于 Blum & Micali 在 FOCS 1982 的论文，首先引入如下问题：

• 定义 5（Principal Square Root Problem）：令 $p$ 是一个素数，$g$ 是 $\mathbb Z^*_p$ 的一个生成元。若 $a$ 是一个 $[0,p-1)$ 中的偶数，则 $g^a$ 有两个平方根 $g^b,g^{b+(p-1)/2}$，其中 $b\in S^-$。$g^b$ 称为 $g^a$ 的主平方根。主平方根问题即输入 $g^a$，求解 $g^b$。

我们的证明分四步走：

• 假设 $G$ 的输出和随机数可区分，则 $T^-$ 和 $T^+$ 可区分；

• 若 $T^-$ 和 $T^+$ 可区分，则存在多项式 $q(n)$ 使得输入为 $\{g^a\mid a\in \left[0,\frac{p-1}{q(n)}\right)\}$ 的主平方根问题可以在多项式时间内解决；

• 对于某个多项式 $q(n)$，若输入为 $\{g^a\mid a\in \left[0,\frac{p-1}{q(n)}\right)\}$ 的主平方根问题可以在多项式时间内解决，则输入为 $\{g^a\mid a\in \left[0,\frac{p-1}{q(n)}\right)\}$ 的离散对数问题可以在多项式时间内解决；

• 对于某个多项式 $q(n)$，若输入为 $\{g^a\mid a\in \left[0,\frac{p-1}{q(n)}\right)\}$ 的离散对数问题可以在多项式时间内解决，则输入为整个 $\mathbb Z^*_p$ 的离散对数问题也可以在多项式时间内解决，与 Discrete Log Assumption 矛盾。

其中第二步是问题的关键。

第一步

假设 p.p.t. $A$ 能够区分 $G$ 的输出和随机数，令 $p_1=\Pr_{a\in S^-}[A(g^a)=1], p_2=\Pr_{a\in S^+}[A(g^a)=1]$，则存在 non-negligible 函数 $\delta(n)$ 使得

$$\left|p_1-\frac{p_1+p_2}{2}\right|\ge\frac{\delta(n)}{2}.$$

因此

$$\left|p_1-p_2\right|\ge\delta(n),$$

这表示 $A$ 本身就能区分 $T^-$ 和 $T^+$。

第二步

$T^-$ 和 $T^+$ 可区分，即存在 p.p.t. $A$ 和 non-negligible 函数 $\delta(n)$ 使得

$$p_1:=\Pr_{a\in S^-}[A(g^a)=1],\quad p_2:=\Pr_{a\in S^+}[A(g^a)=1],\quad p_1-p_2\ge\delta(n).$$

下面假设 $\frac{1}{\delta(n)}$ 不超过某个多项式。这个条件对无穷多个 $n$ 而非全部 $n$ 成立，但是对于不成立的 $n$ 我们也没有必要分析，所以可以做这个假设。

WLOG，假设 $A$ 只会输出 $0$ 和 $1$。

令 $q=q(n)$ 是一个待定的多项式，$S^=\left[0,\frac{p-1}{q}\right)\cap 2\mathbb Z$，我们将构造一个使用 $A$ 的 oracle 的 p.p.t. $B$，使得对于任意 $a\in S^$，

$$\Pr[B(g^a)=g^{a/2}]\ge 1-\frac{1}{2n}.$$

令 $a\in S^*$ 和 $e=g^a$，考虑如何计算 $g^{a/2}$。我们容易计算出 $e$ 的两个平方根 $\{h_0,h_1\}=\{g^{a/2},g^{a/2+(p-1)/2}\}$，但难点在于区分它们。

随机 $q$ 个 $S^-$ 中的数 $r_1,\ldots,r_{q}$，令 $e_i=eg^{2r_i}$，令 $h_{i,0}=h_0g^{r_i},h_{i,1}=h_1g^{r_i}$ 是 $e_i$ 的两个平方根。由于 $e_i$ 是一个均匀随机的二次剩余，因此 $h_{i,0}$ 和 $h_{i,1}$ 各自服从 $\mathbb Z^*_p$ 的均匀分布，且它们总是一个属于 $S^-$，另一个属于 $S^+$。假设 $h_j=g^{a/2} (j\in\{0,1\})$，我们可以计算

$$\begin{aligned} \Pr[A(h_{i,j})=1]&=\Pr\left[\frac{a}{2}+r_i<\frac{p-1}{2}\right]\cdot p_1+\Pr\left[\frac{a}{2}+r_i>\frac{p-1}{2}\right]\cdot p_2\\ &\ge \left(1-\frac{1}{q}\right)\cdot p_1+\frac{1}{q}\cdot p_2. \end{aligned}$$

同理

$$\Pr[A(h_{i,1-j})=1]\leq \frac{1}{q}\cdot p_1+\left(1-\frac{1}{q}\right)\cdot p_2.$$

因此有

$$\mathbb E[A(h_{i,j})-A(h_{i,1-j})]\ge \left(1-\frac{2}{q}\right)(p_1-p_2)\ge \left(1-\frac{2}{q}\right)\delta(n).$$

那么最终 $B$ 的算法就是计算 $Sum_0=\sum_{i=1}^q A(h_{i,0})$ 和 $Sum_1=\sum_{i=1}^q A(h_{i,1})$。若 $Sum_j>Sum_{1-j}$，我们就认为 $h_j=g^{a/2}$。下面用 Hoeffding 不等式分析这个算法的正确率：

$$\begin{aligned} &\quad \Pr[Sum_j\leq Sum_{1-j}]\\ &\leq \Pr\left[(Sum_j-Sum_{1-j})-\mathbb E[Sum_j-Sum_{1-j}]\ge q\left(1-\frac{2}{q}\right)\delta(n)\right]\\ &\leq \exp\left(-\frac{2q^2(1-2/q)^2\delta^2(n)}{q(1-(-1))^2}\right)\\ &=\exp\left(-\frac{q(1-2/q)^2\delta^2(n)}{2}\right) \end{aligned}$$

所以，只要 $\frac{1}{\delta(n)}$ 是多项式，就存在合适的多项式 $q$ 使得上述概率不超过 $\frac{1}{2n}$（具体计算略），这就完成了我们的目标。

第三步

若我们会做主平方根问题，考虑如下离散对数算法 $C_0$：

• 输入 $y$，初始令 $r=y, x=0$。循环下列过程 $n$ 轮：

  • 判断 $r$ 是否是二次剩余：

    若 $r$ 是二次剩余，令 $r$ 变为 $r$ 的主平方根；

    若 $r$ 不是二次剩余，令 $r$ 变为 $r/g$ 的主平方根，设这是第 $i$ 轮，再让 $x\leftarrow x+2^{i-1}$。

• 输出 $x$。

上述算法从低位到高位依次确定 $x$ 的每一位，我们调用了 $n$ 次求主平方根的算法。同时我们可以归纳地说明，只要 $y\in\left[0,\frac{p-1}{q}\right)$ 且前 $k$ 次主平方根都求对了，那么第 $k+1$ 次求主平方根的输入一定在 $\left[0,\frac{p-1}{q}\right)$ 中。

根据第二步的结论，$n$ 次主平方根全都求对的概率为

$$\left(1-\frac{1}{2n}\right)^n\ge \frac{1}{2}$$

这也是 $C_0$ 的正确率的下界。

定义 $C_1$ 为将 $C_0$ 重复 $n$ 次，就可以将正确率 boost 到 $1-\frac{1}{2^n}$。

第四步

将 $[0,p-1)$ 分成 $q$ 段：第 $i$ 段是 $\left[(i-1)\cdot\frac{p-1}{q},i\cdot\frac{p-1}{q}\right)$，考虑如下算法 $C$：

• 输入 $y$。枚举 $i=0,\ldots,q-1$：

  • 令 $y_i=y\cdot g^{-i\cdot (p-1)/q}$，若 $C_1(y_i)$ 正确算出了 $y_i$ 的离散对数 $x_i$，则输出 $x_i+i\cdot\frac{p-1}{q}$。

存在一个 $i$ 使得 $y_i\in \left[0,\frac{p-1}{q}\right)$，因此 $C$ 的正确率至少是 $1-\frac{1}{2^n}$。这与 Discrete Log Assumption 矛盾。

原论文：

Blum, M., & Micali, S. (1982, November). How to generate cryptographically strong sequences of pseudo random bits. In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) (pp. 112-117). IEEE.