I read a paper of linear cryptanalysis that is J.Daemen et al's Probability distribution of correlation and differentials in block cipher.

In this paper's lemma 8's proof, I can't understand this formula (page.13).

The number of balanced Boolean functions $g(a)$ for a given value of $x$ is :

$$ {{2^{n-1}} \choose {2^{n-2}+x}} {{2^{n-1}} \choose {2^{n-2}-x}} = {{2^{n-1}} \choose {2^{n-2}+x}}^2$$ and

If we divide this by the total number of balanced Boolean functions,..."

Please, tell me how this formula is derived.


So $x$ measures the departure from balance in the left half of the truth table, say it is the excess number of 1's in the left half of length $2^{n-1}$. By the definition of binomial coefficients there are $$\binom{2^{n-1}}{2^{n-2}+x}$$ such vectors. This is the first factor. The second factor is the count of vectors missing $x$ 1's, since the overall truth table is balanced.

Using $$\binom{a}{b}=\binom{a}{a-b}$$ completes the argument.

  • $\begingroup$ Why the probability is computed by only g(a)? u, v, alpha don't affect probability? $\endgroup$
    – jyj
    Dec 7 '18 at 2:44
  • $\begingroup$ Yes it is. Read the discussion preceding equation (20) starting in the previous page. $\endgroup$
    – kodlu
    Dec 7 '18 at 3:45
  • $\begingroup$ Glad it was helpful. Perhaps you can upvote the answer, if you liked it :-) $\endgroup$
    – kodlu
    Dec 8 '18 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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