1
$\begingroup$

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:

enter image description here

can someone explain what that property means or what symbol k|∆x[K] means?

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.