# The sign of the correlation in linear approximation

${\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.
• 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. – kodlu Feb 10 '16 at 12:37