How to recover private key in ElGamal when random value k is known Given following ElGamal encryption scheme: $\delta = M(\alpha^a)^k \mod{p}$. Assume that an attacker knows the random value $k$. How can he recover the private key $a$?

I know that it's possible to recover the message M by computing $\frac{m}{\alpha^a} \mod{p}$. But how can we now derive $a$ from this information and not end up with a discrete logarithm problem?
How can he recover the private key $a$?


They can't. First, note that $\delta=M(\alpha^a)^k\bmod p$ you can (as you already noted), recover $M$ and thus construct $\delta'=(\alpha^a)^k\bmod p$ given $\delta$, $\beta=\alpha^a$ and $k$. Now you are in a situation which is equivalent to that after a Diffie-Hellman handshake. You are given your own ephemeral DH key $k$, the generator $\alpha$ and the shared secret $\delta'$, if you now could actually find $a$, that is the other party's DH key, this would completely and utterly break any form of $a$-reuse which is assumed to be secure.

More formally:
Let $\mathcal O(\delta',k,\alpha,\mathcal G)$ be an oracle, that returns $a$ from $\delta'=(\alpha^a)^k$ in the group $\mathcal G$. Now let $(\beta,\alpha,\mathcal G)$ be an arbitrary discrete-logarithm instance, such that $\beta=\alpha^x$ in $\mathcal G$. Now note that if we call $\mathcal O$ with $\mathcal O(\beta,1,\alpha,\mathcal G)$, we get $x$ back, the discrete logarithm and have thus solved the discrete logarithm problem efficiently using this capability.

This means that if we could recover $a$ from $(\delta',k)$ we could solve the discrete logarithm problem efficiently, but as this is assumed hard, we can't efficiently recover $a$ from $(\delta',k)$. Of course you may also want to note that coming up with $(\delta',k)$ doesn't require any special knowledge, anybody who is ElGamal-encrypting $M=1$ constructs this pair.