On additive differential probabilities of a composition of bitwise XORs

Исследуются разностные характеристики $\mathrm{adp}_k^{\oplus}$ по модулю $2^n$ композиции $k-1$ побитовых XOR. Для векторов $\alpha^1, \ldots, \alpha^{k+1} \in \mathbb{Z}_2^n$ они определяются как вероятность преобразования функцией $x^1 \oplus \ldots \oplus x^k$ входных разностей $\alpha^1, \ldots, \alpha^k $ в выходную разность $\alpha^{k+1}$, где $x^1, \ldots, x^k \in \mathbb{Z}_2^n$ и $k \geq 2$. Данные характеристики используются при разностном криптоанализе симметричных алгоритмов, в том числе ARX-конструкций, использующих только три операции: сложение по модулю $2^n$, побитовый XOR и циклический сдвиг битов. Показано, что многие свойства, известные для $\mathrm{adp}_2^{\oplus}$, обобщаются на $\mathrm{adp}_k^{\oplus}$. Доказаны симметрии аргументов $\mathrm{adp}_k^{\oplus}$. Получены рекуррентные формулы, позволяющие уменьшить на $1$ размерность аргументов $n$. Найдены все несовместные разности и все разности, при которых $\mathrm{adp}_k^{\oplus}$ равна $1$. Для чётного $k$ доказано, что $\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})$. Построены матрицы, которые можно использовать для вычисления $\mathrm{adp}_k^{\oplus}$ за линейное по $n$ время. Показано, что случаи чётного и нечётного $k$ существенно различаются.