A probabilities question

[LandR]

I'm doing a free online crypto course and one of the exercises we had contained this question.

I got it wrong and don't know how to actually work it out.

The question:

Let X be a uniform random variable over the set {0,1}n (That is X is a random string of bits of length n.)

Let Y be a random variable over the set {0,1}n (Not necessarily uniform).

Y is independent of X

Define Z as X xor Y.

What is the probability that Z equals 0n

?

Anyone help me understand how to solve this problem ?

[Marras]

Anyone help me understand how to solve this problem ?

Let's look it one bit a time.

The probability that the first bit of Z is 0 is the probability that the xor of first bits of X and Y is zero. The xor is zero if either both of the bits are zero or if they both are one. Since X and Y are independent with each other and both cases are distinct, the probability can be computed using just multiplication and addition.

So, we get:

P(first bit of Z is 0) = P(first bit of X is 0 and first bit of Y is 0) + P(first bit of X is 1 and first bit of Y is 1)

As X is uniform both possible values for its first bit have the same probability 0.5. The probability for the first bit of Y is not known, but let's say that it's zero with the probability p and one with probability (1 - p).

Then, the probability comes up as:

P(first bit of Z is 0) = 0.5*p + 0.5 * (1-p)

A bit of algebraic manipulation will give you the result, and you can then generalize it to the case of n-bit messages.

[ddt]

I'm doing a free online crypto course and one of the exercises we had contained this question.

I got it wrong and don't know how to actually work it out.

The question:

Let X be a uniform random variable over the set {0,1}n (That is X is a random string of bits of length n.)

Let Y be a random variable over the set {0,1}n (Not necessarily uniform).

Y is independent of X

Define Z as X xor Y.

What is the probability that Z equals 0n

?

Anyone help me understand how to solve this problem ?

As the previous poster already explained, for Z to be 0n, the bits in X must be equal to the respective bits in Y. The easiest way to look at this is: First look at the value of Y. Then for the desired outcome, X must be equal to Y. As X is independent of Y, and X is uniform, this probability is 2-n, irrespective of the value of Y you began with. So the probability is 2-n.

Alternatively, you could write a sum over all possible outcomes of Y and write out the conditional probabilities and come to the same conclusion.

[LandR]

Let's look it one bit a time.

The probability that the first bit of Z is 0 is the probability that the xor of first bits of X and Y is zero. The xor is zero if either both of the bits are zero or if they both are one. Since X and Y are independent with each other and both cases are distinct, the probability can be computed using just multiplication and addition.

So, we get:

P(first bit of Z is 0) = P(first bit of X is 0 and first bit of Y is 0) + P(first bit of X is 1 and first bit of Y is 1)

As X is uniform both possible values for its first bit have the same probability 0.5. The probability for the first bit of Y is not known, but let's say that it's zero with the probability p and one with probability (1 - p).

Then, the probability comes up as:

P(first bit of Z is 0) = 0.5*p + 0.5 * (1-p)

A bit of algebraic manipulation will give you the result, and you can then generalize it to the case of n-bit messages.

Thank you, I think I'm still a bit confused.

So for one bit the probability is:

0.5*p + 0.5 * (1-p) = 0.5p + 0.5- 0.5p = 0.5

So, for each additional bit it would be 0.5 * 0.5.

So for 2 bits it would be 0.25
For 3 bits it would be 0.125

So the probability would be 0.5n

?

So the probability is 2-n.


Oh!

The options on the course quiz were:

http://www.speed-shot.co.uk/images/a1.gif,
http://www.speed-shot.co.uk/images/a2.gif,
http://www.speed-shot.co.uk/images/a3.gif,
and 0.5.

Oh, I just realised. 1 / 2n is 0.5n and 2-n.

Thank you for the help!

[LandR]

One more point though, what if X and Y were both uniform random variables ?

Wouldn't the probability just be the same ?

I don't understand the point of why it was stated that Y is not necessarily uniform..

[edd]

One more point though, what if X and Y were both uniform random variables ?

Wouldn't the probability just be the same ?

I don't understand the point of why it was stated that Y is not necessarily uniform..

It's a crypto course - I presume Y could be message data or some untrusted source or generally something you don't have control of.

[Marras]

I don't understand the point of why it was stated that Y is not necessarily uniform..

The point of that exercise is to show that one-time-pad method of cryptography is provably secure. That is, if you have a uniformly random key that is as long as the message, there is no way to crack the encrypted message.

Here X is the random key and Y is the non-random message, stated in a slightly different way. No matter what the Y is, if X is random, the output is random.

Even though one-time-pad is provably secure, its real implementations can have flaws that make it possible to break it. For example, if X is not truly random it may be possible to decode parts or the whole message. Another flaw is that if you use a completely random X to crypt two different messages Y1 and Y2, both can be trivially cracked.

[LandR]

If anyone is interested, here is the course

https://www.coursera.org/course/crypto

I thought it was very interesting. There were a lot of topics covered and each week had a quiz of 10 or so questions based on the material and interesting programming assignments.

The material was very good quality I thought for a free course and I learned a lot. Although I won't claim to understand the math content!

[ddt]

One more point though, what if X and Y were both uniform random variables ?

Wouldn't the probability just be the same ?

I don't understand the point of why it was stated that Y is not necessarily uniform..

And to add to the other answers: when setting up and proving a mathematical theorem, you try to have as few assumptions as possible in the theorem. Even when you don't (yet) need that general case.