Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
look at your "Diffie-Hellman and ElGamal" slides and/or see my answer below. –  Oleksi Apr 5 '13 at 0:53
add comment

1 Answer 1

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.

share|improve this answer
    
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
1  
Not 100% sure, but I think so. –  Oleksi Apr 5 '13 at 1:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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