Efficient Algorithms for Computing Differential Properties of Addition

Helger Lipmaa; Shiho Moriai

Paper 2001/001

Efficient Algorithms for Computing Differential Properties of Addition

Helger Lipmaa and 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)$.

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©

Metadata

Available format(s): PDF PS
Category: Secret-key cryptography
Keywords: modular addition differential cryptanalysis differential probability impossible differentials maximum differential probability
Contact author(s): helger @ tml hut fi
History: 2001-05-16: last of 3 revisions; 2001-01-05: received; See all versions
Short URL: https://ia.cr/2001/001
License: CC BY

BibTeX

@misc{cryptoeprint:2001/001,
      author = {Helger Lipmaa and Shiho Moriai},
      title = {Efficient Algorithms for Computing Differential Properties of Addition},
      howpublished = {Cryptology {ePrint} Archive, Paper 2001/001},
      year = {2001},
      url = {https://eprint.iacr.org/2001/001}
}