Paper 2017/432

Statistical and Linear Independence of Binary Random Variables

Kaisa Nyberg

Abstract

Linear cryptanalysis makes use of statistical models that consider linear approximations over block cipher and random permutation as binary random variables. In this note we develop conditions under which linear independence of binary random variables and statistical independence of their correlations are equivalent properties. As an application we obtain that the correlations of linear combinations of the components of a random $n$-bit to $m$-bit transformation are statistically independent if and only if these linear combinations are linearly independent.

Note: he purpose of this revision is to remove unproven claims stated in Section 4 of the first version of this eprint paper that are actually wrong: independence of two linear approximations of a random permutation and of a cipher with pre- and post-whitening keys. Considering the former case correlations of two different linear approximations of a random permutation are not independent. The reason is that two components of a permutation cannot be independent as their sum must be balanced. Then given one component with a known imbalance, the freedom of choosing the second component to have a certain imbalance will be restricted. There is no such restriction when components of a random transformation are considered. Therefore the claim of Corollary 2 remains valid for linear combinations of components of a random transformation as shown in this revised version.