The Number of Impossible Additive Differentials for the Composition of XOR and Bit Rotation Full article
| Journal |
Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797 |
||
|---|---|---|---|
| Output data | Year: 2024, Volume: 18, Number: 4, Pages: 722-743 Pages count : 22 DOI: 10.1134/s1990478924040094 | ||
| Tags | ARX, differential probability, XOR, modular addition, bit rotation, impossible differential | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics, Siberian Branch of Russian Academy of Sciences, Novosibirsk, 630090, Russia | FWNF-2022-0019 |
Abstract:
Additive differentials of the function (x⊕y) ≪ r whose probability is 0 are considered, where x, y ∈ Z n 2 and 1 ≤ r < n. They are called impossible differentials and are interesting in the context of differential cryptanalysis of ciphers whose schemes consist of additions modulo 2 n, bitwise XORs (⊕), and bit rotations (≪ r). The number of all such differentials is calculated for all possible r and n. It is also shown that this number is greater than 38 245 8 n. Moreover, the estimate is asymptotically tight for r, n − r → ∞. For any fixed n the number of all impossible differentials decreases as r goes from 1 to ⌈n/2⌉ (to ⌈n/2⌉ + 1 in the case of n ∈ {4, 5, 6, 8, 10, 12}) and then increases monotonically as r goes to n − 1. A simplified description of all impossible differentials is obtained up to known symmetries.
Cite:
Kolomeec N.A.
The Number of Impossible Additive Differentials for the Composition of XOR and Bit Rotation
Journal of Applied and Industrial Mathematics. 2024. V.18. N4. P.722-743. DOI: 10.1134/s1990478924040094 Scopus РИНЦ OpenAlex
The Number of Impossible Additive Differentials for the Composition of XOR and Bit Rotation
Journal of Applied and Industrial Mathematics. 2024. V.18. N4. P.722-743. DOI: 10.1134/s1990478924040094 Scopus РИНЦ OpenAlex
Original:
Коломеец Н.А.
Число невозможных разностей по модулю 2^n композиции XOR и циклического сдвига битов
Дискретный анализ и исследование операций. 2024. Т.31. №4. С.58-89. DOI: 10.33048/daio.2024.31.800 РИНЦ OpenAlex
Число невозможных разностей по модулю 2^n композиции XOR и циклического сдвига битов
Дискретный анализ и исследование операций. 2024. Т.31. №4. С.58-89. DOI: 10.33048/daio.2024.31.800 РИНЦ OpenAlex
Dates:
| Submitted: | Apr 9, 2024 |
| Accepted: | Jun 22, 2024 |
| Published print: | Dec 25, 2024 |
| Published online: | Jul 11, 2025 |
Identifiers:
| ≡ Scopus: | 2-s2.0-105012422943 |
| ≡ Elibrary: | 82621658 |
| ≡ OpenAlex: | W4412194729 |