The goal of this thesis is to construct substitution boxes (S-boxes) in block ciphers for the protection of information in current communications systems. The general domain of the thesis is symmetric cryptography (a.k.a. secret key cryptography) and the sub-domain is the study of constructions of S-boxes in block ciphers. Most block ciphers are constructed using Boolean (n,m)-functions, where n denotes the number of input bits and m denotes the number of output bits. The most commonly used block cipher is the Advanced Encryption Standard (AES). AES has been adopted by the National Institute of Standards and Technology (NIST) of the United States in 2001. Since its original publication, AES has been cryptanalyzed but no attack has been practically successful. Its designers chose the Inverse (8,8)-function as an S-box for it because of its good cryptographic properties, such as a high nonlinearity, a low differential uniformity, bijectivity and a large algebraic degree. The research for cryptographically strong S-boxes has been a target for researchers around the world. These S-boxes have to satisfy the different cryptographic properties which are necessary to prove resistance against the main cryptanalysis techniques (or attacks) such as linear, differential, higher order differential cryptanalysis and their variants. Over time, attackers are likely to find ways to exploit the potential weaknesses of the AES S-box. In particular, its S-Box has the peculiarity of being a power function, which is an advantage for the designer but can also be one for the attacker, and of having a low graph algebraic immunity. Additionally, the AES S-box is computed with at least four nonlinear multiplications which makes it slower than desirable, especially when implementing countermeasures against side-channel attacks with additive masking techniques. A cryptographically strong S-box or (n,m)-function should satisfy four cryptographic properties when n equals m. First, it must be bijective (at least in a SubstitutionPermutation-Network block cipher). Second, it must be almost perfect nonlinear (APN) or at least have low differential uniformity to resist differential attacks. Third, it must have high nonlinearity to resist linear attacks. Fourth, it must not have a very low algebraic degree (i.e. the algebraic degree must be three or more) to resist higher order differential attacks. Similarly, when n is larger than m as used in Feistel-type block ciphers, the S-boxes should satisfy four properties. First, it would better be balanced [103], that is, its output values are uniformly distributed. Furthermore, these S-boxes should have a high nonlinearity, a low differential uniformity, and should not have a very low algebraic degree. In this thesis, two families of differentially 4-uniform (n,n - 1)-functions are constructed, one based on two EA-equivalent (n-1,n-1)-functions derived from the Cubic (n-1,n-1)-function, the other based on two EA-equivalent (n-1,n-1)-functions derived from the Inverse (n-1,n-1)-function. Differentially 4-uniform (n,n-1)-functions are optimal with respect to differential uniformity. Constructing them is considered to be as difficult as constructing APN (n,n)-functions unless the straightforward construction composing an APN (n,n)-function on the left by a surjective ane (n,n-1)-function is used. The two constructed families use a method and its generalization that can be utilized in the future to construct other families of di?erentially 4-uniform (n,n-1)-functions as well. These two constructed families allow constructing differentially 4-uniform (n,n)functions by concatenating the output bit of any (n,1)-function to the n-1 output bits of our constructed differentially 4-uniform (n,n-1)-functions. By concatenating the output of well-chosen (n,1)-functions, one can guarantee that certain cryptographic properties are preserved, such as balancedness, high nonlinearity and high algebraic degree. We also show a way to raise the algebraic degree of one of these constructed families of differentially 4-uniform (n,n-1)-functions by using a method based on the notion of CCZ-equivalence. In particular, we were able to improve the algebraic degree of one of these families from two to three. In another direction, we were also able to generalize further these two methods to a method for constructing differentially 8-uniform (n,n-2)functions. In particular, we constructed two families of differentially 8-uniform (n,n-2)functions, one based on four EA-equivalent (n-2,n-2)-functions derived from the Cubic (n-2,n-2)-function, the other based on four EA-equivalent (n-2,n-2)-functions derived from the Inverse (n - 2,n - 2)-function. It is an open problem whether differentially 6-uniform (n,n - 2)-functions do exist when n is larger than 5. In the case of their in-existence, differentially 8-uniform (n,n - 2)-functions will be the optimal (n,n - 2)functions with respect to differential uniformity.
| Date of Award | Sep 2016 |
|---|
| Original language | American English |
|---|
| Supervisor | Chan Yeun (Supervisor) |
|---|