Paper 2019/934

Linear Approximations of Random Functions and Permutations

Mohsin Khan and Kaisa Nyberg


The goal of this paper is to investigate the linear cryptanalysis of random functions and permutations. The motivation of this work is twofold. First, before a practical cipher can be distinguished from an ideal one, the cryptanalyst must have an accurate understanding of the statistical behavior of the ideal cipher. Secondly, this issue has been neglected both in old and in more recent studies, particularly when multiple linear approximations are being used simultaneously. Traditionally, the models have been based on the average behavior and simplified using other artificial assumptions such as independence of the linear approximations. The new models given in this paper are realistic, accurate and easy to use. They are backed up by standard statistical tools such as Pearson's chi-squared test and finite population correction and shown to work well in small practical examples.

Note: In this revised version some minor editorial errors and inaccurate formulations have been corrected.

Available format(s)
Secret-key cryptography
Publication info
random functionrandom permutationmultinomial distributionblock ciphermultidimensional linear cryptanalysiscorrelationcapacitywrong-key hypothesisideal cipher
Contact author(s)
kaisa nyberg @ aalto fi
2019-09-01: revised
2019-08-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mohsin Khan and Kaisa Nyberg},
      title = {Linear Approximations of Random Functions and Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2019/934},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.