Lower defree annihilator of function

Suppose $f=x_0x_2(x_1+1)+x_1x_3(x_0+1)$, annihilator is such function $g$, so that $gf=0$ for all $x$

Intuitively solution(for some reason) is obvious - $g=x_0x_1$, which holds true. (Cloud sagemath online script)

It bugs me, that I can't explain this "intuitively". How to arrive at solution properly, not guessing?

PS: We can skip trivial solution $g=0$, function $g$ should depend on $x_n$ variables, at least some of them. Of course $\mathbb{F}_2$ is meant here.

• What does this question have to do with cryptography? Sep 10, 2015 at 18:50
• Attack on streaming ciphers Sep 10, 2015 at 19:03
• Please edit the question body, making the link clear, and the kind of attack you are referring to. If you want others to consider your question seriously you must make the effort. Sep 10, 2015 at 23:56
• It is from lecture notes, dont believe I can, neither actually allowed to link anything. I dont think it is big dismeanor to link page of lecture notes though clip2net.com/s/3nkBMMu second page clip2net.com/s/3nkBQw2 I am making effort, as much as I possibly can. Sep 11, 2015 at 3:35

I'm not sure if I really believe that this is of any use at attacking a stream cipher, but I'll answer your question anyways.

What $gf = 0$ means is that, for any input $x$, we have either $f=0$ or $g=0$.

Now, in the case of $g = x_0x_1$, then this $g$ will be 0 unless $x_0 = x_1 = 1$.

In that case, the first term of $f$, namely $x_0x_2(x_1+1)$ will be 0 (as $x_1+1 = 1+1 = 0$). And, the second term of $f$, namely $x_1x_3(x_0+1)$ will be 0 (as $x_0+1 = 1+1 = 0$).

Hence, whenever $g \ne 0$, we have $f=0$, and so $gf = 0$.

This observation gives a fairly obvious way to create a nontrivial annihilator of any function $f$ (other than $f=1$ for all inputs); namely:

• Find a set of inputs that give $f=0$ (technically, this is an NP-hard problem (!), but in practice is fairly easy).

• Create a $g$ that is 1 for that specific input, and 0 otherwise.

For example, if $f=0$ for $x_0 = 0, x_1 = 1, x_2 = 0$, then this annihilator would be $g = (x_0 + 1)x_1(x_2 + 1)$