0
$\begingroup$

I have a small part of data that is n bit long (0 or 1). Probability that a bit is 0 equals p. I also have a key that is used to cipher this data that is 1 bit long. The key will be 0 or 1 for the whole data (equal probability). A XOR operation between the key and the data takes place, and we take the encrypted data.

If the encrypted data contains k zeros (and n-k ones), calculate the probability that the key used is 0.

I am trying to solve this. My thinking until now is that we have 2 events:

Event(A). Original data had k zeros

I can calculate through the binomial distribution.

$P(A) = {{n}\choose{k}}(p^k(1-p)^{n-k} $

Event(B). Encrypted data has k zeros Since a XOR operator is applied if the key was 0, we will have k bits that are zero, if the key bit was 1 we will have n-k bits that are zero. So $P(B) = \frac{P(A)}{2}$

And then i am searching for the conditional probability $(P(key=0|P(B))$

Is my thinking correct?

$\endgroup$

1 Answer 1

0
$\begingroup$

Let $K$ be the event that the key is $1$. We seek for $P(K'|B)$, where $B$ conforms to your definition, i.e. encrypted data has $k$ zeros. Via Bayes rule, we could write: $$P(K'|B)=\frac{P(B|K')P(K')}{P(B)}$$ Here $P(K')=1/2$, and $P(B|K')=P(A)$ (for $A$, I'm using your def. again) because when the key is $0$, having $k$ zeros means having $k$ zeros from the beginning. We can write $P(B)$ via total probability theorem: $$P(B)=P(B|K')P(K')+P(B|K)P(K)=\frac{P(B|K')+P(B|K)}{2}$$ Here, $P(B|K)=P(n-k \ \text{zeros in the original data})={n \choose n-k}p^{n-k}(1-p)^k$. Summing the two yields (noting that ${n \choose k}={n \choose n-k}$): $$P(K'|B)=\frac{p^k(1-p)^{n-k}}{p^k(1-p)^{n-k}+p^{n-k}(1-p)^k}=\frac{1}{1+\left(\frac{p}{1-p}\right)^{n-2k}}$$

Comments on your solution and notation:

As you can see $P(B)\neq P(A)/2$, instead $P(B \cap K')=P(A)/2$, i.e. the numerator in Bayes formulation. Also, $P(key=0|P(B))$ doesn't have meaning, instead you need to write $P(key=0|B)$.

$\endgroup$
1
  • $\begingroup$ Thank you very much gunes! It now starts to make sense! $\endgroup$
    – baskon1
    Commented Mar 8, 2019 at 9:13

Your Answer

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

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