2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$ ? $\endgroup$ – Hilder Vítor Lima Pereira Jul 4 '18 at 12:17
  • 1
    $\begingroup$ 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. $\endgroup$ – Ruiqi Li Jul 5 '18 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.