Linear Approximations of Random Functions and Permutations

Mohsin Khan; Kaisa Nyberg

Paper 2019/934

Linear Approximations of Random Functions and Permutations

Mohsin Khan and Kaisa Nyberg

Abstract

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.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
Keywords: random function random permutation multinomial distribution block cipher multidimensional linear cryptanalysis correlation capacity wrong-key hypothesis ideal cipher
Contact author(s): kaisa nyberg @ aalto fi
History: 2019-09-01: revised; 2019-08-18: received; See all versions
Short URL: https://ia.cr/2019/934
License: CC BY

BibTeX

@misc{cryptoeprint:2019/934,
      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{https://eprint.iacr.org/2019/934}},
      url = {https://eprint.iacr.org/2019/934}
}