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: 20010516:191331 (All versions of this report)
Short URL: ia.cr/2001/001
[ Cryptology ePrint archive ]