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.
UDC:
519.7
DOI:
10.17223/2226308X/15/17
Fulltext:
PDF file (583 kB)