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

Category / Keywords: secret-key cryptography / random function, random permutation, multinomial distribution, block cipher, multidimensional linear cryptanalysis, correlation, capacity, wrong-key hypothesis, ideal cipher

Date: received 16 Aug 2019, last revised 1 Sep 2019

Contact author: kaisa nyberg at aalto fi

Available format(s): PDF | BibTeX Citation

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

Version: 20190901:100028 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]