形式定义PRNG

Question

我试图寻找一本以正式方式呈现密码概念(特别是PRNG)的书，但我发现的是一种直观的方法。那么，我的问题是，Psuedo随机数生成器(PRNG)或函数的形式定义是什么？

Answer 1

如果我们称U_k为随机变量，即在长度为k的比特串上均匀分布的随机变量，则在不可行的情况下，函数g: \{0,1\}^k \to \{0,1\}^m称为伪随机生成器(如果需要的话，多时间)可以以不可忽略的概率区分g(U_k)和U_m。

更正式地说，让U'_m = g(U_k)作为\Delta^D(U'_m, U_m) = Pr^{DU_m}[Z = 1] - Pr^{DU'_m}[Z = 1]来表示任何区分器有效D的区别优势是可以忽略不计的。

在这里，Z是区分器的输出，任何适当的“非常小”的概念都可以忽略不计；对于效率来说也是一样的。