A pair of polynomial-time computable functions $(\text{Enc}, \text{Dec})$ is a valid private key encryption scheme if for every $n\in \mathbb{N}$, $k\in \{0, 1\}^{n}$,and $x$, we have

$$\text{Dec}(k, \text{Enc}(k, x)) = x$$

A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.

A valid encryption scheme $(\text{Enc}, \text{Dec})$ with plaintext length $l(\cdot)$ is perfectly secret if for every $n\in \mathbb{N}$ and plaintexts $x_{0}, x_{1} \in \{0, 1\}^{l(n)}$, the following two distributions $Y_{0}$and $Y_{1}$ over $\{0, 1\}^{*}$ are identical:
$Y_{i}$ is obtained by sampling $k$ and outputting $\text{Enc}(k, x_{i})$ for $i = 0, 1$.

$$\begin{align*} P(Y = y\,|\, b = i) &= P(Y_{i} = y) = p(y)\end{align*}$$

And $P(Y = y) = p(y)$ due to $Y$ is perfect, so:

$$\begin{align*} P(Y = y, b = i) &= P(b = i)P(Y = y \,|\, b = i) \\ &= P(b = i)p(y) \\ &= P(b = i)P(Y = y)\end{align*}$$

This means $Y$ is independent to $b$, so $\mathcal{A}$ cannot improve its probability to win by getting $y$

$$\begin{align*} l_{p}(n) = l_{c}&(n) = n \\ \text{Enc}(k, x) &= x \oplus k \\ \text{Dec}(k, c) &= k \oplus c\end{align*}$$

For every perfectly secret encryption scheme, the length function $l_{p}(n)$ satisfies $l_{p}(n)\leq n$

Let $\text{Enc}, \text{Dec}$ be a valid encryption scheme. The scheme is computationally secret if, for every PPT adversary algorithm $\mathcal{A}$ in the secrecy experiment, there is negligible function $\text{negl}$ such that

$$P(\mathcal{A} \text{ succ}) \leq \frac{1}{2} + \text{negl}(n)$$

where the probability is taken over the randomness of $\mathcal{A}$ and the experiment.

A cryptographic pseudorandom generator (PRG) with stretch $l(\cdot)$ is a PPT computable function $G: \{0, 1\}^{*} \to \{0, 1\}^{*}$ such that:

1. $\forall \, n\in \mathbb{N}$ and $s\in \{0, 1\}^{n}$, $|G(s)| = l(n)$
2. For any poly-algorithm $\mathcal{A}$, $s\in \{0, 1\}^{n}$ and $r\in \{0, 1\}^{l(n)}$:

   $$|{P (\mathcal{A}((G(s))) = 1) - P (\mathcal{A}((r)) =1)}| = \text{negl}(n)$$

$$\begin{align*} \text{Enc}(k, x) &= x \oplus G(k) \\ \text{Dec}(c, k) &= c \oplus G(k)\end{align*}$$

An encryption scheme $(\text{Enc}, \text{Dec})$ is CPA-secure if, for all PPT adversary $\mathcal{A}$, there exists a negligible function $\text{negl}$ such that

$$P(\mathcal{A} \text{ succ}) \leq \frac{1}{2} + \text{negl}(n)$$

Let $F_{k}$ be a keyed family of functions that is efficient and length-preserving. We say $F_{k}$ is a pseudorandom function if, for all PPT distinguishers $\mathcal{D}$, there exists a negligible function $\text{negl}$ such that:

$$|{P \bigl( D^{F_k(\cdot)}(1^n) = 1 \bigr) - P \bigl( D^{f_n(\cdot)}(1^n) = 1 \bigr)}| \le \text{negl}(n)$$

where $k\gets\{0, 1\}^{n}$ is chosen uniformly at random and $f_{n}$ is chosen uniformly from the set of functions mapping $n$-bit strings to $n$-bit strings.

1. $\text{Enc}(k, x) = \langle r, F_{k}(r)\oplus x \rangle$
2. $\text{Dec}(k, \langle r, s\rangle) = F_{k}(r) \oplus s$

In this $r\gets\{0, 1\}^{n}$ is randomly chosen.

Consider above scheme as $\Pi = (\text{Enc}, \text{Dec})$ and the similar scheme $\widetilde{\Pi} = (\widetilde{\text{Enc}}, \widetilde{\text{Dec}})$ in which we replace $F_{k}$ with an actual random function.

Assume that $\Pi$ is not CPA-secure, which means there exists an $\mathcal{A}$:

$$P(\mathcal{A}_{\Pi}\text{ succ}) \geq \frac{1}{2} + \frac{1}{\text{poly}(n)}$$

Let $r_{c}$ represents the randomness used in encrypting $x$, while $r_{1}, \dots, r_{q}$ represents the $q(n) = \text{poly}(n)$ randomness used when $\mathcal{A}$ queries to the oracle $\text{Enc}$.
Then we can argue that:

$$P(\mathcal{A}_{\widetilde{\Pi}}\text{ succ}) \leq \frac{1}{2} + \text{negl}(n)$$

We can argue this according to whether $r_{c} \in \{r_{1},\dots ,r_{q}\}$

1. If $r_{c} \in \{r_{1},\dots ,r_{q}\}$, then $\mathcal{A}$ can actually get $r_{c}$ as we contain it in the ciphertext. So $\mathcal{A}$ can always succeed in this case.But this case has a negligible probability $\frac{q(n)}{2^{n}}$ to appear.
2. If $r_{c} \notin \{r_{1},\dots ,r_{q}\}$, then the encryption is like a perfect OTP as we cannot get any information about the random function $f$. So $\mathcal{A}$ has a probability of $\frac{1}{2}$ to win.

So, we have that:

$$\begin{align*}P(\mathcal{A}_{\widetilde{\Pi}}\text{ succ}) &= P(\mathcal{A}_{\widetilde{\Pi}}\text{ succ}\,|\in)P(\in) + P(\mathcal{A}_{\widetilde{\Pi}}\text{ succ}\,|\notin)P(\notin) \\&\leq \frac{q(n)}{2^{n}} + \frac{1}{2} = \frac{1}{2} + \text{negl}(n)\end{align*}$$

Define the distinguisher $\mathcal{D}$, who has an orecal $\mathcal{O}$, as follows:

1. Run $\mathcal{A}(1^{n})$, for each oracle query of $\mathcal{A}$ with $x$, do:
   1. Choose $r\gets \{0, 1\}^{n}$
   2. return $\langle r, \mathcal{O}(r)\oplus x\rangle$ to $\mathcal{A}$
2. When $\mathcal{A}$ gives $\mathcal{D}$ two string $x_{0}, x_{1}$, randomly choose a bit $b$ and:
   1. Choose $r\gets \{0, 1\}^{n}$
   2. return $\langle r, \mathcal{O}(r)\oplus x_{b}\rangle$ to $\mathcal{A}$
3. Answer $\mathcal{A}$ as Step 1 until $\mathcal{A}$ gives an output $b'$. Then we output $1$ if $b' = b$ otherwise $0$.

Actually, this distinguisher is simulating the CPA-experiment. So:

$$\begin{align*}P(\mathcal{D}^{F_{k}(\cdot)}(1^{n}) = 1) &= P(A_{\Pi}\text{ succ}) \\P(\mathcal{D}^{f(\cdot)}(1^{n}) = 1) &= P(A_{\widetilde{\Pi}}\text{ succ})\end{align*}$$

This means that:

$$\begin{align*}&\quad |P(\mathcal{D}^{F_{k}(\cdot)}(1^{n}) = 1) -P(\mathcal{D}^{f(\cdot)}(1^{n}) = 1)| \\&= |P(\mathcal{A}_{\Pi}\text{ succ}) - P(\mathcal{A}_{\widetilde{\Pi}}\text{ succ})| \\&\geq |\frac{1}{\text{poly}(n)} - \text{negl}(n)| \geq \frac{1}{\text{poly}(n)}\end{align*}$$

This is contradict to that $F_{k}$ is PRF!