An Algorithm for Improving Algebraic Degree of S-Box Based on Affine Equivalence Transformation

Introduction

Shannon (1949) defined the property of confusion which should exist in an encryption system. Basically confusion is required so that the ciphertext is related to both the plaintext and secret key, in a complex way. In modern block ciphers, this property can be provided by a component called a S-box. Since the S-box plays an important role in a block cipher as it is the only nonlinear part of the cipher in most cases. To avoid various attacks on the ciphers and for efficient software implementation, S-boxes are required to satisfy a lot of properties, for instance being a permutation defined on the fields with even degrees, with a high algebraic degree, a low differential uniformity and a high nonlinearity, etc. (Tan & Zhu, 2016; Ivanov, N. Nikolov, & S. Nikova, 2016; McLaughlin & Clark, 2013). However, it seems very difficult to find an S-box satisfying all the criteria.

Actually, the S-box of low algebraic degree is vulnerable to many attacks, for instance higher-order differential attacks, algebraic attacks or cube attacks (Boura & Canteaut, 2013; Boura, Canteaut, & De Canniere, 2011). In this paper the authors propose an algorithm that allows improving algebraic degree of the S-box while not affecting its other properties in order to increase ability to resist the attacks mentioned above. This proposed algorithm is based on affine equivalence transformation of S-boxes (Biryukov, De Canniere, Braeken, & Preneel, 2003; Carlet, 2010).

The rest of the paper is organized as follows: In the second section, some fundamental definitions are given as a refresher, to help better understand the research results given later in the article, and the main cryptographic properties of S-box are discussed. In the third section, the researchers present and discuss our algorithm. Finally, Section 4 summarizes the paper.

Definitions And Preliminaries

In this section the authors will briefly recall some of the basic definitions and properties of Boolean functions. For a comprehensive survey on Boolean functions the researchers refer to (Carlet, 2010; Crama, & Hammer, 2010; McLaughlin, & Clark, 2013).

S-box: Let the S-box of an n-binary input into m-binary output mapping is denoted by S. Then and to each some is assigned by , where is the 1-dimensional Boolean space. Clearly, S can be considered as a vectorial Boolean function consisting of m individual Boolean functions , where and for . These functions are called coordinate Boolean functions of the S-box S and it is well known that most of the desirable cryptographic properties of S can be defined in terms of their linear combinations. The S-box coordinate Boolean functions and all their linear combinations are referred as the S-box component Boolean functions.