${\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))$$


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.

| improve this answer | |
  • $\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 '16 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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