Geodesic
On additive differential probabilities of a composition of bitwise XORs
Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 59-75.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: additive differential probabilities, differential cryptanalysis.
Mots-clés : ARX, XOR 
@article{PDM_2023_2_a4,
     author = {I. A. Sutormin and N. A. Kolomeets},
     title = {On additive differential probabilities of a composition of bitwise {XORs}},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {59--75},
     publisher = {mathdoc},
     number = {2},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDM_2023_2_a4/}
}
TY  - JOUR
AU  - I. A. Sutormin
AU  - N. A. Kolomeets
TI  - On additive differential probabilities of a composition of bitwise XORs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2023
SP  - 59
EP  - 75
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2023_2_a4/
LA  - en
ID  - PDM_2023_2_a4
ER  - 
%0 Journal Article
%A I. A. Sutormin
%A N. A. Kolomeets
%T On additive differential probabilities of a composition of bitwise XORs
%J Prikladnaâ diskretnaâ matematika
%D 2023
%P 59-75
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2023_2_a4/
%G en
%F PDM_2023_2_a4
I. A. Sutormin; N. A. Kolomeets. On additive differential probabilities of a composition of bitwise XORs. Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 59-75. http://geodesic.mathdoc.fr/item/PDM_2023_2_a4/

[1] Shimizu A. and Miyaguchi S., “Fast Data Encipherment Algorithm (FEAL)”, LNCS, 304, 1988, 267–278 | Zbl

[2] Ferguson N., Lucks S., Schneier B., et al., The Skein Hash Function Family, 2009 http://www.skein-hash.info

[3] Bernstein D. J., Salsa20 specification, 2005 https://cr.yp.to/snuffle/spec.pdf

[4] Bernstein D. J., ChaCha, a variant of Salsa20, 2008 https://cr.yp.to/chacha/chacha-20080128.pdf

[5] Aumasson J.-P., Meier W., Phan R. C.-W., and Henzen L., The Hash Function BLAKE, Springer, Berlin–Heidelberg, 2014 | MR | Zbl

[6] Biham E. and Shamir A., “Differential cryptanalysis of DES-like cryptosystems”, J. Cryptology, 4:1 (1991), 3–72 | DOI | MR | Zbl

[7] Malyshev F. M., “Probabilistic characteristics of differential and linear relations for nonhomogeneous linear medium”, Matematicheskie Voprosy Kriptografii, 10:1 (2019), 41–72 (in Russian) | DOI | MR | Zbl

[8] Malyshev F. M., “Differential characteristics of base operations in ARX-ciphers”, Matematicheskie Voprosy Kriptografii, 11:4 (2020), 97–105 (in Russian) | DOI | MR | Zbl

[9] Leurent G., “Analysis of differential attacks in ARX constructions”, LNCS, 7658, 2012, 226–243 | Zbl

[10] Leurent G., “Construction of differential characteristics in ARX designs application to Skein”, LNCS, 8042, 2013, 241–258 | Zbl

[11] Mouha N., Kolomeec N., Tokareva N., et al., “Maximums of the additive differential probability of exclusive-or with one fixed argument”, IACR Trans. Symmetric Cryptology, 2021:2 (2021), 292–313 | DOI | MR

[12] Velichkov V., Mouha N., De Canniére C., and Preneel B., “The additive differential probability of ARX”, LNCS, 6733, 2011, 342–358 | Zbl

[13] Gligoroski D., Ødegărd R. S., Mihova M., et al., “Cryptographic hash function Edon-R'.”, Proc. 1st Intern. Workshop on Security and Communication Networks (Trondheim, Norway, 2009), 1–9

[14] Lipmaa H., Wallén J., and Dumas P., “On the additive differential probability of Exclusive-Or”, LNCS, 3017, 2004, 317–331 | Zbl

[15] Mouha N., Velichkov V., De Canniére C., and Preneel B., “The differential analysis of S-functions”, LNCS, 6544, 2011, 36–56 | MR | Zbl

[16] Gorodilova A., Tokareva N., Agievich S., et al., “An overview of the eight international olympiad in cryptography “Non-Stop University Crypto””, Siberian Electronic Math. Reports, 19:1 (2022), A9–A37 | MR

[17] Agievich S. V., Gorodilova A. A., Tokareva N. N., et al., “Problems, solutions and experience of the first international student's Olympiad in cryptography”, Prikladnaya Diskretnaya Matematika, 2015, no. 3, 41–62 | DOI