1
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Where $2 \min(p_i) > \max(p_i)$ requirement is coming from, why do we need it? $\endgroup$ – Vadym Fedyukovych Jun 11 '18 at 7:36
  • $\begingroup$ @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. $\endgroup$ – fgrieu Jun 11 '18 at 8:40
  • $\begingroup$ 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. $\endgroup$ – Vadym Fedyukovych Jun 12 '18 at 18:09

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.