Enhanced Criteria on Differential Uniformity and Nonlinearity of Cryptographically Significant Functions

Abstract. The Substitution box (Sbox) plays an important role in the design of both block and stream ciphers as, in most cases, it is the only nonlinear layer of the cipher. There are many requirments of the choice of the Sbox to aviod various attacks. In this paper, we mathematically characterizes the truncated differential cryptanalysis invented by Kundsen, which is called the t-th differential uniformity in this paper. It is found that, although some S-boxes used in certain previously ciphers have optimal differential uniformity, they have very bad t-th differential uniformity for some integer t. This gives an entile possibility to improve the cryptanalysis of these ciphers. As an application of this concept, we propose a construction of a distinguisher of a block cipher by the bias rate of some differential sequences defined in this paper, which is obtained via the t-th differential uniformity. By this algorithm, we found that there are many keys in the recently proposed lightweight LED-64 are weak, namely they are distinguishable from a uniform cipher. Furthermore, we compute the t-th differential uniformity of all 4-bit S-boxes used in previous designed ciphers, and the result of the Sbox used in ZUC, SNOW 3G and AES. Particularly, it is found that the Sbox used in ZUC has very bad 3rd differential uniformity. The second contribution of this paper is to target the following scenario. For many ciphers, there exists a structure consisting of the composition of a linear function a from F2k to F2n and an Sbox S define