Linear Cryptanalysis and Its Extensions

摘要

During its 20 years of existence in public cryptographic literature, the method of Linear cryptanalysis has gained its position as one of the most significant generic methods of statistical cryptanalysis [8]. The main goal of this invited talk is to discuss some recent extensions of linear cryptanalysis for block ciphers. As these extensions typically exploit several linear approximations simultaneously, the statistical analysis involves distinguishing various types of probability distributions of the cipher data. We will present the details of the statistical model of the Zero-correlation cryptanalysis [2] and in particular its multidimensional version [3]. We will also present a proper statistical model for the Statistical saturation attack [5], which was recently shown in [7] to be mathematically equivalent with the Multidimensional linear cryptanalysis [6]. We will explain how this equivalence naturally extends itself to the statistical models of these attacks. Recently we showed that linear approximations can be useful also outside the traditional domain of linear cryptanalysis [1]. Using the link between differential and linear cryptanalysis established in [4] we estimated expected differential probabilities using known strong linear approximations. As a final topic of this invited talk, we want to demonstrate that this link has potential applications also in the opposite direction. As an example, we will recall the classical statistical cryptanalysis method of Index of coincidence, where probabilities of differences, in particular zero-differences, are used to evaluate the nonuniformity of the ciphertext distribution.