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
Publication info
Published elsewhere. Fast Software Encryption ¥FSE¤ 2001©
Keywords
modular additiondifferential cryptanalysisdifferential probabilityimpossible differentialsmaximum 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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.