I was asked about the following variant of $ElGamal$ Encryption Scheme (Preparing for exam):

Instead of encrypting $(g^r,h^r*m)$, encrypt $(g^r,h^r+m)$. And the question is whether the new variant CPA secure? In addition, is it Homomorphic in relation to addition or multiplication?

Regarding the question of whether is it CPA secure, i'm think that no Because of the fact that i can build an $Adversary$ who is sent to the Challenger $m0,m1$ and gets back $Cb$ and compute $Cb$ $-$ $m0$ - if the result in G output 0, else output 1. Is this the right way? Plus I can't figure out how to analyze the probability here.

Regarding the question of is it Homomorphic in relation to addition or multiplication, my answer is no.

I would love to get help in better understanding things, any help would be appreciated.

  • $\begingroup$ If you can substruct, then you can divide, too!. The answer no for homomorphic, requires some math, right? Can you distinguish $(g^{r_1}, h^{r_1} +m_1)$ and $(g^{r_2}, h^{r_2} +m_2)$ $\endgroup$
    – kelalaka
    Mar 10 at 13:37
  • $\begingroup$ Thanks for your response dear @kelalaka But I can not see how to proceed from here. I can not understand what divide to do that will advance me to be able to discern. $\endgroup$ Mar 10 at 14:34
  • $\begingroup$ If you can distinguish with substruction then you can distinguish with division, too, right? Look at the standard CPA proof of Elgamal. $\endgroup$
    – kelalaka
    Mar 10 at 14:36
  • $\begingroup$ Oh! @kelalaka You are basically saying that the scheme is CPA secure and i need to build a Reduction to the original ElGamal scheme? $\endgroup$ Mar 10 at 14:41
  • $\begingroup$ No, Follow the CPA lines of the normal Elgamal and notice any problem if there any. $\endgroup$
    – kelalaka
    Mar 10 at 18:41

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.