Piling-up Lemma - Theory

Theory

The piling-up lemma allows the cryptanalyst to determine the probability that the equality:

holds, where the X 's are binary variables (that is, bits: either 0 or 1).

Let P(A) denote "the probability that A is true". If it equals one, A is certain to happen, and if it equals zero, A cannot happen. First of all, we consider the piling-up lemma for two binary variables, where and .

Now, we consider:

Due to the properties of the xor operation, this is equivalent to

X1 = X2 = 0 and X1 = X2 = 1 are mutually exclusive events, so we can say

Now, we must make the central assumption of the piling-up lemma: the binary variables we are dealing with are independent; that is, the state of one has no effect on the state of any of the others. Thus we can expand the probability function as follows:

Now we express the probabilities p1 and p2 as ½ + ε1 and ½ + ε2, where the ε's are the probability biases — the amount the probability deviates from ½.

Thus the probability bias ε1,2 for the XOR sum above is 2ε1ε2.

This formula can be extended to more X 's as follows:

Note that if any of the ε's is zero; that is, one of the binary variables is unbiased, the entire probability function will be unbiased — equal to ½.

A related slightly different definition of the bias is in fact minus two times the previous value. The advantage is that now with

we have

adding random variables amounts to multiplying their (2nd definition) biases.

Read more about this topic:  Piling-up Lemma

Famous quotes containing the word theory:

    “There is in him, hidden deep-down, a great instinctive artist, and hence the makings of an aristocrat. In his muddled way, held back by the manacles of his race and time, and his steps made uncertain by a guiding theory which too often eludes his own comprehension, he yet manages to produce works of unquestionable beauty and authority, and to interpret life in a manner that is poignant and illuminating.”
    —H.L. (Henry Lewis)

    “[Anarchism] is the philosophy of the sovereignty of the individual. It is the theory of social harmony. It is the great, surging, living truth that is reconstructing the world, and that will usher in the Dawn.”
    —Emma Goldman (1869–1940)

    “There could be no fairer destiny for any physical theory than that it should point the way to a more comprehensive theory in which it lives on as a limiting case.”
    —Albert Einstein (1879–1955)