On additive differential probabilities of a composition of bitwise XORs

I. A. Sutormin ; N. A. Kolomeets

Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 59-75

Résumé

We study the additive differential probabilities $\mathrm{adp}_k^{\oplus}$ of compositions of $k - 1$ bitwise XORs. For vectors $\alpha^1, \ldots, \alpha^{k+1} \in \mathbb{Z}_2^n$, it is defined as the probability of transformation input differences $\alpha^1, \ldots, \alpha^k$ to the output difference $\alpha^{k+1}$ by the function $x^1 \oplus \ldots \oplus x^k$, where $x^1, \ldots, x^k \in \mathbb{Z}_2^n$ and $k \geq 2$. It is used for differential cryptanalysis of symmetric-key primitives, such as Addition-Rotation-XOR constructions. Several results which are known for $\\mathrm{adp}_2^{\oplus}$ are generalized for $\mathrm{adp}_k^{\oplus}$. Some argument symmetries are proven for $\mathrm{adp}_k^{\oplus}$. Recurrence formulas which allow us to reduce the dimension of the arguments are obtained. All impossible differentials as well as all differentials of $\mathrm{adp}_k^{\oplus}$ with the probability $1$ are found. For even $k$, it is proven that $\max\limits_{\alpha^1, \ldots, \alpha^{k} \in \mathbb{Z}_2^n} \mathrm{adp}_k^{\oplus}(\alpha^1,\dots,\alpha^{k}\to\alpha^{k+1}) = \mathrm{adp}_k^{\oplus}(\alpha^1,\dots,0,\alpha^{k+1}\to\alpha^{k+1})$. Matrices that can be used for efficient calculating $\mathrm{adp}_k^{\oplus}$ are constructed. It is also shown that the cases of even and odd $k$ differ significantly.

Détail

Keywords: additive differential probabilities, differential cryptanalysis.
Mots-clés : ARX, XOR