On the Differential and Linear Properties of Addition (2003)
AUTHORS:
Wallén Johan
URL:
http://www.tcs.hut.fi/Publications/info/bibdb.HUT-TCS-A84.shtml
@techreport{ Wal03:HUT-TCS-A84, author = "Wall{\'e}n, Johan", title = "On the Differential and Linear Properties of Addition", url = "http://www.tcs.hut.fi/Publications/info/bibdb.HUT-TCS-A84.shtml", pages = "57", year = "2003", number = "A84", abstract = "We present a detailed analysis of some of the fundamental differential and linear properties of addition modulo $2^n$: the differential probability $\operatorname{xdp}^+$ of addition modulo $2^n$ when differences are expressed using exclusive-or, the dual differential probability $\operatorname{adp}^\oplus$ of exclusive-or when differences are expressed using addition modulo $2^n$ and the correlation $\operatorname{lca}$ of $\mathbf{F}_2$-linear approximations of addition modulo $2^n$. We show that $\operatorname{xdp}^+$, $\operatorname{adp}^\oplus$ and $\operatorname{lca}$ can be viewed as formal rational series with linear representations in base $8$. For $\operatorname{xdp}^+$ and $\operatorname{lca}$, the linear representations give $\Theta(\log n)$-time algorithms for computing $\operatorname{xdp}^+$ and $\operatorname{lca}$, explicit descriptions of all differentials or linear approximations with a given probability or correlation, and allows us to determine the distributions of $\operatorname{xdp}^+$ and $\operatorname{lca}$. For $\operatorname{adp}^\oplus$, the linear representation immediately gives a linear-time algorithm for computing $\operatorname{adp}^\oplus$. We analyse the asymptotic average behaviour of $\operatorname{adp}^\oplus$. In particular, we derive a Fourier representation of a first-order summation function obtained by interpreting differentials as integers in a natural way.", month = "December", flags = "copy, public", address = "Espoo, Finland", keywords = "Differential cryptanalysis, linear cryptanalysis, arithmetic operations, rational series", type = "Research Report", institution = "Helsinki University of Technology, Laboratory for Theoretical Computer Science" }