On multidimensional linear cryptanalysis

Phuong Ha Nguyen, Lei Wei, Huaxiong Wang, San Ling

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

7 Citations (Scopus)


Matsui's Algorithms 1 and 2 with multiple approximations have been studied over 16 years. In CRYPTO'04, Biryukov et al. proposed a formal framework based on m statistically independent approximations. Started by Hermelin et al. in ACISP'08, a different approach was taken by studying m-dimensional combined approximations from m base approximations. Known as multidimensional linear cryptanalysis, the requirement for statistical independence is relaxed. In this paper we study the multidimensional Alg. 1 of Hermelin et al.. We derive the formula for N, the number of samples required for the attack and we improve the algorithm by reducing time complexity of the distillation phase from 2 m N to 2m2m + mN, and that of the analysis phase from 22m to 3m2m. We apply the results on 4- and 9-round Serpent and show that Hermelin et al. actually provided a formal model for the hypothesis of Biryukov et al. in practice, and this model is now much more practical with our improvements.

Original languageEnglish
Title of host publicationInformation Security and Privacy - 15th Australasian Conference, ACISP 2010, Proceedings
EditorsRon Steinfeld, Philip Hawkes
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Number of pages16
ISBN (Print)3642140807, 9783642140808
Publication statusPublished - 2010
Event15th Australasian Conference on Information Security and Privacy, ACISP 2010 - Sydney, NSW, Australia
Duration: 5 Jul 20107 Jul 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6168 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


Other15th Australasian Conference on Information Security and Privacy, ACISP 2010
CitySydney, NSW


Dive into the research topics of 'On multidimensional linear cryptanalysis'. Together they form a unique fingerprint.

Cite this