I have an encryption scheme $Enc(pk, m)$ which outputs ciphertext of the form $c_1 = (pk)^r, c_2 = g^r \cdot m$; where $pk$ is the public key of the form $g^a$, $a$ being the corresponding secret key.

Is this secure?

  • $\begingroup$ I am curious how would you decrypt the ciphertext? $\endgroup$
    – Shan Chen
    Jun 21 '18 at 6:06
  • $\begingroup$ One can decryption using the secret key of that public key i.e $(pk^r)^{sk^{-1}}$ and get $g^r$ $\endgroup$
    – Cinderella
    Jun 21 '18 at 7:04

If you are working in an order $p$ prime order group which is generated by $g$, and $a$ as well as $r$ are drawn uniformly random from $\mathbb{Z}_p$, you can prove this secure under the decisional Diffie-Hellman (DDH) assumption (what you sketch here, is often referred to as modified ElGamal in the literature).

Informally speaking, under DDH you can show that $c_1$ looks like a random value. Now, once you have shown that $c_1$ looks random, you can view $g^r$ like a one-time pad on the message.

See Section 3 of this paper for an excellent formal treatment.

  • $\begingroup$ Thanks! But, I am a bit curious how can I model the adversary's view in the security game by injecting the DDH tuple in $c_1$. Do you have any good reference for such kind of proofs? $\endgroup$
    – Cinderella
    Jun 22 '18 at 1:41
  • $\begingroup$ @Cindarella I've added a reference to my answer. $\endgroup$
    – dade
    Jun 24 '18 at 9:30

If $a$ is not coprime to $\phi(p)$ with prime modulus $p$ (assuming your group is $\mathbb{Z}_p$ with generator $g$), then you actually can not recover $g^r$ from $(pk)^r$.

Example: $pk$ has order $2$, so that $(pk)^r = pk$ or $(pk)^r=1$. And that gives you just one bit of information about $r$: You get $k\mod 2$.

If the group generated by $pk$ is smaller than the group generated by $g$, there is a loss of information, and you won't get a unique decryption.

If $a$ is coprime to $\phi(p)$ and generates the same group as $g$, then let's define $g' = pk, a' = a^-1 \mod \phi(n)$, and then this variant is exactly the same as ElGamal with generators $g'$ and private key $a'$. And the security proof follows immediately from that.


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.