ROBP 三种本质相同的 PRG

这篇博文记录了 read-once branching program 三种本质相同的 pseudorandom generator —— [Nisan’92]、[Impagliazzo-Nisan-Wigderson’94] 和 [Nisan-Zuckerman’96]。

分别阐述了三种 PRG 的构造方法，最后用 Leftover Hash Lemma 这一桥梁将三者联系在一起。

引入

Read-once Branching Program

Nisan’s PRG

Pairwise-independent Hash Family 与其性质

构造

推论

Impagliazzo-Nisan-Wigderson PRG

Combinatorial Rectangle 与其 PRG

构造

更多 Open Problems

Nisan-Zuckerman PRG

Extractor 与其性质

构造

大一统 —— Leftover Hash Lemma

定理内容

Seedless Extractor 定义的是，要构造一个函数 $\text{Ext} : \{0, 1\}^n \to \{0, 1\}^m$，使得对于所有的 $k$-source 都有 $\Delta(\text{Ext}(X), U_m) < \varepsilon$，这被证明是不可能的。

但如果我们换一个顺序，允许对于每种 $k$-source 都换用不同的函数，那么情况会有所不同。

Thm

我们还可以将定理的结论换一个说法：$\Delta((H, H(X)), (U_H, U_{[M]})) < \varepsilon$。

Thm (Leftover Hash Lemma) 设 $\mathcal{H} = \{h : \{0, 1\}^n \to \{0, 1\}^m \}$ 是一个 pairwise-independent hash family，并且 $m = k - 2 \log (1 / \varepsilon)$。那么 $\text{Ext}(x, h) \triangleq h(x)$ 是一个 strong $(k, \varepsilon)$-extractor。

Proof. 由 Cauchy 不等式可得：

$\Delta((H, H(X)), (U_d, U_m)) = \dfrac{1}{2} \| (H, H(X)) - (U_d, U_m) \|_1 \\ \le \dfrac{\sqrt{D M}}{2} \| (H, H(X)) - (U_d, U_m) \|_2 = \dfrac{\sqrt{D M}}{2} \left( \text{CP}((H, H(X))) - \dfrac{1}{D M} \right)^{1 / 2}$

其中 $\text{CP}(X) \triangleq \Pr[X = X'] = \sum_x \Pr[X = x]^2$（这里 $X, X'$ i.i.d.）表示分布 $X$ 的碰撞概率 (collision probability)。

所以我们转而去控制 $\text{CP}((H, H(X)))$，有：

$\begin{aligned} \text{CP}((H, H(X))) & = \Pr[(H, H(X)) = (H', H'(X'))] \\ & = \Pr[H = H' \wedge (X = X' \vee (X \ne X' \wedge H(X) = H(X')))] \\ & = \Pr[H = H'] ( \Pr[X = X'] + \Pr[X \ne X', H(X) = H(X')] )\ (\text{独立性}) \\ & = \text{CP}(H) ( \text{CP}(X) + \Pr[X \ne X'] \cdot \Pr[H(X) = H(X') \mid X \ne X'] ) \\ & \le \text{CP}(H) ( \text{CP}(X) + \Pr[H(X) = H(X') \mid X \ne X'] ) \\ & \le \dfrac{1}{D} \left( \dfrac{1}{K} + \dfrac{1}{M} \right) \le \dfrac{1 + \varepsilon^2}{D M} \end{aligned}$

综上：

$\Delta((H, H(X)), (U_d, U_m)) \le \dfrac{\sqrt{D M}}{2} \cdot \sqrt{\dfrac{1 + \varepsilon^2}{D M} - \dfrac{1}{D M}} = \dfrac{\varepsilon}{2}$

即得。$\Box$

本质相同的论述

更多的讨论

参考文献

[HH23] Pooya Hatami and William M. Hoza. “Theory of Unconditional Pseudorandom Generators”. In: ECCC preprint TR23-019. 2023.

[INW94] Russell Impagliazzo, Noam Nisan, and Avi Wigderson. “Pseudorandomness for Network Algorithms”. In: Proc. 26th Annual ACM Symposium on Theory of Computing (STOC). 1994, pp. 356–364. isbn: 0897916638. doi: 10.1145/195058.195190

[Nis92] Noam Nisan. “Pseudorandom generators for space-bounded computation”. In: Combinatorica 12.4 (1992), pp. 449–461. doi: 10.1007/BF01305237

[NZ96] Noam Nisan and David Zuckerman. “Randomness is linear in space”. In: J. Comput. System Sci. 52.1 (1996), pp. 43–52. issn: 0022-0000. doi: 10.1006/jcss.1996.0004

[Vad12] Salil P. Vadhan. “Pseudorandomness”. In: Foundations and Trends in Theoretical Computer Science 7.1-3 (2012), pp. 1–336. doi: 10.1561/0400000010