Paper 2001/001 Original: eprint.iacr.org/2001/001 ↗
Efficient Algorithms for Computing Differential Properties of Addition
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)$.
Metadata
- Available format(s)
PDF- Category
- Secret-key cryptography
- Publication info
- Preprint.
- History
- 2001-05-16: last updated
- 2001-01-05: published
- Short URL
- https://ia.cr/2001/001
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}