# Paillier's scheme generalisation

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?

Yes, Pailler encryption can be generalized to the product of more than two (distinct) primes, much like in . 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$.

• Where $2 \min(p_i) > \max(p_i)$ requirement is coming from, why do we need it? – Vadym Fedyukovych Jun 11 '18 at 7:36
• @Vadym Fedyukovych: in regular two-primes Pailier, it is common to specify that $p$ and $q$ have the same bit size (the Wikipedia reference mentions that), or slightly more generally that $p<2q$ and $q<2p$ . That ensures $(p−1)/2$ is less than $q$ thus coprime with $q$, and similarly that $(q−1)/2$ is coprime with $p$; which in turn insures that $g=p\,q+1$ is usable as generator without needing any check. $2\min(p_i)>\max(p_i)$ is a generalization of that. – fgrieu Jun 11 '18 at 8:40
• thank you. For the case $q | (p-1)$ (large $p$), it seems decryption result would be restricted as a residue modulo $p$, not $pq$. It seems reference requests are not very welcome for known searcheable ideas. – Vadym Fedyukovych Jun 12 '18 at 18:09