Calculation of the differential probabilities for the sum of $k$ numbers modulo $2^n$

A. S. Mokrousov

Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 54-57

Résumé

We study the differential probabilities $\mathrm{xdp}_{\mathrm{k}}^+(\alpha^1, \dots, \alpha^k \to \alpha^0)$ of the function $f(x_1,\dots, x_k) = x_1 + \dots + x_k \mod 2^n$, $\alpha^0, \alpha^1, \dots, \alpha^k \in \mathbb{Z}_2^n$, where differences are expressed using bitwise “exclusive or”. These values are used in differential cryptanalysis of cryptographic primitives which contain bitwise “exclusive or” and addition modulo $2^n$, such as ARX-constructions. We propose analytic expressions of matrices that are used for calculating $\mathrm{xdp}_{\mathrm{k}}^+$. We also study the differential probability $\mathrm{adp}^{\oplus}(\alpha, \beta \to \gamma)$ of the function $x \oplus y$, $\alpha, \beta, \gamma \in \mathbb{Z}_2^n$, where differences are expressed using addition modulo $2^n$, and describe all triples of differences whose probabilities are greater than ${1}/{4}$.

Détail

Mots-clés : ARX
Keywords: exclusive or, modular addition, differential cryptanalysis, differential probabilities.