TCS / Research / Publications / Linear Approximations of Addition Modulo $2^n$
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Linear Approximations of Addition Modulo


Johan Wallén. Linear approximations of addition modulo . In Fast Software Encryption 2003, volume 2887 of Lecture Notes in Computer Science, pages 261–273. Springer-Verlag, 2003.


We present an in-depth algorithmic study of the linear approximations of addition modulo . Our results are based on a fairly simple classification of the linear approximations of the carry function. Using this classification, we derive an -time algorithm for computing the correlation of linear approximation of addition modulo , 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.


Linear approximations, correlation, modular addition, linear cryptanalysis

Suggested BibTeX entry:

    author = {Johan Wall{\'e}n},
    booktitle = {Fast Software Encryption 2003},
    pages = {261--273},
    publisher = {Springer-Verlag},
    series = {Lecture Notes in Computer Science},
    title = {Linear Approximations of Addition Modulo $2^n$},
    volume = {2887},
    year = {2003},

This work is not available online here.

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.