Clarification of Proof: Proving perfect secrecy for One Time Pads

Question

I came across a version of a proof that One Time Pads have perfect secrecy and have a few questions with this version of the proof. The proof is attributed to Dan Boneh (the proof starts on slide 10),

Definition: A cipher (E,D) over (K,M,C) has perfect secrecy if $\forall m_{0}, m_{1} \in$ M, $(\left\vert{m_{0}}\right\vert)$ = $(\left\vert{m_{1}}\right\vert)$ and $\forall$c $\in$ C, such that: Pr[E(k,$m_{0}$)=c] = Pr[E(k,$m_{1}$)=c] where k is a random variable that is uniformly sampled in the keyspace K.

My understanding of the Proof is as below,

Lemma: OTP has perfect secrecy

Proof:

For every message m and every ciphertext c:

Pr[E(k,m)=c] = ${\dfrac{\text{ #keys k in K s.t. E(k,m)=c}}{\text{Total number of Keys}}}$

Suppose that we have a cipher for all m,c: k in K: E(k,m)=c is equal to some constant.

If that is the case then for all $m_{0}, m_{1}$ the probability of E(k,m)=c is the same and Dan states the the denominator (total number of keys) is the same as the number of keys k in K such that: E(k,m)=c.

If this probability is true then the cipher has perfect secrecy.

Let m in M and c in C, then the number of OTP keys that map m to c is 1.

If E(k,m)=c => k $\oplus$ m = c => k= m $\oplus$ c

What this says is that the number of keys k in K: E(k,m)=c = 1 which completes the proof that OTP has perfect secrecy.

Questions:

• Why does Pr[E(k,m)=c] = ${\dfrac{\text{ #keys k in K s.t. E(k,m)=c}}{\text{Total number of Keys}}}$
• Why is the #keys k in K s.t. E(k,m)=c equal to the total number of keys? Is it because of the following condition: $\forall m_{0}, m_{1} \in$ M, $(\left\vert{m_{0}}\right\vert)$ = $(\left\vert{m_{1}}\right\vert)$ -- which means one of the requirements for perfect secrecy is that every message m has to be the same length, hence meaning that every key k also has to be the same length, and for each unique message m there must be a unique key k that encrypt its. So the total number of keys is equal to the total number of messages.

But this line of reasoning still doesn't make sense to me. Say there are 5 messages: $m_{1},m_{2}, m_{3}, m_{4}, m_{5}$ and 5 keys that encrypt those messages: $k_{1},k_{2}, k_{3}, k_{4}, k_{5}$ -- then the total number of keys is 5 and the total number of keys that uniquely map $m_{1},m_{2}, m_{3}, m_{4}, m_{5}$ to $c_{1},c_{2}, c_{3}, c_{4}, c_{5}$ is 1, namely: E($m_{n}, k_{n})=c_{n}$ for each m,k, c, as you have a 1-1 pair for messages to keys, so the ratio is 1/5 and not 1. What is wrong with this? Or is it counting the total number of such keys that make (k,m) to c? If it counts the total number of such keys, then that answer is 5 in this example. I'm confused.

• How does showing Pr[E(k,m)=c] = ${\dfrac{\text{ #keys k in K s.t. E(k,m)=c}}{\text{Total number of Keys}}}$ = 1 prove OTP have perfect secrecy. This doesn't make any sense to me given the statement of the theorem.

I need help understanding this proof, breaking down what the proof is saying.

Thanks!

Answer 1

As you have shown, the number of keys such that $E(k,m)=c$ for given $m$ and $c$ is $1$. So the probability

$$Pr[E(k, m) = c] = \frac{1}{number\,of\,keys}$$

with $k$ chosen randomly from $K$ is the same for any plain text and any cipher text, so

$$Pr[E(k, m_0) = c] = Pr[E(k, m_1) = c]$$

for all $c \in C$ and $m_0, m_1 \in M$ with $|m_0| = |m_1|$, and thus by definition the OTP has perfect secrecy.