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.

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
random functionrandom permutationmultinomial distributionblock ciphermultidimensional linear cryptanalysiscorrelationcapacitywrong-key hypothesisideal cipher
Contact author(s)
kaisa nyberg @ aalto fi
History
2019-09-01: revised
See all versions
Short URL
https://ia.cr/2019/934

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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.