Private key

Secret key for both sender and receiver. Message $m$ from sender to receiver. A pair of encode and decode fuction :$E(m,k)$, $D(k, E(m, k))=m$.

Definition 15   Perfect Secrecy(Shannon 1990's). $\forall m$, the probability distribution over $E(m,k)$ is identical, as a function of $k$.

Evesdropper is just as powerful as the receiver.

Informal definition. A one way function $F$ has the property that $F$ is efficiently computable but $F^{-1}$ is not efficiently computable.

RSA: Hopes that multiplication is a one way function.

Homework: Show that if one way function exist then $\mathbf{P}\neq \mathbf{NP}$.

Formal definition of One way function. $F$ is computed in poly time by a deterministic TM. $\forall$ randomized machine $M$, the probability that $M(y) = x$ where $F(x) = y$ is small.

Definition 16   Computationally Secure. Weak. $\forall$ probablistic turing machines, the probability that $M$ can determine a particular pit of the sent message is at most $\frac{1}{2} + \frac{1}{n^{\Omega(1)}}$ (some small thing).

Assumes a uniform distribution over all messages and all keys.

Theorem 13   If one way functions exist then there is a computationally secure private key system for $n^c$ bit messages with $n$ bit keys.

Definition 17   A psudo-random generator $G$ takes $n$ bits and produces $n^c$ bits such that for all probablistic poly time machine $M$, the probability that $M$ does something different is in $U_{n^c}$ and $G(U_n)$ is small.

Theorem 14   If one way function exists then psudo-random generators exists.

Claim: This theorem implies the previous theorem.

Hard and skip...

Theorem 15   If pseudorandom generators exist, then $\mathbf{BPP}\subseteq \mathrm{subexponential deterministic time}$.

If cryptography is possible then randomized computation doesn't buy you much over deterministic computaiton.

Proof. Assume a pseudo-random generator $G$. Let $M$ be a BPP machine.

$B$: $k<< n$ random bits, run $M$ using $G(k bits)$ as my random string. By definition of pseudo random generators, $B$ and $M$ must basically do the same thing, only different for some small probability.

Deterministic Algorithm $A$: for $i\leftarrow1$ to $2^k$, simulate $B$ using random bits $i$

$\qedsymbol$