Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
On Multidimensional Linear Cryptanalysis
verfasst von : Phuong Ha Nguyen, Lei Wei, Huaxiong Wang, San Ling
Erschienen in: Information Security and Privacy
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 2
m
2
m
+
mN
, and that of the analysis phase from 2
2
m
to 3
m
2
m
. 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.