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?

  • $\begingroup$ What if all of this correct and your implementation is incorrect? $\endgroup$
    – kelalaka
    Oct 18 '18 at 6:03
  • 1
    $\begingroup$ 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. $\endgroup$ 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!


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.