1
$\begingroup$

First, some well-known results are as follows. For random variables $X$ and $Y$, we have $$H(X,Y) \leq H(X) + H(Y).$$ The equality is achieved when $X$ and $Y$ are independent.

Second, in one-time pad, random variables $M$, $K$ and $C$ are used to denote a plain text, a private key and the codeword generated by $M \bigoplus K$ (modulo-2 operation), respectively. Note that $K$ is independent of $M$. We assume an eavesdropper also received the transmitted codeword $C$ through a public channel, but he does not know the key $K$.

Then my questions are as follows?

1) Are $M$ and $C$ correlated? (The answer is "Yes" to me due to the post https://math.stackexchange.com/questions/1218305/if-x-and-y-are-correlated-random-varibales-and-z-is-independent-of-x-and-y-then )

2) If they are correlated, $H(M|C) < H(M)$ should be true according to the statements in the beginning. However, in one-time pad, perfect secrecy can be achieved, which means $H(M|C) = H(M)$ when $H(M) \leq H(K)$. Can anyone help me out of this confusion?

Thank you very much in advance.

$\endgroup$
  • $\begingroup$ 1) How do you define "correlated"? 2) $H(M|C) \le H(M)$ is always true. Perfect secrecy means $H(M|C) = H(M)$. $\endgroup$ – fkraiem Apr 16 '15 at 4:00
  • $\begingroup$ I mean "linearly correlated", the definition of which can be found in the wiki en.wikipedia.org/wiki/… . It is relative to independent condition. And I also want to correct the statement that, when they are correlated, we have $H(M|C) < H(M)$. $\endgroup$ – zhu Apr 16 '15 at 4:07
  • $\begingroup$ This seems irrelevant here. How would you define the standard deviation of $M$ and $C$, or their covariance? $\endgroup$ – fkraiem Apr 16 '15 at 4:09
2
$\begingroup$

Are M and C correlated?

No.

The distribution that the values the M and C may take on are independent of each other. The condition probability distribution that M has is unchanged no matter what the observed C value is.

This is true whether you are using the statistical meaning of correlation, or whether you are looking more specifically at linear correlations.

Here's why the answer to the math stack exchange is "they might be correlated", while the corresponding answer here is "they aren't"; consider in the math stack exchange case that $X$ and $Z$ are independent variables that can take the values 0 and 1 with probability 0.5 each, and that $X=Y$, and that the addition is integer addition. In this case, if $Y$ is 0, $X+Z$ can take on the values 0 and 1, while if $Y$ is 1, $X+Z$ can take on the values 1 and 2; hence the probability distribution of $Y$ and $X+Z$ are not independent.

This corner case can't happen with one time pad.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ About the last statement, I think the two questions are related. We can think $Y$ and $X$ are the same, then the answer there will be $X$ and $X+Z$ are correlated ($Z$ is independent of $X$). Here, the question is about the correlation between $M$ and $C=M \oplus K $ ($K$ is independent of $M$). $\endgroup$ – zhu Apr 16 '15 at 4:27
  • $\begingroup$ @zhu: if you think there might be a correlation, you might find it fruitful to select a probability distribution for $M$, and compute the resulting distribution of $M \oplus K$ (assuming an independent $K$) $\endgroup$ – poncho Apr 16 '15 at 4:35
  • $\begingroup$ Thanks for your help. From your answer, I think maybe the difference of the correlation results in the two cases is caused by different math operations (sum and modulo-2) are used. $\endgroup$ – zhu Apr 16 '15 at 4:52
  • $\begingroup$ @zhu That is correct. With XOR, for every possible $M$ and every possible $C$ there exists a single $K$ such that $M\oplus K=C$. For addition, this is not necessarily true if $M$, $K$, and $C$ have a maximum size. $\endgroup$ – cpast Apr 16 '15 at 5:13

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.