# Opening "packed" univariate polynomials over binary fields.

*Acknowlegements: Based on [Lev's Ideas](https://hackmd.io/@levs57/SJ4fuZMD0) for the multilinear case.
Thanks also to Ulrich Haböck for motivating discussions on fri-binius and packing*

**The problem:**
We have $k$ univariate "component polynomials" $P_1(X),\ldots,P_k(X)$ with binary coefficients:
$P_j(X):=\sum_{i<n} c_{i,j}X^i$,
where the $c_{i,j}$ are bits.

Let $K$ be the field $F_{2^k}$.
We wish to have an efficient scheme to commit to the $\{P_j\}$ and open them all at a given point $r\in K$.
We assume we are given some base univariate PCS over $K$, e.g. KZG. We wish to
have a more efficient solution than using the PCS separately for each $P_j$, and even more efficient than fflonk in commitment time.

Let $b_1,\ldots,b_k$ be a basis of $K$ over $F_2$.

We define the "packed polynomial" $P(X)$ over $K$ as
$P(X)=\sum_{\ell<n} c_\ell X^\ell$
where $c_\ell:= \sum_{j\in [k]} c_{\ell,j}b_j$.

Let $Tr$ be the trace of $K$ over $F_2$. Concretely $Tr(c):=\sum_{0\leq \ell<k} c^{2^\ell}$.

We use the following algebraic claim (that can be found in textbooks about finite fields, *TODO: add ref*)

**Claim:** For each $j\in [k]$, there exists $d_j\in K$ such that for any bits $e_1,\ldots e_k$ the following holds.
Set $e=\sum_{i \in [k]} e_{i} b_i$.
Then $Tr(d_j\cdot e)= e_j$.

### The scheme

Our scheme will be as follows:
**commit:** To commit to $\{C_j\}_{j\in [k]}$ simply commit to the packed polynomial $C$ using the base PCS.

**Open:** To open all the $\{C_j\}_{j\in [k]}$ at a point $r\in K$ do the following.
Open $C$ at the points $r,r^{-2},\ldots,r^{-2^{k-1}}$.
(Note that these points are well defined as squaring is bijective on $K$)

Call the obtained evaluations, $z_1,\ldots, z_k$. That is $z_j=C(r^{-2^{j}})$, except with negligible probability under the soundness of the base PCS.

Now, for each $j\in [k]$ compute $C_j(r)$ as
$C_j(r)= \sum_{i\in [k]}(d_j z_i)^{2^i}$

Let's see why this works:
$z_i^{2^i}= (C(r^{-2^{i}}))^{2^i}$
$=(\sum_{0\leq \ell <n }c_\ell(r^{-2^i})^\ell)^{2^i}= \sum_{\ell <n} c^{2^i}_{\ell}r^{\ell}$

Plugging this in and changing summation order, we have for each $j$:
$\sum_{i\in [k]} (d_j z_i)^{2^i}$
$=\sum_{i\in [k]} (d_j^{2^i}\sum_{\ell <n} c^{2^i}_{\ell}r^{\ell})$
$=
\sum_{\ell <n} r^{\ell} \sum_{i\in [k]} (d_jc_\ell)^{2^i}$

$=\sum_{\ell <n} r^{\ell} Tr(d_j c_\ell)=\sum_{\ell <n} r^{\ell} c_{j,\ell}= C_j(r)$,

Where we used the above claim in the second last equality.

**Open Question:**
*Can we do similar packing over prime field??!!*