What is the need for two private/public keys in twin elgamal? I'm relatively new and would need some help.

  • $\begingroup$ Are you refering to this? $\endgroup$
    – mikeazo
    Commented Dec 11, 2012 at 13:32

1 Answer 1


At a purely technical level, having the two group elements and secret exponents enables a proof, in the random oracle model, that the scheme is CCA secure assuming that decision Diffie-Hellman is hard. For regular (hashed) ElGamal, we only know how to prove CCA security in the random oracle model under a stronger assumption (in our paper we called it strong Diffie-Hellman, but gap Diffie-Hellman seems more common).

The intuition for why the two keys should help is more difficult. At a very high level, by deriving the session encryption key as the hash of two Diffie-Hellman group elements, we are getting some "verifiable proof" that the ciphertext was either properly computed or is useless to the adversary, and allows the reduction to respond accordingly. Looking back at regular ElGamal, the difference is that "proof" is not "verifiable". The stronger assumption in the CCA proof of ElGamal is what technically allows this "proof" to become "verifiable".

The paper makes this argument formal. In order to understand it better, I'd recommend starting with this paper, which gives the mentioned proof for hashed ElGamal under the stronger assumption. Then one can contrast it with the twin construction and security analysis.


Your Answer

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

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