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.

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

share|improve this question
Are you refering to this? –  mikeazo Dec 11 '12 at 13:32

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer


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.