Abstract
An important question in designing cryptographic functions including substitution boxes (S-boxes) is the relationships among the various nonlinearity criteria each of which indicates the strength or weakness of a cryptographic function against a particular type of cryptanalytic attack. In this paper we reveal, for the first time, interesting connections among the strict avalanche characteristics, differential characteristics, linear structures and nonlinearity of quadratic (S-boxes). In addition, we show that our proof techniques allow us to treat in a unified fashion all quadratic permutations (namely, quadratic (S-boxes that form permutations), regardless of the underlying construction methods. This greatly simplifies the proofs for a number of known results on the nonlinearity characteristics of quadratic permutation. As a by-product, we solve an open problem regarding the existence of differentially 2-uniform quadratic permutations on an even dimensional vector space. Another contribution of this paper is the identifcation of an error in a paper presented by Beth and Ding at EUROCRYPT'93.
Publication Details
Jennifer Seberry, Xian-Mo Zhang and Yuliang Zheng, Relationship among Nonlinearity Criteria In Advances in Cryptography - EUROCRYPT'94, Lecture Notes in Computer Science, Vol 950, Springer-Verlag, Berlin, Heidelberg, New York, (1995), 376-388.