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
-
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}
}
