- Pseudo-random Generators
- PRG-Based Encryption: One-time Pad Example
- Pseudo-random Functions
- Pseudo-random Permutations

# Pseudo-random Generators

Let us think of an experiment with an efficient **distinguisher** $D$ that plays the following two games:

- A game where challenger gives the distinguisher a uniformly random chosen value; the distinguisher wins if it can find that this value was actually uniformly randomly generated:

sequenceDiagram actor D actor chal Note over chal: pick uniformly random y_unif chal ->> D: y_unif Note over D: compute b' #8712; {0, 1} Note over D,chal: "D" wins if b' = 1

- A game where challenger gives the distinguisher a pseudo-randomly generated value, with a uniformly random chosen
**seed**; the distinguisher wins if it can find that this value was actually pseudo-randomly generated:

sequenceDiagram actor D actor chal Note over chal: pick uniformly random s Note over chal: y_psd = G(s) chal ->> D: y_psd Note over D: compute b' #8712; {0, 1} Note over D,chal: "D" wins if b' = 0

With these two games, we would like to see:

$∣Pr[D(y_{unif})=1]−Pr[D(y_{psd})=1]∣≤negl$

Notice that this is the statement we made in semantic security. Also notice that the seed of pseudo-random generator ($s$ in $G(s)$) is assumed to be uniformly random. If the seed is known, you can easily guess which number will be generated.

## A more formal definition

Let $l$ be a polynomial and let $G$ be a **deterministic** polynomial-time algorithm such that for any $n$ and any input $s∈{0,1}_{n}$, the result of $G(s)$ is a string of length $l(n)$. We say that $G$ is a pseudo-random generator (PRG) if the followings hold:

**Expansion:**For every $n$ it holds that $l(n)>n$. This $l$ is called the**expansion factor**of $G$.**Pseudorandomness:**For every efficient (i.e. probabilistic polynomial time) distinguisher $D$ there is a negligible function $negl$ such that:

$∣Pr[D(r)=1]−Pr[D(G(s))=1]∣≤negl$

where $s$ is chosen uniformly random from ${0,1}_{n}$ and $r$ is chosen uniformly random from ${0,1}_{l(n)}$.

# PRG-Based Encryption: One-time Pad Example

Consider a scheme $X$ and a PRG $G:{0,1}_{n}→{0,1}_{n_{′}}$, $M={0,1}_{n_{′}}$.

$Gen(1_{n})→k:k←{0,1}_{n}$

$Enc(k,m)→c:c:=G(k)⊕m$

$Dec(k,c)→m_{′}:m_{′}:=G(k)⊕c$

**Theorem:** $G$ is a secure PRG $⟹$ $X$ is a secure encryption scheme against a 1-message eavesdropper.

**Proof:** If $∃$ efficient $A$ who breaks $X$, then we construct efficient $B$ who breaks $G$; as in, $B$ would be able to distinguish wheter a given value is pseudo-random or uniformly random with non-negligible advantage.

sequenceDiagram actor chal actor B actor A alt uniform ("R") rect rgb(220, 220, 240) Note over chal: r #8712; {0, 1}^n' end else pseudo-random ("PR") rect rgb(240, 220, 220) Note over chal: s #8712; {0, 1}^n Note over chal: r = G(s) end end chal ->> B: 1^n, r B ->> A: 1^n Note over B: b #8712; {0, 1} A ->> B: m_0, m_1 Note over B: c = r #8853; m_b B ->> A: c A ->> B: b' alt b = b' rect rgb(220, 220, 240) Note over B: output "R" end else b #8800; b' rect rgb(240, 220, 220) Note over B: output "PR" end end

Looking at $A$'s game:

$Pr[b_{′}=b]=21 +ϵ(n)$

where $ϵ(n)$ is either negligible or non-negligible, we do not know yet :)

Looking at $B$'s game:

$∣Pr[Boutputs R∣ris R]−Pr[Boutputs R∣ris PR]∣=ϵ(n)$

Since $Boutputs R$ if and only if $b_{′}=b$:

- $Pr[Boutputs R∣ris R]$ is equal to $1/2$. We know this from One-time Pad.
- $Pr[Boutputs R∣ris PR]$ is equal to $1/2+ϵ(n)$ probability, and for $b_{′}=b$ player $A$ would need to lose. So what is the probability $Pr[b_{′}=b]=1−Pr[b_{′}=b]=1−(1/2+ϵ(n))$.

Our expression for $B$'s game is then:

$ 21 −(21 −ϵ(n)) =ϵ(n)$

At this point, we were able to connect formally that the probability $B$ wins it's game is equal to the probability $A$ wins it's game. If $A$ were to have a non-negligible advantage in guessing $b_{′}$, then $B$ would have a non-negligible difference between the result of its games. However, we had assumed that $G$ is a pseudo-random generator so $B$ should not have a non-negligible difference!

Therefore, $B$ must have a negligible difference ($ϵ(n)$ is negligible) and thus $A$ has negligible advantage. $X$ is indeed a secure scheme (against a 1-message eavesdropper, which is a very puny weak defense but hey its something). Q.E.D.

# Pseudo-random Functions

Denote the set of all function that map ${0,1}_{n}→{0,1}_{n}$ as $Func_{n}$. Note that this a HUGE set, with the size $2_{n2_{n}}$.

Now, let $F:{0,1}_{∗}×{0,1}_{∗}→{0,1}_{∗}$ be an efficiently computable function. Define $F_{k}(x):=F(k,x)$. Here, we refer to $k$ as key. Assume that $F$ is length preserving : $F(k,x)$ is only defined if $∣k∣=∣x∣$, in which case $∣F(k,x)∣=∣k∣=∣x∣$. Notice that choosing $k←{0,1}_{n}$ is then equivalent to choosing the function $F_{k}:{0,1}_{n}→{0,1}_{n}$. In other words, $F$ defines a distribution over functions in $Func_{n}$.

We define that $F$ is a pseudo-random function if $F_{k}$ for a uniform key $k$ is indistinguishable from a uniform function $f∈Func_{n}$. More formally, for all distinguishers $D$:

$∣k←{0,1}_{n}Pr [D_{F_{k}(.)}=1]−f←Func_{n}Pr [D_{f(.)}=1]∣≤negl(n)$

where $F_{k}:{0,1}_{n}→{0,1}_{n}$ for some $n_{′}=poly(n)$.

It is easy to think of an interactive proof where the distinguisher keeps querying $x$ to get $f(x)$ in one scenario, and $F_{k}(x)$ in the other; if it can't distinguish the difference after polynomially many such queries, our dear $F_{k}$ is a pseudo-random function! Also note that given a PRF $F$, we can immediately obtain a PRG $G$. For example:

$G(k)=F_{k}(00…0)∣∣F_{k}(00…01)$

where $∣∣$ is concatenation.

# Pseudo-random Permutations

Let $F$ be a length-preserving keyed function. Then, $F$ is a keyed-permutation if:

- $F_{k}$ is a bijection for every $k$, meaning that $F_{k}$ is invertible.
- $F_{k}$ is efficiently computable, where $F_{k}(F_{k}(x))=x$.

Essentially, a PRF with $n_{′}=n$ and bijection is a PRP.