International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Efficient Algorithms for Computing Differential Properties of Addition

Authors:
Helger Lipmaa
Shiho Moriai
Download:
URL: http://eprint.iacr.org/2001/001
Search ePrint
Search Google
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
}