Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I'm studying Impossible Differential Cryptanalysis of SPECK paper and I'm having trouble understanding the differential diffusion property of addition in page 19 which is as follows:
can someone explain what that property means or what symbol k|∆x[K] means?
The expression $\{k|\Delta x[k]=1\}$ should be read as "the set of $k$ such that the $k$th bit of $\Delta x$ is set". It follows then that $\ell_1$ is the rightmost bit position where the two $x$ values differ and $\ell_2$ is the rightmost position where the two $y$ value differ. It also follows that the two $x$ values and two $y$ values agree in all $\ell-1$ positions to the right of the $\ell$th position.
Elementary addition tells us that the $\ell-1$ rightmost bits of $z$ depend only on the $\ell$ rightmost bits of $x$ and the $\ell$ rightmost bits of $y$, so that for two additions where these bits are identical, the $\ell-1$ rightmost bits of the answers are identical. Hence $\Delta z[k]=0$ for $k<\ell$.
In the case where $\ell_1=\ell_2$, the computation of the $\ell$th bit is given by $$z[\ell]=x[\ell]\oplus y[\ell]\oplus c[\ell-1]$$ where $c[\ell-1]$ is the carry bit. This carry bit is the same in both cases but we replace the other terms with $x[\ell]\oplus 1$ and $y[\ell]\oplus 1$ so that $z[\ell]$ is unchanged (i.e. $\Delta z[\ell]=0)$. In the case $\ell=\ell_1\neq\ell_2$ the carry bit is still the same and we only make the replacement $x[\ell]\oplus 1$ so that $z[\ell]$ flips (i.e. $\Delta z[\ell]=1$). Similarly in the case $\ell=\ell_2\neq\ell_1$ we make the replacement $y[\ell]\oplus 1$ so that again $\Delta z[\ell]=1$.
