A probabilities question

LandR · 24th May 2012, 03:23 AM

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}ⁿ (That is X is a random string of bits of length n.)

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

Y is independent of X

Define Z as X xor Y.

What is the probability that Z equals 0ⁿ

?

Anyone help me understand how to solve this problem ?

Marras · 24th May 2012, 03:48 AM

Originally Posted by LandR

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 · 24th May 2012, 04:13 AM

Originally Posted by 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}ⁿ (That is X is a random string of bits of length n.)

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

Y is independent of X

Define Z as X xor Y.

What is the probability that Z equals 0ⁿ

?

Anyone help me understand how to solve this problem ?

As the previous poster already explained, for Z to be 0ⁿ, 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 · 24th May 2012, 07:00 AM

Originally Posted by Marras

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.5ⁿ

?

Originally Posted by ddt

So the probability is 2^-n.

Oh!

The options on the course quiz were:

,

,
and 0.5.

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

Thank you for the help!

LandR · 24th May 2012, 07:05 AM

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 · 24th May 2012, 07:10 AM

Originally Posted by 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..

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 · 24th May 2012, 07:25 AM

Originally Posted by LandR

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 Y₁ and Y₂, both can be trivially cracked.

LandR · 24th May 2012, 07:44 AM

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 · 24th May 2012, 08:19 AM

Originally Posted by 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..

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.

24th May 2012, 03:23 AM	#1
LandR Graduate Poster Join Date: Sep 2009 Posts: 1,028	A probabilities question 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}ⁿ (That is X is a random string of bits of length n.) Let Y be a random variable over the set {0,1}ⁿ (Not necessarily uniform). Y is independent of X Define Z as X xor Y. What is the probability that Z equals 0ⁿ ? Anyone help me understand how to solve this problem ?
LandR Graduate Poster Join Date: Sep 2009 Posts: 1,028

24th May 2012, 03:48 AM	#2
Marras Scholar Join Date: Apr 2012 Posts: 97	Originally Posted by LandR 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.5p + 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.
Marras Scholar Join Date: Apr 2012 Posts: 97

24th May 2012, 04:13 AM	#3
ddt Mafia Penguin Join Date: Dec 2007 Location: Netherlands Posts: 10,323	Originally Posted by 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}ⁿ (That is X is a random string of bits of length n.) Let Y be a random variable over the set {0,1}ⁿ (Not necessarily uniform). Y is independent of X Define Z as X xor Y. What is the probability that Z equals 0ⁿ ? Anyone help me understand how to solve this problem ? As the previous poster already explained, for Z to be 0ⁿ, 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.
	__________________ Proud member of the Solipsistic Autosycophant's Group

24th May 2012, 07:00 AM	#4
LandR Graduate Poster Join Date: Sep 2009 Posts: 1,028	Originally Posted by Marras 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.5p + 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.5p + 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.5ⁿ ? Originally Posted by ddt So the probability is 2^-n. Oh! The options on the course quiz were: , , , and 0.5. Oh, I just realised. 1 / 2ⁿ is 0.5ⁿ and 2^-n. Thank you for the help!
LandR Graduate Poster Join Date: Sep 2009 Posts: 1,028	Last edited by LandR; 24th May 2012 at 07:03 AM. Reason: Me being stupid!

24th May 2012, 07:05 AM	#5
LandR Graduate Poster Join Date: Sep 2009 Posts: 1,028	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..
LandR Graduate Poster Join Date: Sep 2009 Posts: 1,028

24th May 2012, 07:10 AM	#6
edd Graduate Poster Join Date: Nov 2007 Posts: 1,557	Originally Posted by 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.. 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.
edd Graduate Poster Join Date: Nov 2007 Posts: 1,557	__________________ When I look up at the night sky and think about the billions of stars out there, I think to myself: I'm amazing. - Peter Serafinowicz

24th May 2012, 07:25 AM	#7
Marras Scholar Join Date: Apr 2012 Posts: 97	Originally Posted by LandR 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 Y₁ and Y₂, both can be trivially cracked.
Marras Scholar Join Date: Apr 2012 Posts: 97

24th May 2012, 07:44 AM	#8
LandR Graduate Poster Join Date: Sep 2009 Posts: 1,028	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!
LandR Graduate Poster Join Date: Sep 2009 Posts: 1,028

24th May 2012, 08:19 AM	#9
ddt Mafia Penguin Join Date: Dec 2007 Location: Netherlands Posts: 10,323	Originally Posted by 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.. 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.
	__________________ Proud member of the Solipsistic Autosycophant's Group