# 5: Pseudorandom Generators

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$

( \newcommand{\kernel}{\mathrm{null}\,}\) $$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\id}{\mathrm{id}}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\kernel}{\mathrm{null}\,}$$

$$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$

$$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$

$$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

One-time pad requires a key that’s as long as the plaintext. Let’s forget that we know about this limitation. Suppose Alice & Bob share only a short $$\lambda$$-bit secret $$k$$, but they want to encrypt a $$2 \lambda$$-bit plaintext $$m$$. They don’t know that (perfect) one-time secrecy is impossible in this setting (Exercise 2.11), so they try to get it to work anyway using the following reasoning:

• The only encryption scheme they know about is one-time pad, so they decide that the ciphertext will have the form $$c=m \,\oplus$$ ??. This means that the unknown value $$? ?$$ must be $$2 \lambda$$ bits long.
• In order for the security of one-time pad to apply, the unknown value ?? should be uniformly distributed.
• The process of obtaining the unknown value ?? from the shared key $$k$$ should be deterministic, so that the sender and receiver compute the same value and decryption works correctly.

Let $$G$$ denote the process that transforms the key $$k$$ into this mystery value. Then $$G$$ : $$\{0,1\}^{\lambda} \rightarrow\{0,1\}^{2 \lambda}$$, and the encryption scheme is $$\operatorname{Enc}(k, m)=m \oplus G(k)$$

It is not hard to see that if $$G$$ is a deterministic function, then there are only $$2^{\lambda}$$ possible outputs of $$G$$, so the distribution of $$G(k)$$ cannot be uniform in $$\{0,1\}^{2 \lambda}$$. We therefore cannot argue that the scheme is secure in the same way as one-time pad.

However, what if the distribution of $$G(k)$$ values is not perfectly uniform but only "close enough" to uniform? Suppose no polynomial-time algorithm can distinguish the distribution of $$G(k)$$ values from the uniform distribution. Then surely this ought to be "close enough" to uniform for practical purposes. This is exactly the idea of pseudorandomness. It turns out that if $$G$$ has a pseudorandomness property, then the encryption scheme described above is actually secure (against polynomial-time adversaries, in the sense discussed in the previous chapter).

This page titled 5: Pseudorandom Generators is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.