Packing HE ciphertexts for coordinate-wise multiplication

Let \(X\) be an integer, and \((x_n,...,x_0)\) binary decomposition

Goal: define packing technique so that we can assume that the scheme works over messages that are vectors in \(F^n_p\) despite the HE message space are polynomials in \(R=F_p[X]/(X^n + 1)\).

To this end we want define a bijection \((encode, decode)\) where
\(encode: F_p^n \to R=F_p[X]/(X^n + 1))\) s.t. \(\forall v_1, v_2 \in F^n_p: v_1\cdot v_2 = decode(encode(v_1) * encode(v_2))\)

Let \(z\) be an integer, \(n = 2^z\), \(m = 2 · n\), and \(p\) be a prime such that \(p = 1 \mod m\).
In this case, \((X^n + 1)\) splits over \(F_p\), i.e., \((X^n +1) = \prod_i F_i(X)\), where each \(F_i\) is a linear polynomial.

The \(encode\) function can be defined via CRT encoding as follows.

Given \(\vec v\), build a polynomial \(p(X)\) of degree \(n-1\) by solving the following system of equations
\[\forall i: p(X) = v_i \bmod F_i(X)\]

The \(decode\) function is the one that, on input a polynomial \(p(X)\), returns the vector
\[(p(X) \bmod F_1(X), \ldots, p(X) \bmod F_n(X))\]

Let us briefly see how the homomorphic property holds after a multiplication. Assume \(p_j(X) =encode(\vec v_j)\) for \(j=1,2\), and that \(p(X) = p_1(X)\cdot p_2(X) \bmod (X^n + 1)\). Namely, \(p(X) = p_1(X)\cdot p_2(X) - t(X) (X^n + 1)\) for some polynomial \(t(X)\).

Then
\[p(X) \bmod F_i(X) = p_1(X)\cdot p_2(X) - t(X) (X^n + 1) \bmod F_i(X) = \]
\[ p_1(X)\cdot p_2(X) \bmod F_i(X) = v_{1,i} \cdot v_{2,i}\]
(using the fact that \(X^n + 1 \mod F_i(X) = \prod_j F_j(X) \bmod F_i(X) = 0\))