Paillier's scheme generalisation

Question

Paillier's scheme assume has message and ciphertext space equal to $\mathbb{Z}_N$ with $N=pq$, that is $N$ is the product of two different primes.

Is there a way to generalise this for $N$ that is the product of many ($>2$) different primes?

Answer 1

Yes, Pailler encryption can be generalized to the product of more than two (distinct) primes, much like in multi-prime-rsa. We just have $N=\prod p_i$ with $i\ne j\implies p_i\ne p_j$. Each $p_i$ must be secret and uniformly random in some large interval. It we want to use $g=N+1$ as the generator (which is common) without an explicit check of its order, it remains enough to ensure that $2\min(p_i)>\max(p_i)$. For $n$ primes, choosing $p_i$ as a random prime in $(2^{1024-1/n},2^{1024})$ ensures that, and that $N$ is exactly $1024\,n$ bits, and may simplify code using the last section's speedup by making all the primes standard-sized. For a working random prime generator and reasonable $n$, odds of hitting two equal factors or enabling a Fermat factorization remain negligible.

For the other steps of key generation, and for decryption, it is enough to compute $\varphi(N)$ or/and $\lambda(N)$ correctly:

• $\varphi(N)$ is the product off all the $(p_i-1)$
• $\lambda(N)$ is the Least Common Multiple off all the $(p_i-1)$

There's noting special to do for encryption; in fact there is no way to recognize from the public key if $N$ is the product of two or of more large primes.

---

If we want a speedup at decryption, we have the option to compute $c^{\lambda(N)}\bmod N^2$ (which is where most of the computation effort is spent) by computing $c^{\lambda(N)}\bmod{p_i}^2$ separately for each $p_i$, and using the Chinese remainder theorem to obtain the final result. That works like there, except

• for the moduli $r_i$ there, we use ${p_i}^2$
• for their reduced exponents $d_i$, we use $\lambda(N)\bmod\lambda({p_i}^2)$, that is $\begin{align} d_i&=\lambda(N)\bmod(p_i(p_i-1))\\ &=\left(\frac{\lambda(N)}{p_i-1}\bmod p_i\right)(p_i-1) \end{align}$.

The speedup obtained by using the CRT is by a factor about $n^2/2$ (with classical mulmod algorithms of cost proportional to the square of the number of bits); that's about half the speedup in multiprime RSA, because in Pailler the exponent $\lambda(N)$ has about half as many bits as the modulus $N^2$, whereas in RSA the exponent $d$ has about as many bits as the modulus $N$.