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