On multidimensional linear cryptanalysis

DSpace/Manakin Repository


Search DR-NTU

Advanced Search Subject Search


My Account

On multidimensional linear cryptanalysis

Show full item record

Title: On multidimensional linear cryptanalysis
Author: Nguyen, Phuong Ha; Wei, Lei; Wang, Huaxiong; Ling, San
Copyright year: 2010
Abstract: 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 2m 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.
Subject: DRNTU::Science::Mathematics
Type: Journal Article
Series/ Journal Title: Lecture notes in computer science
School: School of Physical and Mathematical Sciences
Rights: © 2010 Springer-Verlag Berlin Heidelberg. This is the author created version of a work that has been peer reviewed and accepted for publication by Lecture Notes in Computer Science, Springer-Verlag Berlin Heidelberg. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: http://dx.doi.org/10.1007/978-3-642-14081-5_3
Version: Accepted version

Files in this item

Files Size Format View
On Multidimensional Linear Cryptanalysis.pdf 273.1Kb PDF View/Open

DOI Query

- Get published version (via Digital Object Identifier)

This item appears in the following Collection(s)

Show full item record


Total views

All Items Views
On multidimensional linear cryptanalysis 317

Total downloads

All Bitstreams Views
On Multidimensional Linear Cryptanalysis.pdf 185

Top country downloads

Country Code Views
United States of America 77
China 53
Singapore 12
France 8
Russian Federation 7

Top city downloads

city Views
Mountain View 43
Xinxing 15
Singapore 11
East Lansing 9
Beijing 3