## On the Additive Differential Probability of Exclusive-Or

Helger Lipmaa, Johan Wallén and Philippe Dumas. On the Additive Differential Probability of Exclusive-Or. In Bimal Roy and Willi Meier, editors, Fast Software Encryption 2004, volume 3017 of Lecture Notes in Computer Science, pages 317--331, Delhi, India, February 5--7, 2004. Springer, Heidelberg.

File: [.ps.bz2 (184 KB), .pdf (177 KB)] ps recommended.

Abstract:

We study the differential probability $\adp^\oplus$ of exclusive-or when differences are expressed using addition modulo $2^N$. This function is important when analysing symmetric primitives that mix exclusive-or and addition---especially when addition is used to add in the round keys. (Such primitives include extsc{idea}, Mars, extsc{rc6} and Twofish.) We show that $\adp^\oplus$ can be viewed as a formal rational series with a linear representation in base $8$. This gives a linear-time algorithm for computing $\adp^\oplus$, and enables us to compute several interesting properties like the fraction of impossible differentials, and the maximal differential probability for any given output difference. Finally, we compare our results with the dual results of Lipmaa and Moriai on the differential probability of addition modulo $2^N$ when differences are expresed using exclusive-or..

Keywords: Additive differential probability, differential cryptanalysis, rational series.