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.
3
-
1$\begingroup$ 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. $\endgroup$– Bla BlaatDec 17, 2017 at 9:41
-
$\begingroup$ indeed, correlation should be able to be negative $\endgroup$– Richie FrameJan 17, 2018 at 4:36
-
$\begingroup$ The answer is good, see the reference. $\endgroup$– kodluFeb 17, 2018 at 0:30
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
