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.

  • $\begingroup$ Sorry for the late reaction. Thank you for the clear explanation :) $\endgroup$ – Pieter Verschaffelt May 15 '18 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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