3
$\begingroup$

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.

$\endgroup$
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 Blaat Dec 17 '17 at 9:41
  • $\begingroup$ indeed, correlation should be able to be negative $\endgroup$ – Richie Frame Jan 17 '18 at 4:36
  • $\begingroup$ The answer is good, see the reference. $\endgroup$ – kodlu Feb 17 '18 at 0:30
1
$\begingroup$

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.

scanpages

$\endgroup$

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.