I don't see this property $\gcd(p\,q,(p-1)(q-1))=1$ used in the scheme. And in Paillier's original paper, I don't find this requirement.

Is it required just for the difficulty of factoring $n$?
Or is it related to the specific security of Paillier Encryption?

  • 2
    $\begingroup$ Hint: the condition (or rather, an equivalent one) is in Paillier's paper, in "Since $\gcd(\lambda,n)=1$" in the proof of Lemma 3. What happens if this condition is not met (and proving that the probability of that is extremely low for a conventionally generated RSA modulus $n$) is left to an answer (that I do not plan to write) to an interesting question. Also, if someone can spot the justification for the "Since" rather than Further assuming the overwhelmingly likely condition, I want to know. $\endgroup$
    – fgrieu
    Sep 29 at 4:44
  • $\begingroup$ $gcd(\lambda,n)=1$ and $gcd(n,(p-1)(q-1)=1$ implies each other, so they are equivalent. However, I still don't know why it is required. Since in wiki, $g$ is not generated as in Paillier's paper. $\endgroup$ Sep 29 at 7:08
  • $\begingroup$ Does anyone know where the wiki version comes from? $\endgroup$ Sep 29 at 7:41
  • $\begingroup$ Extra hint: if we take the artificially small example of $p=23$, $q=47$, $n=1081$, there is the problem that $1^n\equiv24^n\pmod{n^2}$, hence whatever $g$ we choose the function $\varepsilon_g:\mathbb Z_n\times\mathbb Z_n^*\to\mathbb Z_{n^2}^*$ defined by $(x,y)\mapsto x^g y^n\bmod n^2$ will collide. $\endgroup$
    – fgrieu
    Sep 29 at 10:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.