Paper 2018/1103

Some Properties of Modular Addition

Victoria Vysotskaya

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
Published elsewhere. Minor revision. 7th Workshop on Current Trends in Cryptology (CTCrypt 2018) - Suzdal, Russia, 2018 - Pre-proceedings
Keywords
modular additionpartitionsdifferential cryptanalysis
Contact author(s)
vysotskaya victory @ gmail com
History
2018-11-18: revised
2018-11-16: received
See all versions
Short URL
https://ia.cr/2018/1103
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1103,
      author = {Victoria Vysotskaya},
      title = {Some Properties of Modular Addition},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1103},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1103}},
      url = {https://eprint.iacr.org/2018/1103}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.