In this exercise, we review a simple but very powerful mechanism that can be used to...

 

Transcribed Image Text:

In this exercise, we review a simple but very powerful mechanism that can be used to reduce the bias of a source of entropy. Suppose that you have access to a source of bits and you want to generate sequences of random bits. The problem is that the source is not perfect, 1's and 0's may be not equally distributed, and some patterns may be more frequent than others. Let (x0,x1,...,xn) = {0, 1}n+1 be the output of this source. Assume that n is odd. The mechanism works as follows: (a) Pack the bits x0,x1,..., xn in pairs. - (b) For i = 0,..., (n − 1)/2 i. If (x2i, x2i+1) = (0, 1), output 0 ii. Else if (x2i, x2i+1) = (1,0), output 1 iii. Else, do nothing Activate Windows Go to Settings to activ ... Ym be the output of this extraction. Let yo, Exercises: (a) First, assume that each bit x¿ is independent from the rest, with Pr[x; = 1] = p and Pr[x; = 0] = 1 − p for every i = 0,..., n. In this case, i. Compute A. Pr[(x0,x1) = (0, 0)], B. Pr[(x0,x1) = (1,0)], C. Pr[(x0,x1) = (0,1)], and D. Pr[(x0,x1) = (1, 1)]. ii. Compute the probability that, at the i-th step of the algo- rithm, the output is 0, the probability that the output is 1, and the probability that there is no output. iii. Compute Pr[y; = 1] for j = 1, . . ., n. (b) Until now, we assumed that x's are independently distributed, which may be unrealistic. Now suppose that • Pr[(x2i, x2i+1) = ● Pr[(x2i, x2i+1) = • Pr[(x2i, x2i+1) = • Pr[(x2i, x2i+1) = (0, 0)] = 1/3], (1, 1)] = 1/3], (0, 1)] = 1/6 – €], and (1, 0)] = 1/6 + €] for some € = [−1/6, 1/6]. For this case, answer the following questions: For this case, answer the following questions: i. Compute Pr[yj tractor is useful. = 1] for j = 1,...,n and discuss if this ex- ii. Assuryahat pairs of bits are generated independently (i.e. (x0,x1) is generated independently from (x2, x3), for instance), design a generalization of the Von-Neumann extractor that outputs a sequence Y1, ..., Ym with Pr[y; = 1] = 1/2. (This mechanism is a deterministic randomness extractor. These ex- tractors are used to obtain random seeds in hardware. Usually, x¿ are the output of a sensor or a circuit with chaotic behaviour. The output ..., Ym is later combined with other strings, and can be used as a seed for pseudo-random generators.) Yo, In this exercise, we review a simple but very powerful mechanism that can be used to reduce the bias of a source of entropy. Suppose that you have access to a source of bits and you want to generate sequences of random bits. The problem is that the source is not perfect, 1's and 0's may be not equally distributed, and some patterns may be more frequent than others. Let (x0,x1,...,xn) = {0, 1}n+1 be the output of this source. Assume that n is odd. The mechanism works as follows: (a) Pack the bits x0,x1,..., xn in pairs. - (b) For i = 0,..., (n − 1)/2 i. If (x2i, x2i+1) = (0, 1), output 0 ii. Else if (x2i, x2i+1) = (1,0), output 1 iii. Else, do nothing Activate Windows Go to Settings to activ ... Ym be the output of this extraction. Let yo, Exercises: (a) First, assume that each bit x¿ is independent from the rest, with Pr[x; = 1] = p and Pr[x; = 0] = 1 − p for every i = 0,..., n. In this case, i. Compute A. Pr[(x0,x1) = (0, 0)], B. Pr[(x0,x1) = (1,0)], C. Pr[(x0,x1) = (0,1)], and D. Pr[(x0,x1) = (1, 1)]. ii. Compute the probability that, at the i-th step of the algo- rithm, the output is 0, the probability that the output is 1, and the probability that there is no output. iii. Compute Pr[y; = 1] for j = 1, . . ., n. (b) Until now, we assumed that x's are independently distributed, which may be unrealistic. Now suppose that • Pr[(x2i, x2i+1) = ● Pr[(x2i, x2i+1) = • Pr[(x2i, x2i+1) = • Pr[(x2i, x2i+1) = (0, 0)] = 1/3], (1, 1)] = 1/3], (0, 1)] = 1/6 – €], and (1, 0)] = 1/6 + €] for some € = [−1/6, 1/6]. For this case, answer the following questions: For this case, answer the following questions: i. Compute Pr[yj tractor is useful. = 1] for j = 1,...,n and discuss if this ex- ii. Assuryahat pairs of bits are generated independently (i.e. (x0,x1) is generated independently from (x2, x3), for instance), design a generalization of the Von-Neumann extractor that outputs a sequence Y1, ..., Ym with Pr[y; = 1] = 1/2. (This mechanism is a deterministic randomness extractor. These ex- tractors are used to obtain random seeds in hardware. Usually, x¿ are the output of a sensor or a circuit with chaotic behaviour. The output ..., Ym is later combined with other strings, and can be used as a seed for pseudo-random generators.) Yo,

Answer rating: 100% (QA)

The VonNeumann extractor is a method to reduce the bias in a source of entropy by processing its output in pairs and extracting unbiased random bits Lets go through the exercises step by step a Assumi... View the full answer