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?
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&amp;=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&amp;=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:


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$.
The term $(q-1)^{-1}$ of the first equation mysteriously vanishes from the second.
Something on the tune of $L(x)\equiv L_p(x)\bmod p$ seems to be assumed  without justification.
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!