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 functionrandom permutationmultinomial distributionblock ciphermultidimensional linear cryptanalysiscorrelationcapacitywrong-key hypothesisideal 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},
url = {https://eprint.iacr.org/2019/934}
}
