Opening "packed" univariate polynomials over binary fields.

Acknowlegements: Based on Lev's Ideas 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??!!