# ElGamal in a different group

Can Elgamal be secure in $\bmod {n^2}$? Meaning instead of using a prime order group to use a group where DCR assumption holds?

• With "DCR", do you mean "Decisional composite residuosity assumption" form Paillier?. Then I would suggest it has nothing to do with ElGamal, because it relates a modulus $n^2$ to the same exponent $n$.
– user27950
Dec 23, 2015 at 18:00

There are a number of multiplicative subgroups in the ring of divisor classes modulo $n^2$. One particular subgroup (with easy logarithm) is generated by $(n+1)$. You would not want to use it for ElGamal. Other subgroup (of large enough order) are fine.
I don't know if anyone has looked at this question specifically. However, Diffie-Hellman modulo a composite $n=pq$ is actually as hard as factoring. See this paper by Biham, Boneh, and Reingold. It is worth seeing if a similar reduction can be proven for DCR.
• I fixed the link. The title is: Breaking Generalized Diffie-Hellman Modulo a Composite is no Easier than Factoring. Regarding DCR and factoring, factoring is at least as hard as DCR (if factoring is easy then DCR certainly is; the opposite direction is not known). My suggestion is to try to prove that DDH is hard mod $n^2$ if DCR is hard. I don't know if it's true, but it's an interesting question. Dec 22, 2015 at 20:29