Asymptotic Distributions for S-Box Heterogeneous Differential Probabilities

We study asymptotic behavior of heterogeneous differentials, i.e. pairs of S-box input and output differences when «differences» are calculated with respect to non-equal Abelian operations. We prove that probabilities of any fixed (+,⊕)-differential asymptotically follow Poisson distribution with parameter 1 or 1/2 dependent on the order of input difference in corresponding group, when S-box is taken randomly and uniformly from a set of all possible n-bit bijective mappings. These results generalize and complete the Hawkes and O‘Connor research about asymptotic distribution of homogeneous differentials. Besides, we examine the convergence of exact differential probabilities to their asymptotic estimations. Experimental evaluations show that discrepancy is low even for small size n of S-box