## CryptoDB

### Paper: Efficient Algorithms for Computing Differential Properties of Addition

Authors: Helger Lipmaa Shiho Moriai URL: http://eprint.iacr.org/2001/001 Search ePrint Search Google 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)$.
##### BibTeX
@misc{eprint-2001-11414,
title={Efficient Algorithms for Computing Differential Properties of Addition},
booktitle={IACR Eprint archive},
keywords={secret-key cryptography / modular addition, differential cryptanalysis, differential probability, impossible differentials, maximum differential probability},
url={http://eprint.iacr.org/2001/001},
note={Fast Software Encryption ?FSE? 2001? helger@tml.hut.fi 11458 received 4 Jan 2001, last revised 16 May 2001},
author={Helger Lipmaa and Shiho Moriai},
year=2001
}