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},
}
|