Abstract
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 ofdifferential 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 toknown symmetries.
