International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Maximums of the Additive Differential Probability of Exclusive-Or

Authors:
Nicky Mouha , Strativia, Largo, MD, USA
Nikolay Kolomeec , Sobolev Institute of Mathematics, Novosibirsk, Russia
Danil Akhtiamov , The Hebrew University of Jerusalem, Jerusalem, Israel
Ivan Sutormin , Sobolev Institute of Mathematics, Novosibirsk, Russia
Matvey Panferov , Novosibirsk State University, Novosibirsk, Russia
Kseniya Titova , Novosibirsk State University, Novosibirsk, Russia
Tatiana Bonich , Novosibirsk State University, Novosibirsk, Russia
Evgeniya Ishchukova , Southern Federal University, Taganrog, Russia
Natalia Tokareva , Sobolev Institute of Mathematics, Novosibirsk, Russia
Bulat Zhantulikov , Novosibirsk State University, Novosibirsk, Russia
Download:
DOI: 10.46586/tosc.v2021.i2.292-313
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8912
Search ePrint
Search Google
Abstract: 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.
Video from TOSC 2021
BibTeX
@article{tosc-2021-31087,
  title={Maximums of the Additive Differential Probability of Exclusive-Or},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2021, Issue 2},
  pages={292-313},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8912},
  doi={10.46586/tosc.v2021.i2.292-313},
  author={Nicky Mouha and Nikolay Kolomeec and Danil Akhtiamov and Ivan Sutormin and Matvey Panferov and Kseniya Titova and Tatiana Bonich and Evgeniya Ishchukova and Natalia Tokareva and Bulat Zhantulikov},
  year=2021
}