Dependent Linear Approximations - The Algorithm of Biryukov and Others Revisited

Reference:

Miia Hermelin and Kaisa Nyberg. Dependent linear approximations - the algorithm of Biryukov and others revisited. In J. Pieprzyk, editor, CT-RSA'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 non-negligible 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 log-likelihood 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 = {CT-RSA'10},
    editor = {J. Pieprzyk},
    pages = {318--333},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {Dependent Linear Approximations - The Algorithm of {B}iryukov and Others Revisited},
    volume = {5985},
    year = {2010},
}