# Can the CRT speed-up Paillier decryption by more than a factor of two?

In the Pailler cryptosystem, decryption goes $$m\gets\displaystyle\left\lfloor\frac {\left(c^\lambda\bmod n^2\right)-1}n\right\rfloor\mu\bmod n$$ with $$\mu being a part of the private key just like $$\lambda=\operatorname{lcm}(p-1,q-1)$$ for $$n=p\,q$$.

The Chineese Remainder Theorem allows to speed-up this computation knowing the factorization $$n=p\,q$$, as follows:

• 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$$
note: $$q^{-2}\bmod p^2$$ can be precomputed.
• Then evaluate $$m\displaystyle\gets\left\lfloor\frac{x-1}n\right\rfloor\,\mu\bmod n$$.

This speeds-up decryption by a factor of at most two (each of the first two modular exponentiations is manipulating values half as large as for $$c^\lambda\bmod n^2$$, and is thus at best four times faster). In RSA, the CRT gives larger savings (sometime approaching four), because the exponents $$d_p$$ and $$d_q$$ have about half the size of $$d$$.

Can we improve the savings obtained and exceed a factor of two?

This question is an attempt to compute $$m_p=m\bmod p$$ and $$m_q=m\bmod q$$, then use the CRT to get $$m$$. If the computation of $$m_p$$ could somewhat we performed mostly modulo $$p$$ or $$p^2$$, perhaps the savings would be improved.

Since CRT is an isomorphism computing $$m_p=m\bmod q$$ and $$m_q=m\bmod q$$ directly is possible. To see this in the formulas above replace the $$\bmod n$$ step with $$p$$ and $$q$$.
To the question, I don't know if working in $$\mathbb{Z}_{p^2}^{*}$$ and $$\mathbb{Z}_{q^2}^{*}$$ could let you compute $$m_p$$ and $$m_q$$ more quickly than simply doing the steps modulo the prime factors of $$n$$. One thing that could help is to reduce $$\lambda$$ by the order of $$\mathbb{Z}_{p^2}^{*}$$ (or $$q^2$$ respectively). The order is given by the Euler totient function of $$p^2$$ which is $$\phi(p^2) = p(p-1)$$. This helps when $$p$$ or $$q$$ is small but in general doesn't speed things up.
The only other comment I can make is the improvement you want would need to exploit some property of the group of elements of the form $$x=c^\lambda\bmod n^2$$ under multiplication. This is the group of elements of order dividing $$n$$. Its two nontrivial subgroups are the elements of order dividing $$p$$ and $$q$$.
• I see how we have $m_p=\displaystyle\left\lfloor\frac {\left(c^\lambda\bmod n^2\right)-1}n\right\rfloor\mu\bmod p$, same for $m_q$, and that we can get $m$ from $m_p$ and $m_q$. But that's not any a faster than computing $m$ by the normal method. And I fail to see how the $\bmod p$ can get into the input of the floor function in that definition of $m_p$, which seems necessary to "reduce $\lambda$" as in the answer. – fgrieu Oct 23 '18 at 13:51