3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ look at your "Diffie-Hellman and ElGamal" slides and/or see my answer below. $\endgroup$
    – Oleksi
    Apr 5, 2013 at 0:53

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is it the same result for (g^a(mod p))^k as it is for (g^a)^k(mod p)? $\endgroup$ Apr 5, 2013 at 1:13
  • 1
    $\begingroup$ Not 100% sure, but I think so. $\endgroup$
    – Oleksi
    Apr 5, 2013 at 1:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.