§4 Pseudorandom Generators

Pseudorandomness

• Definition: Let $\{D_n\}$ be a sequence of distributions over $p(n)$-bit strings. $\{D_n\}$ is pseudorandom if for every probabilistic, polynomial-time algorithm $\mathscr A$, there is a negligible function $\epsilon$ such that

  $$\left|\operatorname{Pr}_{x \leftarrow D_{n}}[\mathscr{A}(x)=1]-\operatorname{Pr}_{x \leftarrow U_{p(n)}}[\mathscr{A}(x)=1]\right| \leq \epsilon(n)$$

Pseudorandom (Number) Generators (PRGs/PRNGs)

• Definition. Let $p$ be a polynomial and let $G$ be a deterministic polynomial-time algorithm such that for any $n$ and any input $s \in \{0,1\}^n$, $G(s)$ is a string of length $p(n)$.

  We say that $G$ is a pseudorandom generator if the following hold:

  1. Expansion: For every $n$ it holds that $p(n) > n$. We call $p$ the expansion factor of $G$.

  2. Pseudorandomness: For any PPT algorithm $D$, there is a negligible function $\epsilon$ such that

     $$\left|\operatorname{Pr}_{s \leftarrow U_{n}}[D(G(s))=1]-\operatorname{Pr}_{r \leftarrow U_{p(n)}}[D(r)=1]\right| \leq \epsilon(n)$$

     where the first probability is over uniform choice of $s \in \{0,1\}^n$ and the randomness of $D$, and the second is over uniform choice of $r \in \{0,1\}^{p(n)}$ and the randomness of $D$.

Linear Congruential Generator

• The Linear Congruential Generator is a simple Pseudo-Random Generator, that is in general not cryptographically secure.

• Parameters.

  • $m > 0$: the modulus,
  • $0 < a < m$: the multiplier,
  • $0 ≤ c < m$: the increment, and
  • $0 ≤ X_0 < m$: the seed.

• The Linear Congruential Generator generates a sequence of pseudo-random numbers $\{X_n\}$ via:

  $$X_{n+1} = (aX_{n} + c) \bmod m$$

Blum Blum Shub Generator

• The Blum Blum Shub Generator is a cryptographically secure pseudo-random bit generator.

• Parameters.

  • $p, q$: large prime numbers such that $p \equiv q \equiv 3 \pmod{4}$,
  • $M = p \times q$,
  • $s$ : random number relatively prime to $M$.

• The Blum Blum Shub generator generates a sequence of pseudo-random bits $B_i$ via:

  $$X_{0}=s^{2} \bmod M, \text { for } i=1 \rightarrow \infty, X_{i}=\left(X_{i-1}\right)^{2} \bmod M, B_{i}=X_{i} \bmod 2$$

Stream Cipher

• Definition: A Stream Cipher is a pair of deterministic algorithms $(Init, GetBits)$ where:
  1. $Init$ takes input seed $s$, optional initialisation vector $IV$, outputs initial state $st_0$.
  2. $GetBits$ takes input state $st_i$, outputs bit $y$ and updated state $st_{i+1}$.

Pseudo One-Time Pad

• Pseudo One-Time Pad Construction. Let $G$ be a pseudorandom generator with expansion factor $p$. Define a private-key encryption scheme for messages of length $p$ as:
  • $Gen$ : Takes input $1^n$, outputs a uniform $k \in \{0,1\}^n$ as the key.
  • $Enc$: Takes as inputs key $k \in \{0,1\}^n$ and message $m \in \{0,1\}^{p(n)}$, outputs the ciphertext $c := G(k) \oplus m$.
  • $Dec$ : Takes as inputs key $k \in \{0,1\}^n$ and ciphertext $c \in \{0,1\}^{p(n)}$, outputs the message $m := G(k) \oplus c$.

Pseudo One-Time Pad: Computational Security

• Theorem. If $G$ is a pseudorandom generator, then the Pseudo One-Time Pad construction is a fixed-length private-key encryption scheme that has indistinguishable encryptions in the
  presence of an eavesdropper.

— Feb 3, 2023

§4 Pseudorandom Generators by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.