Pseudorandomness
Randomness is a very important concept in cryptography (and not only in cryptography). Although the concept of randomness is often mentioned, what exactly is randomness and how is it implemented?
Our understanding of the concept of “randomness” cannot be separated from the physical phenomena in real life. For example, the sequence of numbers obtained by rolling a six-sided die multiple times is clearly “random”; this randomness, guaranteed by physical experiments, is called True randomness.
True random number generation is technically demanding and inefficient: a true random number generator (TRNG) must rely on some random external physical phenomenon as the information entropy resource, such as the trajectory of the user’s mouse movement, thermal noise from resistors and oscillators, computer hardware noise, etc.
NO pure algorithms could achieve true randomness.
Here, pure algorithms are the algorithms that only use designed mathmatical formulaes or precalculated tables to produce number suquence.
TRNGs that generate random numbers with the help of external physical phenomenon is inefficient. Only pure algorithm could meet the requirement of producing many numbers efficiently. Therefore, the concept of pseudorandomness is put forward: Pseudorandom numbers are numbers that appear random.
Pseudorandom number generators (PRGs) are the generators that efficiently generate pseudorandom number sequence. PRG takes a short seed $s$ and produces a pseudorandom string $G(s)$.
Pseudorandomness is the relaxation of true randomness.
We could say that pseudorandomness is equivalent to true randomness in probablistic polynomial time (PPT) background.
How to define “appear random”? There are several PPT statistical tests that used to check whether a number sequence is statistical independent or not. If a number sequence could pass all the statistical tests, it is regarded as random, no matter it is generated by TRNGs or PRGs.
Essentially, pseudorandom number sequence (or say PRGs) is deterministic : for a fixed seed $s$, $G(s)$ always remains the same. However, if an adversary observing $G(s)$ without knowing the seed $s$, he can NOT distinguish $G(s)$ from a truly random number sequence $r$ with non-negligible advantage.
We could see that in the definition of PRGs:
$G$ is a PRG if for every PPT distinguisher $D$, $|\Pr_{s\leftarrow U_n}[D(G(s))=1]-\Pr_{r\leftarrow U_{p(n)}}[D(r)=1]|\leq \varepsilon(n)$.
Note that $p(n)$ is the expansion factor of PRG: $G$ expands the seed $s$ ($|s|=n$) to $G(s)$ ($|G(s)|=p(n)$)
伪随机也是我觉得十分巧妙的一个概念。
其实，本质上来说，伪随机和加密十分相似。加密算法通过密钥 $k$ 的不可知性保证密文 $c$ 的不可解读性；而伪随机数生成器则通过种子 $s$ 的不可知性保证生成的数串 $G(s)$ 的 (伪) 随机性。
这也可以说是柯克霍夫定律威力的延伸体现。