7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – user27950 Dec 23 '15 at 18:00
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yehuda the link you provided does not work. Can you tell me the title? Thanks $\endgroup$ – curious Dec 22 '15 at 16:19
  • $\begingroup$ 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. $\endgroup$ – Yehuda Lindell Dec 22 '15 at 20:29
  • $\begingroup$ So the general framework towards this would be to construct a PPT A to break DCR by using a PPT B who breaks DDH $\endgroup$ – curious Dec 22 '15 at 20:58
  • $\begingroup$ Also with respect to DCR and factoring i was meaning what you wrote. My semantics were wrong though. Wrong vocabulary to describe a common technical agreement. You need to know the right words to communicate your ideas, but not when you work alone on them :) $\endgroup$ – curious Dec 22 '15 at 21:05
  • $\begingroup$ From "Extended-DDH and Lossy Trapdoor Functions": "This series of works generalizing DDH-based constructions suggests the heuristic that “anything that can be done with DDH can be done with DCR or QR.” Like any heuristic it is not completely accurate, but it appears to provide the right intuition" $\endgroup$ – curious Dec 22 '15 at 21:17

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.