Multidimensional Extension of Matsui's Algorithm 2

Reference:

Miia Hermelin, Joo Yeon Cho, and Kaisa Nyberg. Multidimensional Extension of Matsui's Algorithm 2. In Orr Dunkelman, editor, Fast Software Encryption 2009, volume 5665 of Lecture Notes in Computer Science, pages 209–227. Springer, 2009.

Abstract:

Matsui's one-dimensional Alg. 2 can be used in recovering bits of the last round key of a block cipher. In this paper a truly multidimensional extension of Alg. 2 based on established statistical theory is presented. Two possible methods, an optimal method based on the log-likelihood ratio and a method based on a goodness-of-fit test are compared in theory and by practical experiments on reduced round Serpent. The theory of advantage by Selc cuk is generalised in multiple dimensions and the advantages and data, time and memory complexities for both methods are derived.

Keywords:

Matsui's algorithm 2, multidimensional, linear cryptanalysis, key ranking, ranking statistic, advantage, goodness-of-fit, log-likelihood ratio

Suggested BibTeX entry:

@inproceedings{her09fse,
    author = {Miia Hermelin and Joo Yeon Cho and Kaisa Nyberg},
    booktitle = {Fast Software Encryption 2009},
    editor = {Orr Dunkelman},
    pages = {209--227},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {Multidimensional {E}xtension of {M}atsui's {A}lgorithm 2},
    volume = {5665},
    year = {2009},
}