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<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$.

  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Oct 23 '18 at 13:51

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.