On the Differential and Linear Properties of Addition

Reference:

Johan Wallén. On the differential and linear properties of addition. Research Report A84, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, December 2003.

Abstract:

We present a detailed analysis of some of the fundamental differential and linear properties of addition modulo : the differential probability of addition modulo when differences are expressed using exclusive-or, the dual differential probability of exclusive-or when differences are expressed using addition modulo and the correlation of -linear approximations of addition modulo . We show that , and can be viewed as formal rational series with linear representations in base . For and , the linear representations give -time algorithms for computing and , explicit descriptions of all differentials or linear approximations with a given probability or correlation, and allows us to determine the distributions of and . For , the linear representation immediately gives a linear-time algorithm for computing . We analyse the asymptotic average behaviour of . In particular, we derive a Fourier representation of a first-order summation function obtained by interpreting differentials as integers in a natural way.

Keywords:

Differential cryptanalysis, linear cryptanalysis, arithmetic operations, rational series

Suggested BibTeX entry:

@techreport{HUT-TCS-A84,
    address = {Espoo, Finland},
    author = {Johan Wall{\'e}n},
    institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
    month = {December},
    number = {A84},
    pages = {58},
    title = {On the Differential and Linear Properties of Addition},
    type = {Research Report},
    year = {2003},
}