# Applying Chinese RemainderTheorem and Paillier Homomorphic encryption

I'm trying to optimize the decryption process for Paillier Homomorphic Encryption (PHE) using the Chinese Remainder Theorem (CRT). However, I want to check if there's a different way of applying CRT to PHE apart from the traditional approach and still get the same result or a faster result since there's a simpler variant for the PHE as stated here in Wikipedia.

Recall that,

𝑚=𝐿(𝑐^𝜆  𝑚𝑜𝑑 𝑛^2 ). 𝜇 𝑚𝑜𝑑 𝑛,   𝑐= 𝑔^𝑚.𝑟^𝑛  𝑚𝑜𝑑 𝑛^2,   𝜆=𝜑(𝑛)=(𝑝−1)(𝑞−1)

𝜇=[(𝐿(𝑔^𝜆 𝑚𝑜𝑑𝑛^2 ))]^(−1)𝑚𝑜𝑑 𝑛,   𝜇=𝜑(𝑛)^(−1) 𝑚𝑜𝑑 𝑛 = [(𝑝−1)(𝑞−1)]^(−1) 𝑚𝑜𝑑 𝑛

𝑚=𝐿(𝑐^𝜆  𝑚𝑜𝑑 𝑛^2 ). 𝜇 𝑚𝑜𝑑 𝑛

𝑚=𝐿(𝑐^((𝑝−1)(𝑞−1))  𝑚𝑜𝑑 𝑛^2 ). [[(𝑝−1)(𝑞−1)]^(−1)  𝑚𝑜𝑑 𝑛]𝑚𝑜𝑑 𝑛

𝑚𝑝= 𝐿𝑝 [(𝑐^((𝑝−1))  𝑚𝑜𝑑 𝑝^2 ).(𝑝−1)^(−1) 𝑚𝑜𝑑 𝑝]𝑚𝑜𝑑 𝑝

𝑚𝑞= 𝐿𝑞 [(𝑐^((𝑞−1))  𝑚𝑜𝑑 𝑞^2 ).(𝑞−1)^(−1) 𝑚𝑜𝑑 𝑞]𝑚𝑜𝑑 𝑞

Let 𝑘𝑝= (𝑝−1)^(−1) 𝑚𝑜𝑑 𝑝       and       𝑘𝑞= (𝑞−1)^(−1) 𝑚𝑜𝑑 𝑞

𝑚𝑝= 𝐿𝑝 [(𝑐^((𝑝−1))  𝑚𝑜𝑑 𝑝^2 )] 𝑘𝑝 𝑚𝑜𝑑 𝑝

𝑚𝑞= 𝐿𝑞 [(𝑐^((𝑞−1))  𝑚𝑜𝑑 𝑞^2 )] 𝑘𝑞 𝑚𝑜𝑑 𝑞

𝑚 = CRT(𝑚𝑝, 𝑚𝑞) 𝑚𝑜𝑑 𝑝𝑞

𝑚 = 𝐿𝑝 [(𝑐^(𝑝−1)  𝑚𝑜𝑑 𝑝^2 ) 𝑘𝑝 𝑚𝑜𝑑 𝑝]  + 𝐿𝑞 [(𝑐^(𝑞−1)  𝑚𝑜𝑑 𝑞^2 ) 𝑘𝑞 𝑚𝑜𝑑 𝑞]

𝑚  = 𝐿(𝑐^𝜆  𝑚𝑜𝑑 𝑛^2 ). 𝜇 𝑚𝑜𝑑 𝑛


Implementing the above steps in python gave me an inconsistent decryption result.

Is this proof correct, and if not, can anyone please explain as to why it's not correct and how to make it correct?

• What if all of this correct and your implementation is incorrect? – kelalaka Oct 18 '18 at 6:03
• Nine time out of ten the issue with implementing something like this is that the modular arithmetic is wrong. I'd double check that you are doing division and modular exponentiation correctly. – puzzlepalace Oct 18 '18 at 22:25

A working method for CRT-aided decryption in Pailler goes:

• Evaluate $$x=c^\lambda\bmod n^2$$ by the Chinese Remainder theorem, that is
• $$x_p\gets c^\lambda\bmod p^2$$
• $$x_q\gets c^\lambda\bmod q^2$$
• $$x\gets\left(q^{-2}(x_p-x_q)\bmod p^2\right)q^2+x_q$$
• Then evaluate $$m\displaystyle\gets\left\lfloor\frac{x-1}n\right\rfloor\,\mu\bmod n$$.

The savings are by a factor of at most 2, rather than at most 4 for RSA, because the exponent $$\lambda$$ remains the same size, when its $$d_p$$ and $$d_q$$ have their size halved in RSA.

The question's method is broken where it goes from the following line to the next:

\begin{align} m&=L\left(c^{(p-1)(q-1)}\bmod n^2\right)\cdot\left((p-1)(q-1)^{−1}\bmod n\right)\bmod n\\ m_p&=L_p\Big(\left(c^{p-1}\bmod p^2\right)\cdot\big((p-1)^{−1}\bmod p\big)\Big)\bmod p \end{align}

Problems are:

1. Function $$L_p$$ is not stated. I work under the assumption that $$L_p$$ is to $$p$$ what $$L$$ is to $$n$$, that is $$L_p(x)\displaystyle=\left\lfloor\frac{x-1}p\right\rfloor$$. Also I assume $$m_p=m\bmod p$$.
2. The term $$(q-1)^{-1}$$ of the first equation mysteriously vanishes from the second.
3. Something on the tune of $$L(x)\equiv L_p(x)\bmod p$$ seems to be assumed without justification.
4. The term $$(p-1)^{-1}\bmod p$$ (which BTW is always $$p-1$$) has mysteriously entered the input of $$L_p$$ when $$(p-1)^{-1}$$ was at the output of $$L$$.

Numerical experiments disprove the second equation (under the assumptions made in 1). If there is a way to repair it, I want to know!