${\text{Let }}g:{\{ 0,1\} ^n} \to {\{ 0,1\} ^n}$ be a round function of an $n$-bit iterated block cipher and let $K \in {\{ 0,1\} ^n}$ be a fixed round-key, and denote ${g_K}(x) = g(x \oplus K).$ Show that $${\text{cor}}(u \cdot x,v \cdot {g_K}(x)) = {( - 1)^{u \cdot K}}{\text{cor}}(u \cdot x,v \cdot g(x))$$


1 Answer 1


Since $c(f,g)=\sum_x (-1)^{f(x)\oplus g(x)}$, we can write $$c(u\cdot x, v \cdot g(x\oplus K))=\sum_x (-1)^{u\cdot x \oplus g(x\oplus K)}$$ where the sum ranges over all binary strings of length $n$ which is a vector space over the binary field. Now let $y=x\oplus K$ and note that as $x$ ranges over this vector space so does $y$. Therefore we can rewrite the same correlation as $$c(u\cdot x, v \cdot g(x\oplus K))=\sum_y (-1)^{u\cdot (K \oplus y) \oplus g(y)}=(-1)^{u\cdot K}\sum_y (-1)^{u\cdot y \oplus g(y)}.$$ The last sum is just $c(u\cdot x, v \cdot g(x))$ thus giving the claimed result.

This is also related to a shift property of the Walsh Hadamard transform which is after all a Fourier transform.

  • $\begingroup$ Here $g(x)=S(x)$ and $g_K(x)=S(x \oplus K).$ Also the correlation $c(u \cdot x,v \cdot g(x \oplus K))$ is a sum of plus ones and minus ones and not 0 or 1 if you look at my equation. Finally, what you need to observe is the following. If all the key bits (either for the Sbox or the round or the full cipher) are set to zero and the correlation is computed and its value is obtained say $c_{unkeyed}$ and then a nonzero key value $K$ is chosen, and a new correlation value is obtained, say $c_{keyed}$ we have the relationship $c_{keyed}=(-1)^{u\cdot K}c_{unkeyed}$ where $u $ is the mask used. $\endgroup$
    – kodlu
    Feb 10, 2016 at 12:37

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.