Cryptology ePrint Archive: Report 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.

Category / Keywords: Xiao-Massey lemma, block cipher, linear cryptanalysis, linear approximation, random Boolean function, random transformation, multiple linear cryptanalysis

Date: received 19 May 2017, last revised 10 Oct 2017

Contact author: kaisa nyberg at aalto fi

Available format(s): PDF | BibTeX Citation

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.

Version: 20171010:100500 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]