6
$\begingroup$

I'm reading about one-time pad in "Introduction to Modern Cryptography" by Katz and Lindell. I can understand the definition of perfect secrecy. However, how is OTP proven to be perfectly secure ? I'm quite rusty on probability, so please explain the steps.

The proof in the book goes like this,

$M$ is the set of messages (all possible bit strings of length $\ell$), the message space. $K$ (the key space) is equal to the message space, and the cipher is computer as $c=k\oplus m$, where $k$ belongs to $K$ (chosen uniformly at random) and m belongs to $M$, \begin{align*} \Pr&[C=c\mathrel|M=m] \\ &= \Pr[M \oplus K = c \mathrel| M = m] \\&\quad\text{(How did the random variable $C$ become $M\oplus K$ here?)} \\ &= \Pr[m \oplus K = c] \\&\quad\text{(where did the conditional probability go ? what rule should I apply here ?)} \\ &= \Pr[K = m \oplus c] \\&\quad\text{(what is this ?)} \\ &= 1/2^\ell \\&\quad\text{(how should I arrive at this finally ?)} \end{align*} I did not understand any of these four steps. Please explain the reasoning behind these steps. This result is being used to show that it satisfies the definition of perfect secrecy. Please help me understand this result.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

First, be careful about case:

  • The uppercase letters denote random variables in some probability space.
  • The lowercase letters denote particular values in the domains of the corresponding random variables.

For example, if the probability space is $\Omega$, then $C\colon \Omega \to \{0,1\}^\ell$ is a random variable for the ciphertext in the one-time pad system, and $c \in \{0,1\}^\ell$ is a particular value of a ciphertext, which at some sample $\omega \in \Omega$ might be the value of $C(\omega) = c$.

The random variable $C$ is related to the random variables $M$ and $K$ by $C = M \oplus K$, which is the standard mild abuse of notation for random variables meaning that $C(\omega) = M(\omega) \oplus K(\omega)$ in any sample $\omega \in \Omega$. Any fixed values $c$, $m$, and $k$ might or might not be related by $c = m \oplus k$, although if in some sample $\omega$ we have $C(\omega) = c$ and $M(\omega) = m$ and $K(\omega) = k$ then $c$, $m$, and $k$ are indeed related by $c = m \oplus k$.

For any fixed message $m \in \{0,1\}^\ell$, in the event $E = \{\omega \in \Omega \mathrel: M(\omega) = m\}$ where the message $M$ takes on the value $m \in \{0,1\}^\ell$, what can you conclude about $C$? In other words, if for any $\omega$ we have $M(\omega) = m$, what can you say about $C(\omega)$? Can you use this to eliminate $C$ from the ellipsis in $\Pr[\;\cdots \mathrel| M = m]$?

Next, if you have an equation about the random variable $K$ without reference to $M$, given an equation about $M$, recall the definition of independence of random variables and how it relates to conditional probabilities. Finally, use the probability mass function for $K$, and you'll have an answer.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thanks for taking time to help. Is it possible that for some single value omega in {0,1}^l be that C(omega) = c and M(omega) = m and K(omega) = k such that c = m exor k ? I understand that you want me to think about it and arrive at the solution myself but would it be possible for you explain in much simpler terms ? I'm very bad at probability. To be honest, I still did not understand. Sorry, I'm not able to write in LaTeX here in comments. $\endgroup$
    – rranjik
    May 22, 2018 at 15:49
  • 2
    $\begingroup$ @user3222 $\omega$ is an abstract sample in a sample space, not a bit string. We could make it concrete by defining $\Omega$ to be the cartesian product $\{0,1\}^\ell\times\{0,1\}^\ell$, and then defining defining $M(\omega)=x_0$ and $K(\omega)=x_1$ when $\omega = (x_0, x_1)$, but the language of random variables is convenient because it is not necessary to write out such concrete details. If you're not familiar with this language, I suggest finding an introductory text on probability theory first discussing random variables; then you can return to this. (For LaTeX, use \$dollar signs\$.) $\endgroup$
    – Squeamish Ossifrage
    May 22, 2018 at 15:55
  • 1
    $\begingroup$ Okay. I understand that I should learn probability before I start reading this. Thanks for being nice to me so far. But, can you please give me a hint of what I can conclude about $C(\omega)$ here ? Only thing I can conclude is that it is take up a value within $\{0,1\}^\ell$, and that is all I can guarantee. What should I do knowing that $M(\omega) = m$ ? And, please give a hint on how to go from step 2 to 3 ($\Pr[m \oplus K = c] = \Pr[K = m \oplus c]$). I will not pester you more. Thanks for teaching me this thing LaTeX thing. I'm picking up. $\endgroup$
    – rranjik
    May 22, 2018 at 16:36
  • 1
    $\begingroup$ @user3222 If $C(\omega) = M(\omega) \oplus K(\omega)$ for all $\omega$, and you know $M(\omega) = m$, then…(fill in the blank). For the other question, look up or try to figure out properties of xor. (What's $a \oplus a$ for any $a$?) $\endgroup$
    – Squeamish Ossifrage
    May 22, 2018 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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