PRG 与 PRF

Note

伪随机序列生成器 (Pseudorandom Generator, PRG)
伪随机生成函数 (Pseudorandom Function, PRF)

PRG 是密码学中一个很重要的部分，它的作用是把 $n$ bit 的序列映射为 $\ell(n)$ bit 的序列，一般来说， $\ell(n)\gg n$ 。

为什么需要这么做呢？

我们知道，最早的 绝对安全 (perfectly secret) 加密机制是 one-time pad ，简称 OTP，它的形式为： $$ \mathcal{C} = \mathcal{M} \oplus \mathcal{K} $$

也就是密文等于明文与密钥的异或，虽然是很安全的，但需要满足两个重要的前提：

密钥 $\mathcal{K}$ 的长度与 $\mathcal{M}$ 一致
每次加密都需要更换密钥 $\mathcal{K}$

这样问题就来了，解密的一方也需要使用 $\mathcal{K}$ 来解密，那么该如何安全地传输密钥呢？

换句话说，既然能够安全地传输密钥 $\mathcal{K}$ ，那么为什么不能直接安全地传递明文 $\mathcal{M}$ 呢？

因此现代密码学中的加密方案，一般要求密钥长度远远低于明文长度，假如我们有这种 伪随机序列生成器 $G$ ，那么我们就可以把长度为 $n$ bit 的密钥 $\mathcal{K}$ 映射为长度为 $n$ bit 的 $G(\mathcal{K})$ ，再使用 OTP：

$\mathcal{C} = \mathcal{M} \oplus G(\mathcal{K})$

在密码学中，对 PRG 的定义比较严格，在现实生活中往往很难找到实际的构造，只能看做理论上的存在。

在明白 PRG 的定义之前，需要知道什么是 计算不可区分。

1. 计算不可区分

Note

计算不可区分 (computationally indistinguishable)

假设 $X_{n},Y_{n}$ 是两个在 $\{0,1\}^{\ell(n)}$ 上的分布，对于它们的两个序列 $\{X_{n}\},\{Y_n\}$ ，如果对于 polynomially-bounded $\epsilon$ 和所有的 polynomial-time $\mathcal{A}$ ，当 $n$ 足够大时，有：

$|\Pr[\mathcal{A}(X_n)=1] - \Pr[\mathcal{A}(Y_n)=1]|\leq \epsilon(n)$

总是成立，那么我们称 $X$ 与 $Y$ 是计算不可区分的，记作 $X_n\approx Y_n$ 。

2. 伪随机数生成器

如果存在一个函数 $G$ ，可以把 $n$ bit 字符串映射为 $\ell(n)$ bit，其中 $\ell(n)\geq n$ ，

且 $G(U_n)\approx U_{l(n)}$ ，那么 $G$ 就是伪随机数生成器。

Note

对于固定的输入， $G$ 会给出固定的输出。输出的随机性取决于输入的随机性。

3. 伪随机函数

像这样 $\mathcal{F}=\{f_s\}_{s\in\{0,1\}^*}$ 的函数，其中 $f_s:\{0,1\}^{|x|}\rightarrow\{0,1\}^{|s|}$ ，如果在随机挑选 $s$ 的情况下， $\mathcal{F}$ 与真正的随机函数 $F(\cdot)$ 是不可区分的，那么我们称 $\mathcal{F}$ 是伪随机函数。

Game-based

在密码学中，我们一般使用 Game-based 方式来进行说明，假设我们有下面这两种游戏：

Game 1:

s is chosen at random in $\{0,1\}^n$ ;
Adversary $\mathcal{A}$ gets black-box access to the function $f_s(\cdot)$ for as long as it wishes (poly( $n$ ) time);
$\mathcal{A}$ outputs a bit $v\in\{0,1\}$

Game 2:

A random function $F:\{0,1\}^n\rightarrow\{0,1\}^n$ is chosen;
$\mathcal{A}$ gets black-box access to the function $F(\cdot)$ for as long as it wishes (poly( $n$ ) time);
$\mathcal{A}$ outputs a bit $v\in\{0,1\}$

For every poly-time $\mathcal{A}$ and poly-bounded $\epsilon$ , and large enough $n$ :

$|\Pr[\mathcal{A}\ \mathsf{outputs\ 1\ in\ Game\ 1}]-\Pr[\mathcal{A}\ \mathsf{outputs\ 1\ in\ Game\ 2}]| < \epsilon(n)$