Determine if $f(x)+x_0+x_n$ is balanced If $f(x)=x_0x_1\oplus x_1x_2\oplus\cdots\oplus x_{n-2}x_{n-1}\oplus x_{n-1}x_n\oplus L(x)$ is a balanced boolean function (which is a boolean function whose output yields as many 0s as 1s over its input). Determine if $f(x)\oplus x_0\oplus x_n$ is balanced.    Notice that $L(x)=k_0x_0\oplus k_1x_1\oplus k_2x_2+\cdots\oplus k_nx_n$, where $  k_i \in \{0,1\}$.  


Newly to this field. Any hints would be helpful.
If you want to learn about your new field, I strongly recommend you to read only section 3 of Correlation of Quadratic Boolean Functions: Cryptanalysis of All Versions of Full MORUS, maybe skipping the proofs but definitely not the examples during the first reading.

Try then to solve your problem for at least an hour, before reading my solution below. (Hint: Apply Algorithm 1 (no need to program it) to your function $f$, and then Lemma 4 to the result of Alg. 1.)



As a self-contained answer would be much too long, I assume that the reader understood section 3 of the paper mentioned above.

Following Algorithm 1, define $x'_0 := x_0+x_2$ then $x'_2 := x_2 + x_4$, and so on, and additionally (don't look at the $k'$ before you understood about the $x'$) $k'_0 := k_0, k'_{2i+1} = k_{2i+1}, k'_{2i+2} := k_{2i+2}+k_{2i}$ to clean up the linear term L  to get

$$f(x'_0, x_1, x'_2, x_2, \dots) = x'_0x_1 + x'_2x_3 + \dots + x'_{m-1}x_m + k'_0x_0 + k'_1x_1 + \dots + k'_nx_n,$$

in disjoint quadratic form, where $m=n$ if $n$ odd and $m=n-1$ if $n$ even.

Lemma 4 tells you now that kodlu is right in claiming that $f$ cannot be balanced if $n$ is odd, as all variables $x'_0, x_1, x'_2, \dots$ show up in some quadratic term (that are separated after the substitution).

Lemma 4 tells you also that for $n$ even, $k'_n = k_n+k_{n-2}$ being $1$ is equivalent to $f$ being balanced, as $x_n$ is the only variable not showing up in any quadratic term (that all are separated over the variables $x'_0, x_1, x'_2, \dots$).

For $n$ even adding $x_n$ to $f$ corresponds to replacing $k_n$ by $k_n+1$ making $k'_n=0$ and $f$ not balanced.

Adding then $x_0$ to $f$ corresponds to replacing $k'_i$ by $k'_i+1$ for all even indices $i$, in particular also for $i=n$ even, making $k'_n=1$ and $f$ balanced again.