CryptoDB
Efficient Algorithms for Computing Differential Properties of Addition
Authors: | |
---|---|
Download: | |
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)$. |
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 }