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_p^n$ 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.

$\mathrm{\forall }{v}_1,v_2\in F_p^n:v_1\cdot v_2=decode(encode(v_1)\ast encode(v_2))$

Let

$z$ be an integer,

$n=2^z$,

$m=2·n$, and

$p$ be a prime such that

$p=1\mathrm{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

$\overrightarrow{v}$, build a polynomial

$p(X)$ of degree

$n-1$ by solving the following system of equations

$$\mathrm{\forall }i:p(X)=v_{i}mod{F}_i(X)$$

The

$decode$ function is the one that, on input a polynomial

$p(X)$, returns the vector

$$(p(X)mod{F}_1(X),\dots ,p(X)mod{F}_n(X))$$

Let us briefly see how the homomorphic property holds after a multiplication. Assume

$p_j(X)=encode({\overrightarrow{v}}_j)$ for

$j=1,2$, and that

$p(X)=p_1(X)\cdot p_2(X)mod(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)mod{F}_i(X)=p_1(X)\cdot p_2(X)-t(X)(X^n+1)mod{F}_i(X)=$$

$$p_1(X)\cdot p_2(X)mod{F}_i(X)=v_{1,i}\cdot v_{2,i}$$
(using the fact that

$X^n+1\mathrm{mod}{F}_i(X)=\prod _j{F}_j(X)mod{F}_i(X)=0$)