Cryptology ePrint Archive: Report 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)}$).

Category / Keywords: secret-key cryptography / modular addition, partitions, differential cryptanalysis

Original Publication (with minor differences): 7th Workshop on Current Trends in Cryptology (CTCrypt 2018) - Suzdal, Russia, 2018 - Pre-proceedings

Date: received 14 Nov 2018, last revised 18 Nov 2018

Contact author: vysotskaya victory at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20181118:173932 (All versions of this report)

Short URL: ia.cr/2018/1103


[ Cryptology ePrint archive ]