1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Have a look here: crypto.stackexchange.com/questions/20748/… $\endgroup$ – curious Aug 11 '16 at 20:37
  • $\begingroup$ @curious, Thanks for the link. I'll have a look. But the proof I presented is different than the proof using bayes theorem (that you linked to). I would like to better understand the proof presented by Dan and what his reasoning is (the proof linked in the slides). The techniques used in this proof are different than the ones that you linked to-- so I consider them different proofs. $\endgroup$ – Max Aug 11 '16 at 20:44
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thanks! This part makes sense "E(k,m)=c for a given m and c is 1." What do you mean by "with k is chosen randomly from K is the same for any plain text and cipher text, and thus OTP has perfect secrecy"? I understand k is to be chosen randomly from K, but I do not understand the rest of the statement. How does this prove OTP has perfect secrecy? I am mostly confused by the denominator. $\endgroup$ – Max Aug 11 '16 at 20:56
  • $\begingroup$ This is essentially the definition of perfect secrecy given in your reference. $\endgroup$ – aventurin Aug 11 '16 at 21:00
  • $\begingroup$ I don't understand the reference you're referring to. I understand that the ciphertext is not to reveal any information about the plaintext. But I don't understand how P[E(k,m)=c] = 1 / (# of keys) proves that OTP has perfect secrecy. Can you explain this? How do you determine the denominator? Is it equal to the numerator? It is unclear to me how this proves what I am trying to show. Thanks. $\endgroup$ – Max Aug 11 '16 at 21:03
  • $\begingroup$ It is by the definition is from the text you have cited (slide 9). The denominator is the number of keys in $K$. Hope my edit helps. $\endgroup$ – aventurin Aug 11 '16 at 21:22
  • $\begingroup$ Thanks. First question: so this means that for any keys k, and any messages m that Pr[(k,m)=c] = 1/(number of keys) hence showing Pr[E(k,m0) = c] = Pr[E(k,m1) = c], thus proving the condition of perfect secrecy. Is that right? Second question: is the denominator (# of keys) different than the numerator (Pr[E(k,m)=c] = 1) -- I think it would otherwise this says you only have a total number of 1 key. I'm confused by that, as I thought Dan mentioned they were both the same size (this is confusing me a bit) and thus a constant. I am confused a bit still. $\endgroup$ – Max Aug 11 '16 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.