Maximums of the Additive Differential Probability of Exclusive-Or
At FSE 2004, Lipmaa et al. studied the additive differential probability adp⊕(α,β → γ) of exclusive-or where differences α,β,γ ∈ Fn2 are expressed using addition modulo 2n. This probability is used in the analysis of symmetric-key primitives that combine XOR and modular addition, such as the increasingly popular Addition-Rotation-XOR (ARX) constructions. The focus of this paper is on maximal differentials, which are helpful when constructing differential trails. We provide the missing proof for Theorem 3 of the FSE 2004 paper, which states that maxα,βadp⊕(α,β → γ) = adp⊕(0,γ → γ) for all γ. Furthermore, we prove that there always exist either two or eight distinct pairs α,β such that adp⊕( α,β → γ) = adp⊕(0,γ → γ), and we obtain recurrence formulas for calculating adp⊕. To gain insight into the range of possible differential probabilities, we also study other properties such as the minimum value of adp⊕(0,γ → γ), and we find all γ that satisfy this minimum value.
Copyright (c) 2021 Nicky Mouha, Nikolay Kolomeec, Danil Akhtiamov, Ivan Sutormin, Matvey Panferov, Kseniya Titova, Tatiana Bonich, Evgeniya Ishchukova, Natalia Tokareva, Bulat Zhantulikov
This work is licensed under a Creative Commons Attribution 4.0 International License.