Reference:
Miia Hermelin and Kaisa Nyberg. Dependent linear approximations  the algorithm of Biryukov and others revisited. In J. Pieprzyk, editor, CTRSA'10, volume 5985 of Lecture Notes in Computer Science, pages 318–333. Springer, 2010.
Abstract:
Biryukov, et al., showed how it is possible to extend Matsui's Algorithm 1 to find several bits of information about the secret key of a block cipher. Instead of just one linear approximation, they used several linearly independent approximations that were assumed to be statistically independent. Biryukov, et al., also suggested a heuristic enhancement to their method by adding more linearly and statistically dependent approximations. We study this enhancement and show that if all linearly dependent approximations with nonnegligible correlations are used, the method of Biryukov, et al., is the same as the convolution method presented in this paper. The data complexity of the convolution method can be derived without the assumption of statistical independence. Moreover, we compare the convolution method with the optimal ranking statistic loglikelihood ratio, and show that their data complexities have the same order of magnitude in practice. On the other hand, we show that the time complexity of the convolution method is smaller than for the other two methods.
Keywords:
Matsui's Algorithm 1, linear cryptanalysis, multidimensional cryptanalysis, method of Biryukov, convolution method
Suggested BibTeX entry:
@inproceedings{her10ctrsa,
author = {Miia Hermelin and Kaisa Nyberg},
booktitle = {CTRSA'10},
editor = {J. Pieprzyk},
pages = {318333},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
title = {Dependent Linear Approximations  The Algorithm of {B}iryukov and Others Revisited},
volume = {5985},
year = {2010},
}
