Intuition

To design a CPA-Secure scheme, we can output $i, m \oplus PRG(k)_{i\dots i+|m|-1}$, which is very hard to compute when $i$ is exponential in $n$.

PseudoRandom Function

• $\{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^*$

    **KEY           INPUT       OUTPUT**
  

• Easy to compute

• $l_{input} = l_{key} = l_{output} = n$ for most of the cases

• With a randomly sampled key $k$, $f$ if indistinguishable with a randomly sampled function (from $2^{n2^n}$functions)

PRF $\Rightarrow$ CPA-secure Enc

• Enc$(k,m) = r, f(k, r)\oplus m$
• $r \stackrel{\smash{\$}}\leftarrow \{0,1\}^*$

PRF $\Leftrightarrow$ PRG

• PRF $\Rightarrow$ PRG $f(k,0)||f(k,1)$
• PRG $\Rightarrow$ PRF
  • binary tree construction
  • Hybrid argument: Substitute the strings on the path of adversary’s query into random ones (at most $np(n)$ hybrids)
  • Check Goldreich’s book

PseudoRandom Permutation

• given key, $f(k, .)$ is a permutation
• $f$ is a PRF
• efficient computation

Strong PRP (Block Cipher)

• efficient calculation and inversion