# A question about fully homomorphic SIMD operations

I'm going through Gentry, Halevi and Smart's paper "Fully Homomorphic Encryption with Polylog Overhead" and have a question about the permutation operations.

Background:

The cyclotomic polynomial can be factored modulo $p$, i.e. $\Phi_m(X)=\Pi_{i=0}^{l-1}F_i(X)\mod{p}$. According to CRT (Chinese Remainder Theorem), we have $\mathbb{Z}_p[X]/(\Phi_m(X))\cong \mathbb{Z}_p[X]/(F_0(X))\times\cdots\times\mathbb{Z}_p[X]/(F_{l-1}(X))$.

If I have a message vector $(m_0(X),m_1(X),...,m_{l-1}(X))$ where $m_i(X)\in\mathbb{Z}_p[X]/(F_i(X))$, then I can get the aggregate message $m(X)$ which satisfies $m(X)\mod({F_i(X)},p)=m_i(X)$.

In this paper, they argue that by simply replacing $X$ with $X^i$ inside $m(X)$, for some exponent $i\in\mathbb{Z}^*_m$, we can obtain a new message $m(X^i)$.

On the end of 11th page:

But how does this new aggregate plaintext $m(X^i)$ relate to the original $m(X)$? Here we apply to Galois theory, which tells us that decoding the aggregate $m(X^i)$(which we do roughly by setting $> z_j(X)\leftarrow m(X^i)\mod{(F_j(X),p)}$), the set of $z_j(X)$'s that we get is exactly the same as when decoding the original aggregate $m(X)$, albeit in different order.

I tried to find out some specific examples to prove this, but failed. I find that the $(z_0(X),...,z_{l-1}(X))$ is exactly reordered, but $z_j(X)$ corresponds to $m_k(X^i)$ rather than $m_k(X)$.

Example:

$\Phi_{31}(x)=(1+x^2+x^5)(1+x^3+x^5)(1+x+x^2+x^3+x^5)(1+x+x^2+x^4+x^5)(1+x+x^3+x^4+x^5)(1+x^2+x^3+x^4+x^5)\mod{2}$.

Suppose the message vector is $(m_0(x),m_1(x),m_2(x),m_3(x),m_4(x),m_5(x))=(1+x, 2+x, 3+x, 4+x, 5+x, 6+x)$, its corresponding aggregate message $m(x)$ is $x^2 + x^4 + x^7 + x^8 + x^{11} + x^{13} + x^{14} + x^{16} + x^{19} + x^{21} + x^{22} + x^{25} + x^{26} + x^{28}$.

Then replacing $x$ by $x^6$, we have $m(x^6)=x + x^2 + x^3 + x^4 + x^8 + x^{11} + x^{12} + x^{13} + x^{16} + x^{17} + x^{21} + x^{22} + x^{24} + x^{26}$.

$m(x^6)\mod{(1+x^2+x^5)}=x+x^3=m_5(x^6)$

$m(x^6)\mod{(1+x^3+x^5)}=1+x+x^4=m_0(x^6)$

$m(x^6)\mod{(1+x+x^2+x^3+x^5)}=1+x+x^2+x^3+x^4=m_2(x^6)$

$m(x^6)\mod{(1+x+x^2+x^4+x^5)}=1+x^3+x^4=m_3(x^6)$

$m(x^6)\mod{(1+x+x^3+x^4+x^5)}=x^2+x^3=m_4(x^6)$

$m(x^6)\mod{(1+x^2+x^3+x^4+x^5)}=1+x+x^2=m_1(x^6)$

• I didn't check it in details, but are that section of the paper (4.2) uses a prime $p$ that satisfies $p \equiv 1 \pmod{31}$. Are you sure it would also apply for $p = 2$ ? – Hilder Vítor Lima Pereira Jul 4 '18 at 12:17
• In the full version of this paper, $m=31, p=2$ is one of their example in Appendix C.3. Their example however didn't give the details either. I tried my specific example based on theirs. – Ruiqi Li Jul 5 '18 at 1:38