The Number of Impossible Additive Differentialsfor the Composition of XOR and Bit Rotation

Additive differentials of the function $$ (x \oplus y) \lll r $$ whose probability is $$ 0 $$ are considered, where $$ x, y \in \mathbb {Z}_2^{n} $$ and $$ 1 \leq 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 ( $$ \oplus $$ ), and bit rotations ( $$ \lll 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 $$ \frac {38}{245} 8^n $$ . Moreover, the estimate is asymptotically tight for $$ r, n-r \to \infty $$ . For any fixed $$ n $$ the number of all impossible differentials decreases as $$ r $$ goes from $$ 1 $$ to $$ \lceil n/2 \rceil $$ (to $$ \lceil n/2 \rceil + 1 $$ in the case of $$ n \in \{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.