[[xzz-2019-libra]]

section 3.3.3

$\sum_{x_1, x_2, ..., x_c \in \{0,1\}^l} f_0(g, x_1, x_2, ..., x_c)f_1(x_1)f_2(x_2)...f_c(x_c)$

general idea
- each phase should have just one variable after partially evaluating already known variables.

example
- $\sum_{x_1,x_2,x_3,x_4 \in \{0,1\}^l} f_0(g, x_1, x_2, x_3, x_4)f_1(x_1)f_2(x_2)f_3(x_3)f_4(x_4)$

- phase 1 poly
- polynomial with constant $G$ and variable $x_1$
- $\sum_{x_1 \in \{0,1\}^l} f_1(x_1) \cdot \sum_{x_2,x_3,x_4 \in \{0,1\}^l} f_0(G,x_1,x_2,x_3,x_4)f_2(x_2)f_3(x_3)f_4(x_4)$
- replace second operand with $h_{G}(x_1)$
- so $h_G(x_1) = \sum_{x_2,x_3,x_4 \in \{0,1\}^l} f_0(G,x_1,x_2,x_3,x_4)f_2(x_2)f_3(x_3)f_4(x_4)$
- phase 1 poly = $\sum_{x_1 \in \{0,1\}^l} f_1(x_1) \cdot h_G(x_1)$

- phase 2 poly
- polynomial with constants $G, X1$ and variable $x_2$
- $f_1(X1) \cdot \sum_{x_2 \in \{0,1\}^l} f_2(x_2) \cdot \sum_{x_3,x_4 \in \{0,1\}^l} f_0(G,X1,x_2,x_3,x_4)f_3(x_3)f_4(x_4)$
- replace second operand with $h_{G,X1}(x_2)$
- $h_{G,X1}(x_2) = \sum_{x_3,x_4 \in \{0,1\}^l} f_0(G,X1,x_2,x_3,x_4)f_3(x_3)f_4(x_4)$
- phase 2 poly = $f_1(X1) \cdot \sum_{x_2 \in \{0,1\}^l} f_2(x_2) \cdot h_{G,X1}(x_2)$

- phase 3 poly
- polynomial with constants $G, X1, X2$ and variable $x_3$
- $f_1(X1) \cdot f_2(X2) \cdot \sum_{x_3 \in \{0,1\}^l} f_3(x_3) \cdot \sum_{x_4 \in \{0,1\}^l} f_0(G,X1,X2,x_3,x_4)f_4(x_4)$
- replace second operand with $h_{G,X1,X2}(x_3)$
- $h_{G,X1,X2}(x_3) = \sum_{x_4 \in \{0,1\}^l} f_0(G,X1,X2,x_3,x_4)f_4(x_4)$
- phase 2 poly = $f_1(X1) \cdot f_2(X2) \cdot \sum_{x_3 \in \{0,1\}^l} f_3(x_3) \cdot h_{G,X1,X2}(x_3)$

- phase 4 poly
- polynomial with constants $G, X1, X2, X3$ and variable $x_4$
- phase 4 poly = $f_1(X1) \cdot f_2(X2) \cdot f_3(X3) \cdot \sum_{x_4 \in \{0,1\}^l} f_0(G,X1,X2,X3,x_4)f_4(x_4)$