# Proving security of an encryption scheme

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?

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

• 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? – Cinderella Jun 22 '18 at 1:41
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.