Score:2

Why is asked that gcd(pq,(p-1)(q-1))=1 in the Paillier encryption scheme?

za flag

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?

fgrieu avatar
ng flag
Hint: the condition (or rather, an equivalent one) is [in Paillier's paper](https://link.springer.com/content/pdf/10.1007/3-540-48910-X_16.pdf#page=4), 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.
mactep Cheng avatar
za flag
$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.
mactep Cheng avatar
za flag
Does anyone know where the wiki version comes from?
fgrieu avatar
ng flag
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.