TY - JOUR

T1 - Differential-Linear Cryptanalysis Revisited

AU - Blondeau, Celine

AU - Leander, Gregor

AU - Nyberg, Kaisa

PY - 2017/7

Y1 - 2017/7

N2 - The two main classes of statistical cryptanalysis are the linear and
differential attacks. They have many variants and enhancements such as
the multidimensional linear attacks and the truncated differential
attacks. The idea of differential-linear cryptanalysis is to apply first
a truncated differential attack and then a linear attack on different
parts of the cipher and then combine them to a single distinguisher over
the cipher. This method is known since 1994 when Langford and Hellman
presented the first differential-linear cryptanalysis of the DES.
Recently, in 2014, Blondeau and Nyberg presented a general link between
differential and linear attacks. In this paper, we apply this link to
develop a concise theory of the differential-linear cryptanalysis. The
differential-linear attack can be, in the theoretical sense, considered
either as a multidimensional linear or a truncated differential attack,
but is for both types an extreme case, which is best measured by the
differential-linear bias. We give an exact expression of the bias in a
closed form under the sole assumption that the two parts of the cipher
are independent. Unlike in the case of ordinary differentials and linear
approximations, it is not granted that restricting to a subset of
characteristics of a differential-linear hull will give a lower bound on
the absolute value of the bias. Given this, we revisit the previous
treatments of differential-linear bias by Biham et al. in 2002–2003, Liu
et al. in 2009, and Lu in 2012, and formulate assumptions under which a
single differential-linear characteristic gives a close estimate of the
bias. These results are then generalized by considering a subspace of
linear approximations over the second part of the cipher. To verify the
assumptions made, we present several experiments on a toy-cipher.

AB - The two main classes of statistical cryptanalysis are the linear and
differential attacks. They have many variants and enhancements such as
the multidimensional linear attacks and the truncated differential
attacks. The idea of differential-linear cryptanalysis is to apply first
a truncated differential attack and then a linear attack on different
parts of the cipher and then combine them to a single distinguisher over
the cipher. This method is known since 1994 when Langford and Hellman
presented the first differential-linear cryptanalysis of the DES.
Recently, in 2014, Blondeau and Nyberg presented a general link between
differential and linear attacks. In this paper, we apply this link to
develop a concise theory of the differential-linear cryptanalysis. The
differential-linear attack can be, in the theoretical sense, considered
either as a multidimensional linear or a truncated differential attack,
but is for both types an extreme case, which is best measured by the
differential-linear bias. We give an exact expression of the bias in a
closed form under the sole assumption that the two parts of the cipher
are independent. Unlike in the case of ordinary differentials and linear
approximations, it is not granted that restricting to a subset of
characteristics of a differential-linear hull will give a lower bound on
the absolute value of the bias. Given this, we revisit the previous
treatments of differential-linear bias by Biham et al. in 2002–2003, Liu
et al. in 2009, and Lu in 2012, and formulate assumptions under which a
single differential-linear characteristic gives a close estimate of the
bias. These results are then generalized by considering a subspace of
linear approximations over the second part of the cipher. To verify the
assumptions made, we present several experiments on a toy-cipher.

KW - Bias of differential-linear approximation

KW - Block cipher

KW - Differential cryptanalysis

KW - Linear cryptanalysis

KW - Multidimensional linear approximation

KW - Truncated differential

UR - http://www.scopus.com/inward/record.url?scp=84990892307&partnerID=8YFLogxK

U2 - 10.1007/s00145-016-9237-5

DO - 10.1007/s00145-016-9237-5

M3 - Article

AN - SCOPUS:84990892307

VL - 30

SP - 859

EP - 888

JO - Journal of Cryptology

JF - Journal of Cryptology

SN - 0933-2790

IS - 3

ER -