# Thread: How to reduce algebraic degree of Boolean Functions?

1. ## How to reduce algebraic degree of Boolean Functions?

Hi everybody,

I would much appreciate if anyone could assist me with the following problem:

Given:
consider a 4-bit input vector
$x=(a,b,c,d)$, with $a,b,c,d \in GF(2)$.

Now consider a function
$S(x) = (S_3(x),S_2(x),S_1(x),S_0(x))$, with $S:GF(2)^4 \rightarrow GF(2)^4$ and $S_3,S_2,S_1,S_0:GF(2)^4 \rightarrow GF(2)$,
i.e. the component functions $S_3,S_2,S_1,S_0$ are Boolean functions of algebraic degree $\leq 3$.

Now consider two functions $Z,Y: GF(2)^4 \rightarrow GF(2)^4$ that have the following properties:
$Y(x)=(e(x),f(x),g(x),h(x))=y$
$Z(y)=(i(y),j(y),k(y),l(y))=z$
with the component functions
$e,f,g,h,i,j,k,l:GF(2)^4 \rightarrow GF(2)$ also being Boolean functions but only with an algebraic degree $\leq 2$.
$y,z \in GF(2)^4$ denote the two 4-bit output vectors of $Y$ and $Z$.

Wanted:
I am looking for Boolean functions $e,f,g,h,i,j,k,l$ with algebraic degree $\leq 2$, such that
$S(x) = Z(y) = Z(Y(x))$ holds.

I have already looked at Matlab, but it seems that it does not supports Boolean algebra

Does anyone has any idea how to approach this problem?

Thanks!