伪随机性

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.

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)$.

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)$)