One Time Pad

Info: Def: a cipher defind over (K, M, C)
a cipher is a pair of “efficient” algs (E, D) where $E:K\times M\to C$ and $D:K\times C \to M$
Consistency equation: $\forall m \in M,k\in K,D(k,E(k,m))=m$
every cipher has to satisfy it in order to be a cipher. Other wise, it would be unpossible to decrypt.

• E is often randomized. D is always deterministic.

One time pad

Warning: First example of a “secure” cipher.

$M=C=K=\{0,1\}^n$

A key in one time pad is a random sequence of bits that’s as long as the message to be encrypted.

Success: If all you see is the cipher text, you should know nothing about the plain text.

Def: a cipher (E, D) over (K, M, C) has perfect secrecy if $\forall m_0,m_1 \in M,\forall c \in C$, $Pr(E(k,m_0)=C)=Pr(E(k,m_1)=C)$
where k is uniform in K, k is a random variable that’s uniformly smaple in the key space K.

if an attacker intercept a particular cipher text c, he has no idea about what it comes from. Even the most powerful attacker can learn nothing about the plain text from the cipher text.

Tip: There is only one OTP key map $m$ to $c$

Danger: Perfect secrecy requires $\|K\|\geq \|M\|$