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&lt;n$ 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$.