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 practical and ideal block ciphers as binary random variables. Recently, more complex models have been proposed that take also into account the statistical behavior of correlations of linear approximations over the key space of the cipher and over the randomness of the ideal cipher. The goal of this ongoing work is to investigate independence properties of linear approximations and their relationships. In this third revised version we show that the assumptions of Proposition~1 of the previous version are contradictory and hence renders that result useless. In particular, we prove that linear and statistical independence of binary random variables are equivalent properties in a vector space of variables if and only if all non-zero variables in this vector space are balanced, that is, correspond to components of a permutation. This study is motivated by finding reasonable wrong-key hypotheses for linear cryptanalysis and its generalizations which will also be discussed.

Category / Keywords: Xiao-Massey lemma, block cipher, linear cryptanalysis, linear approximation, random Boolean function, random vectorial Boolean function, multidimensional linear cryptanalysis, wrong-key hypothesis

Date: received 19 May 2017, last revised 30 Jan 2018

Contact author: kaisa nyberg at aalto fi

Available format(s): PDF | BibTeX Citation

Note: This is an updated version of ongoing work.

Version: 20180130:130651 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]