ABSTRACT
Substitution boxes or S-boxes are very important ingredients in the construction of secret key cryptographic algorithms. Their main role is to break the linearity of these algorithms. Due to the binary nature of computers, most S-boxes act on bits. They take a number of bits as input and produce a number of bits as output. Having S-boxes with good properties is essential to the security of secret-key encryption. For example, it is well known that the security of the DES algorithm drops dramatically when its S-boxes are replaced without care. The cryptanalysis of FEAL in [BS91b, GC91, MY92, TCG92], which is an encryption algorithm similar to DES, illustrates this point. As a consequence, the properties of S-boxes need to be studied with care when choosing them, or when trying to cryptanalyze an encryption algorithm. In particular, the linear and differential properties of S-boxes, which are respectively used by linear [Mat93, Mat94a, Mat94b, TSM94] and differential [BS91a, BS92, BS93] cryptanalysis, should always be determined.
