# Cross correlation of two Boolean functions

I have been studying Cryptographic Boolean Functions and got stuck with the calculation of cross correlation of two boolean functions. I know the formula is $$c_{f,g}(y) = \sum_{x \in V_{n}} f(x)\cdot g(x\oplus y).$$ What I don't understand is if $f = g$ and $y$ is $0$ shouldn't the correlation be $2^n$? When I calculate, if $f$ and $h$ has the value $0$, $f(x)\cdot g(x)$ will yield $0$, but shouldn't I have $1$ in order to reach $2^n$ in the end? I am sorry if this question sounds silly but I have really spent so much time trying to figure out. Any help would be greatly appreciated.

• Where did you find this formula? I think $\sum_{x\in V_n} (-1)^{f(x) \oplus g(x \oplus y)}$ is more common and then it nicely adds up to $2^n$ and you can actually have negative correlation. – Bla Blaat Dec 17 '17 at 9:41
• indeed, correlation should be able to be negative – Richie Frame Jan 17 '18 at 4:36
• The answer is good, see the reference. – kodlu Feb 17 '18 at 0:30

## 1 Answer

In theoretical computer science literature, boolean functions are defined as $$f\colon \operatorname{GF}(2)^n \to \{\pm 1\},$$ and the usual link with functions defined as $$\tilde{f}\colon \operatorname{GF}(2)^n \to \{0,1\}$$ is via $$f(x)=(-1)^{\tilde{f}(x)}.$$

Edit Here's a standard reference from the Boolean function literature. 