# 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$)