TCS / Research / Publications / Multidimensional Linear Cryptanalysis of Reduced Round Serpent
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Multidimensional Linear Cryptanalysis of Reduced Round Serpent

Reference:

Miia Hermelin, Joo Yeon Cho, and Kaisa Nyberg. Multidimensional Linear Cryptanalysis of Reduced Round Serpent. In Yi Mu, Willy Susilo, and Jennifer Seberry, editors, Information Security and Privacy, 13th Australasian Conference, ACISP 2008 Wollongong, Australia, July 7-9, 2008, Proceedings, volume 5107 of LNCS, pages 203–215. Springer, 2008.

Abstract:

Various authors have previously presented different approaches how to exploit multiple linear approximations to enhance linear cryptanalysis. In this paper we present a new truly multidimensional approach to generalise Matsui's Algorithm 1. We derive the statistical framework for it and show how to calculate multidimensional probability distributions based on correlations of one-dimensional linear approximations. The main advantage is that the assumption about statistical independence of linear approximations can be removed. Then we apply these new techniques to four rounds of the block cipher Serpent and show that the multidimensional approach is more effective in recovering key bits correctly than the previous methods that use a multiple of one-dimensional linear approximations.

Keywords:

multidimensional, linear cryptanalysis, Matsui's algoritm 1, gain, linear approximation, Serpent

Suggested BibTeX entry:

@inproceedings{her08acisp,
    author = {Miia Hermelin and Joo Yeon Cho and Kaisa Nyberg},
    booktitle = {Information Security and Privacy, 13th Australasian Conference, ACISP 2008 Wollongong, Australia, July 7-9, 2008, Proceedings},
    editor = {Yi Mu and Willy Susilo and Jennifer Seberry},
    pages = {203--215},
    publisher = {Springer},
    series = {LNCS},
    title = {Multidimensional {L}inear {C}ryptanalysis of {R}educed {R}ound {S}erpent},
    volume = {5107},
    year = {2008},
}

This work is not available online here.

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.