## PRG

what do you mean by pseudorandomness?

Let’s consider the distribution of strings of l-bit length. Now, distribution is

pseudorandomif choosing any string from the distribution isindistinguishablefrom choosing a uniform l-bit string, i.e. anypolynomial time algorithmcan’t distinguish between string from the distribution and uniform l-bit string.

- thus, pseudorandomness is property of a distribution and similar to how semantic security is computational relaxation of perfect secrecy, pseudorandomness is to true randomness.

**Pseudorandom generator (PRG)**: Informally, PRG is a efficiently computable function $G$ that takes as input $n−$bit strings and output $l(n)−$bit string where $l(n)>n$, and let $Dist_{n}$ be distribution of $l(n)−$bit strings which are the outputs of $G(s)$, by choosing $s∈{0,1}_{n}$ uniformly, then $G$ is PRG iff $Dist_{n}$ is pseudorandom, i.e. any polynomial-time observer can’t distinguish between $G(s)$ and uniformly chosen l(n)-bit string.

- define properties of PRG as:
**expansion**: PRG outputs l(n)-bit string, where $l(n)>n$**pseudorandomness**: $Pr[D(G(s))=1]−Pr[D(r)=1]≤negl(n)$

- existence of PRG $G$, depend on how computationally feasible it is to for a polynomial time distinguisher $D$ to distinguish between a uniform string and the one output by $G$, because if $D$ were modelled as exponential time distinguisher then the probability of brute force attack become large.

## Pseudorandom functions

- A function is not pseudorandom, but chosen from a distribution.
- Keyed function $F(k,x)=y$ where $∣k∣←l_{key}(n),∣x∣←l_{in}(n),∣y∣←l_{out}(n)$
- defining and fixing key $k∈{0,1}_{n}$ creates a function $F_{k}:{0,1}_{n}→{0,1}_{n}$
- This induces a distribution of function in $Func_{n}$, where $Func_{n}$ is distribution of all function that maps n-bit input to n-bit output strings.
- How large is $Func_{n}$? each function $f$ can be viewed as lookup table of $2_{n}$ n-bit length string rows, with output of function $f$ in the row. Thus, each function can be represented as $n⋅2_{n}$ bit string. Total functions are $2_{n⋅2_{n}}$.
- So, any function $F_{k}$ is called pseudorandom if polynomial-time Distinguisher $D$ cannot differentiate between $F_{k}$ or uniformly chosen function $f$ from $Func_{n}$.
- $Pr[D_{F_{k}(⋅)}(1_{n})=1]−Pr[D_{f(⋅)}(1_{n})=1]≤negl(n)$
- Note that distinguisher $D$ doesn’t get full description of the function $f$ since it’s exponential length and $D$ is polynomial time. So, D is given access to oracle that can evaluate $f(x)$ in polynomial time and $D$ can interact with oracle polynomial times.

- PRG can be made from PRF by concatenating evaluations of $F_{k}$, i.e. $G(s)=F_{s}(1)∥F_{s}(2)∥⋯∥F_{s}(l)$ to get $l(n)$ bit pseudorandom string.
- in other direction, creating a PRF $F:{0,1}_{n}×{0,1}_{t(n)}→{0,1}_{n}$ from PRG requires $l(n)=n∗2_{t(n)}$ which is then viewed as lookup table with $2_{t(n)}$ rows and n-bit outputs. But this is only possible for short input lengths, i.e.

Note, however, that F is efficient only if $t(n)=O(gn)$.

don’t understand why this?

- Pseudorandom permutations: $Perm_{n}⊂Func_{n}$ is the set of all bijection on ${0,1}_{n}$. Total size of Perm distribution is $2_{n}!$.
- keyed permutation $F$ defined as function $F$ for which $l_{in}=l_{out}$ and for key $k∈{0,1}_{l_{key}(n)}$, $F:{0,1}_{l_{in}(n)}→{0,1}_{l_{out}(n)}$ is one-to-one and $F_{k}$ should be efficiently computable and invertible.
- Proposition: If $F$ is a PRP, then it is also a PRF.
**Prove this**. **Strong PRP**: when distinguisher $D$ is given oracle access to $F$ and $F_{−1}$ and need to distinguish between $F_{k}$ and uniform function $f$, then it is called Pseudorandom permutation.- $Pr[D_{F_{k},F_{k}}(1_{n})=1]−Pr[D_{f,f_{−1}}(1_{n})=1]≤negl(n)$