Linear Approximations of Addition Modulo $2^n$ (2003)
AUTHORS:
Wallén Johan
BOOKTITLE:
Fast Software Encryption 2003
SERIES:
Lecture Notes in Computer Science
VOLUME:
2887
PAGES:
261--273
@inproceedings{ Wallen:linappr-addition, author = "Wall{\'e}n, Johan", publisher = "Springer-Verlag", title = "Linear Approximations of Addition Modulo $2^n$", series = "Lecture Notes in Computer Science", booktitle = "Fast Software Encryption 2003", abstract = "We present an in-depth algorithmic study of the linear approximations of addition modulo $2^n$. Our results are based on a fairly simple classification of the linear approximations of the carry function. Using this classification, we derive an $\Theta(\log n)$-time algorithm for computing the correlation of linear approximation of addition modulo $2^n$, an optimal algorithm for generating all linear approximations with a given non-zero correlation coefficient, and determine the distribution of the correlation coefficients. In the generation algorithms, one or two of the selection vectors can optionally be fixed. The algorithms are practical and easy to implement.", volume = "2887", year = "2003", keywords = "Linear approximations, correlation, modular addition, linear cryptanalysis", pages = "261--273" }