|
Mathematical Methods of Cryptography
The additive differential probability of $k$ successive exclusive-OR
I. A. Sutorminab a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University
Abstract:
We study the additive differential probability of a composition of bitwise XOR — $\mathrm{adp}^{\oplus}_k$. For a set of vectors $\alpha^1 \ldots \alpha^{k + 1} \in \mathbb{Z}_2^{n}$, it is defined as $$ \textstyle\mathrm{adp}^{\oplus}_k(\alpha^{1}, \ldots, \alpha^{k} \to \alpha^{k + 1}) = \dfrac{1}{2^{kn}} \big|\lbrace x^1, \ldots, x^{k}\in \mathbb{Z}_{2}^{n} : {\bigoplus\limits_{i = 1}^{k}(x^i \boxplus \alpha^i)} = \alpha^{k + 1} \boxplus \bigoplus\limits_{i = 1}^{k} x^i \rbrace\big|.$$ It is used when analyzing symmetric key primitives, such as Addition-Rotation-XOR constructions. It is proven that: 1) $\mathrm{adp}^{\oplus}_k$ is a symmetric function; 2) the value of $\mathrm{adp}^{\oplus}_k$ does not change if $2^{n - 1}$ is added to any two arguments; 3) the value of $\mathrm{adp}^{\oplus}_k$ does not change if any two arguments are replaced by the opposite element of $\mathbb{Z}_{2}^{n}$, and if $k$ is even, then the value of $\mathrm{adp}^{ \oplus}_k$ does not change if any argument is replaced. Recurrence formulas are obtained allowing to calculate the value $\mathrm{adp}^{\oplus}_k$ for arguments of dimension $n + 1$ using the set of values $\mathrm{adp}^{\oplus}_k$ for arguments of dimension $n$. Using recurrent formulas we prove that $\mathrm{adp}^{\oplus}_k$ is equal to zero if and only if there exists a position $i$ such that $(\alpha^1_i, \ldots, \alpha^{ k + 1}_i) \neq (0, \ldots, 0)$; $(\alpha^1_j, \ldots, \alpha^{k + 1}_j ) = (0, \ldots, 0)$ for any $j$, $n \geq j > i$, and either Hamming weight of the vector $(\alpha^1_i, \ldots, \alpha^{k + 1}_i)$ is odd, or $k$ is odd, $i > 1$, vector $(\alpha^1_i, \ldots, \alpha^{k + 1}_i)$ is equal to the $(1, \ldots, 1)$ and Hamming weight of the vector $(\alpha^1_{i - 1}, \ldots, \alpha^{k + 1}_{i - 1})$ is odd. In the case of even $k$, it is proved that $\mathrm{adp}^{\oplus}_k(0, \ldots, 0, \gamma \to \gamma)$ is maximal when the last argument is fixed. In the case of odd $k$, it is conjectured that $\mathrm{adp}^{\oplus}_k(\gamma, \ldots, \gamma \to \gamma)$ is maximum when the last argument is fixed.
Keywords:
differential cryptanalysis, ARX, XOR, modular addition.
Citation:
I. A. Sutormin, “The additive differential probability of $k$ successive exclusive-OR”, Prikl. Diskr. Mat. Suppl., 2022, no. 15, 67–70
Linking options:
https://www.mathnet.ru/eng/pdma582 https://www.mathnet.ru/eng/pdma/y2022/i15/p67
|
Statistics & downloads: |
Abstract page: | 80 | Full-text PDF : | 22 | References: | 19 |
|