# Evolutionary Block Cipher Against Multidimensional Linear And Differential Cryptanalysis

July 10, 2012

Cryptology is one of the most important techniques in the field of information security, which provides an abundance of services including privacy, data integrity, authentication, access control, anonymity, non-repudiation. The high level of security, efficiency and ease of implementation of a cryptosystem are the main design aims of cryptographers. Prof. ZHANG Huanguo and his group from Key Laboratory of Aerospace Information Security and Trusted Computing of Ministry of Education, Wuhan University, have been undertaking research on a entirely new cryptography–Evolutionary Cryptography–during the past 10 years, and have achieved a series of impressive research results on the design, hardware/software implementation and cryptanalysis of the evolutionary cryptography. Their latest work, titled “Capability of evolutionary cryptosystems against differential cryptanalysis” and “Evolutionary cryptography against multidimensional linear cryptanalysis”, were published in Refs.[2] and [1] respectively.

In modern times, the term cryptosystem refers to the ordered list of elements of finite possible plaintexts (P), finite possible ciphertexts (C), finite possible keys (K), and algorithms for encryption (E) and decryption (D). Encryption is the process of converting plaintext into unintelligible ciphertext, whereas decryption is the reverse process to encryption that reveals the plaintext from the unintelligible ciphertext. From a mathematical point of view, a cryptosystem can be precisely expressed as a five-tuple (P, C, K, E, D). Up to now, all known cryptosystems have been designed to encrypt and decrypt the data with fixed algorithms and randomly-changed key. More specifically, suppose E is an encryption algorithm and K=K0K1“¦Kt-1 is the key, the process of encrypting plaintexts P=P0P1“¦Pt-1 is as below:

C0=E(P0, K0), C1=E(P1, K1), “¦, Ct-1=E(Pt-1, Kt-1),
where P, C, K belong to the plaintexts set P, the ciphertexts set C and the keys set K respectively.

Inspired by the fact that frequent replacement of the key contributes to a cryptosystem’s high secrecy level and the success of evolutionary computing, which applies biological evolution into computer science, Prof. ZHANG Huanguo concentrated on replacing both encryption algorithms and keys, and introduced a novel encryption scheme Evolutionary Cryptography. This scheme is distinguished from known cryptographies by two features: the encryption/decryption algorithms are alterable instead of being fixed and the encryption algorithms are replaced with increasingly cryptographically-strong ones from time to time. It can be roughly described in the following way: suppose E-r is an initial encryption algorithm with low level of security, the encryption scheme starting from E-r, evolves through E-r+1, “¦ , E0, E1,“¦, Et-1 with increasingly higher levels of security. The evolving phase from E-r to E0 acts like an embryonic stage. In this embryonic stage, the encryption algorithm E-i does not in practice meet security requirements until it evolves into E0, but afterwards it is secure enough to be used in practical applications and its security level becomes increasingly higher as the process evolves. The evolution process of the encryption algorithms is characterized as follows:

E-r â†’ E-r+1â†’E-r+2â†’“¦ â†’E-1â†’E0â†’E1â†’“¦ â†’Et-1
S(E-r)where S(Ei) denotes the criterion of Ei resisting some known cryptanalysis, and the encryption process is C0=E0(P0, K0), C1=E1(P1, K1), “¦, Ct-1=Et-1(Pt-1, Kt-1).

In general, the resistance against some known cryptanalysis of a cryptosystem mainly depends on some of its fundamental cryptographic components. For instance, the nonlinear cryptographic component S-boxes and the linear permutation used to produce confusion and diffusion in block ciphers play a crucial role in resisting differential cryptanalysis and linear cryptanalysis. A variety of attacks has been found against the known cryptosystems, and these consequently lead to criteria cryptographic components must satisfy. More concretely, the resistance of the cryptosystems to known attacks can be quantified through some fundamental characteristics (some, more related to confusion, and some, more related to diffusion) of the cryptographic functions used in these. Taking the block cipher AES as an example, the criterion nonlinearity of S-box was introduced to quantify its resistance related to linear cryptanalysis; while the differential uniformity was used to quantify its resistance related to differential cryptanalysis. An evolutionary cryptosystem can be explicitly characterized as a six-tuple (E, Ï‰, Î©, Î“, Î¦, f ):

1.E denotes an encryption algorithm;
2.Ï‰ denotes some crucial cryptographic components in the cipher E, such as the nonlinear S-box;
3.Î© denotes the set of all possible cryptographic components Ï‰;
4.Î“ denotes some known criteria of the cryptographic component Ï‰. For instance, for the cryptographic component S-box in block cipher, the set Î“ includes the criteria nonlinearity, differential uniformity and algebraic degree;
5.Î¦ denotes the set of all possible mappings from Î© to itself;
6.f denotes a mapping from Î© to R+, the so-called evaluation function, and its value is called the fitness value.

The two above-cited papers discussed the security of evolutionary block cipher against linear and differential cryptanalysis. Linear and differential cryptanalysis, introduced in the early 1990s, are two most widely-used attacks on iterated block ciphers, and both are important tools in evaluating the security of block ciphers. In the past two decades, much improvement in employing linear attacks has been made, the most remarkable being a multidimensional extension of original linear cryptanalysis.

In those papers, we exploited separately the security of evolutionary block cipher against multidimensional linear cryptanalysis and differential cryptanalysis. Based on a comparison of complexity and success rate between multidimensional linear cryptanalysis and differential cryptanalysis, the research results indicate that the evolutionary block cipher performs more securely and robustly than its initial fixed block cipher does in regards resisting these two important attacks.

On the Net: