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

DOI:

https://doi.org/10.46586/tosc.v2021.i2.292-313

Keywords:

Differential cryptanalysis, ARX, XOR, modular addition

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.

Downloads

Published

2021-06-11

Issue

Section

Articles

How to Cite

Maximums of the Additive Differential Probability of Exclusive-Or. (2021). IACR Transactions on Symmetric Cryptology, 2021(2), 292-313. https://doi.org/10.46586/tosc.v2021.i2.292-313