Cryptology ePrint Archive: Report 2001/001

Efficient Algorithms for Computing Differential Properties of Addition

Helger Lipmaa, Shiho Moriai

Abstract: In this paper we systematically study the differential properties of addition modulo $2^n$. We derive $\Theta(\log n)$-time algorithms for most of the properties, including differential probability of addition. We also present log-time algorithms for finding good differentials. Despite the apparent simplicity of modular addition, the best known algorithms require naive exhaustive computation. Our results represent a significant improvement over them. In the most extreme case, we present a complexity reduction from $\Omega(2^{4n})$ to $\Theta(\log n)$.

Category / Keywords: secret-key cryptography / modular addition, differential cryptanalysis, differential probability, impossible differentials, maximum differential probability

Publication Info: Fast Software Encryption ¥FSE¤ 2001©

Date: received 4 Jan 2001, last revised 16 May 2001

Contact author: helger at tml hut fi

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: The previous version of 2001/001 corresponded to the preproceedings version© This version is the final proceedings version© See http://www©tml©hut©fi/~helger/papers/lm01/ for more information©

Version: 20010831:070056 (All versions of this report)

Short URL: ia.cr/2001/001

Discussion forum: Show discussion | Start new discussion