On additive differential probabilities of a composition of bitwise XORs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2023. № 60. DOI: 10.17223/20710410/60/5

We study the additive differential probabilities adp⊗k of compositions of k - 1 bitwise XORs. For vectors α1,...,αk+1 ℤ2n, it is defined as the probability of transformation input differences al,...,ak to the output difference ak+1 by the function x1 ⊗ ... ⊗ xk, where x1,... ,xk ℤ2n and k ≥ 2. It is used for differential cryptanalysis of symmetric-key primitives, such as Addition-Rotation-XOR constructions. Several results which are known for adp⊗2 are generalized for adp⊗k . Some argument symmetries are proven for adp⊗k . Recurrence formulas which allow us to reduce the dimension of the arguments are obtained. All impossible differentials as well as all differentials of adp⊗k with the probability 1 are found. For even k, it is proven that max max adp⊗k (α1,..., αk → αk+1) = adp⊗k (0,..., 0, αk+1 → αk+1). Matrices that can α1,...,αk be used for efficient calculating adp⊗k are constructed. It is also shown that the cases of even and odd k differ significantly.