Relating differential distribution tables to other properties of substitution boxes (Q1970570)

Relationships among various characteristics of an \(n \times m\) S-box \((n > m)\) are investigated. First, in addition to the well-known differential distribution table two other tables, namely auto-correlation distribution table and correlation immunity distribution table associated with an S-box are introduced. The precise relationship among the three tables is established and later on used to show a number of results on various properties of S-boxes. Particularly, it is shown that the regularity of an S-box can be characterized by its difference distribution table. Then, a new tight lower bound on the differential uniformity of an S-box is given. Finally two upper bounds on the nonlinearity of S-boxes, one for a general, not necessarily regular, S-box and the other for the regular case are proved.