# Chosen ciphertext insecurity in an ElGamal variant

I'm trying to prove something and if I can show that there is a simple way to calculate $(g^a \bmod p)^k$ if I know both $g^k \bmod p$ and $g^a \bmod p$, then (I think) it will help me prove it, but I'm not able to see an obvious way to use the two expressions to calculate the other. Is there a property in modular arithmetic that would allow for that? Or does it seem clearly untrue? I think there may just be some gaps in my knowledge about modular arithmetic so if you have a resource for that you'd like to point me to, that might also help.

If it makes a difference, the broader question I'm trying to solve is the following. We consider a modification of the ElGamal cryptosystem (called the basic ElGamal cryptosystem) where we have $p$, a prime, and $q$, a prime divisor of $p-1$. We have $g$, an element of order $q$ in $\mathbb{Z}^*_p$. The private key is an integer $a$ chosen randomly between $1$ and $q-1$. The public key is $h = g^a \bmod p$. And the ciphertext is $c=\langle c_1, c_2\rangle$ where $c_1 = g^k \bmod p$ and $c_2 = m \, h^k \bmod p$, where $k$ is random between $1$ and $q-1$. I need to prove that this is insecure under a chosen ciphertext attack (and whether it is insecure based on total break, one-way security, semantic security).

Since I know that the regular ElGamal cryptosystem is semantically secure if the Decisional Diffie-Hellman (DDH) assumption holds, I thought that if I can prove that it doesn't hold here, I can show that it is not semantically secure. That's why I wanted to ask this question but if this doesn't make sense as a way to show this, let me know so I can try something else.

-
look at your "Diffie-Hellman and ElGamal" slides and/or see my answer below. – Oleksi Apr 5 '13 at 0:53

There is no known way to compute $(g^a)^k \mod p = g^{ak} \mod p$,

given only

$g^k \mod p$ and

$g^a \mod p$

as per the Decisional Diffie–Hellman assumption. This is roughly equivalent to the discrete log problem. This is described in more detail in this paper.

-
Is it the same result for (g^a(mod p))^k as it is for (g^a)^k(mod p)? – user1136342 Apr 5 '13 at 1:13
Not 100% sure, but I think so. – Oleksi Apr 5 '13 at 1:49