Paper 2018/1103 Original: eprint.iacr.org/2018/1103 ↗
Some Properties of Modular Addition
Abstract
In this paper we study a problem which emerged during an attempt to apply a differential cryptanalysis method to the <<Magma>> algorithm. We obtained a general formula of distribution in the difference distribution table of addition modulo $2^n$ and provided an efficient method for computing the distribution in a row with given index. Moreover, an exact formula that may be used to solve the task of counting all the distributions was obtained, and an asymptotically accurate approximation of number of distinct distributions was proved. Finally, we designed an algorithm to generate all distributions in $2^{O(\sqrt{(n)})}$ operations (whereas the corresponding brute-force method takes $2^{\Omega(n)}$).
Metadata
- Available format(s)
PDF- Category
- Secret-key cryptography
- Publication info
- Preprint.
- History
- 2018-11-18: last updated
- 2018-11-16: published
- Short URL
- https://ia.cr/2018/1103
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2018/1103,
author = {Victoria Vysotskaya},
title = {Some Properties of Modular Addition},
howpublished = {Cryptology {ePrint} Archive, Paper 2018/1103},
year = {2018},
url = {https://eprint.iacr.org/2018/1103}
}