How can we generalize the conversion of Diffie-Hellman to El Gamal public-key encryption scheme? The goals is to be eventually able to show that any 2-round key-exchange protocol can be converted into a public encryption scheme that is CPA-secure.

The 2-round key-exchange protocol mentioned should satisfy the requirement that: given a key K, it will not be able to determine whether it was given the "correct" key corresponding to the given execution of the protocol, or whether K is completely random key independent of the execution.

  • $\begingroup$ I suppose this depends on what you understand with "two-round key-exchange protocol". Diffie-Hellman is actually only one round, since the message from Alice to Bob and the one from Bob to Alice are completely independent from each other. We need a KE protocol which is secure against repetitions of the first message (as this is Alice's public key). $\endgroup$ Dec 3 '11 at 21:52
  • 1
    $\begingroup$ Random question: Are you (the OP) a graduate student at IU? Barring some kind of bizarre coincidence, your question is identical to one of my current homework questions, even down to my professor's hint on the problem. $\endgroup$
    – pg1989
    Dec 6 '11 at 23:54

The conversion of Diffie-Hellmen into Elgamal is assisted by a few factors that are not inherent to key exchange/agreement protocols in general, but a general conversion may be possible.

The DH $\rightarrow$ Elgamal case. In Diffie-Hellman, Alice generates $a$ and sends a representation of it: $g^a$. Bob generates $b$ and sends $g^b$. Both parties can compute $g^{ab}$. To convert to Elgamal, Alice starts the protocol generating $a$ and posts $g^a$ so anyone can complete Diffie-Hellman with her. If Bob wants to complete the protocol, he generates $b$ and sends $g^b$. To make it encryption, he generates the shared secret $g^{ab}$ and multiplies in his message $mg^{ab}$ and sends that as well.

Why is this CPA-secure? Under DDH-assumption $g^{ab}$ is indistinguishable from a random group element so it works as a sort of one-time pad. Since the sender contributes $b$ to the random mask, each encryption of the same message results in a different ciphertext.

What is needed for a general conversion? (These is just "brainstorming" and not meant to be comprehensive).

  • It is important to have a DDH-type assumption that shows the shared secret is indistinguishable from random.
  • The shared secret must be an element of a group so there is a permissible operation that can be used to combine it with the message with closure.
  • The conversion is also assisted by being from an unauthenticated key exchange. Most other common key exchange protocols are authenticated (or mutually authenticated). This doesn't necessary prevent a conversion, just adds unnecessary weight to the encryption scheme (and if you strip off the authentication, you may find yourself back at basic Diffie-Hellman).
  • As per @Paulo's comment, Alice's first move must be securely repeatable.
  • While in DH, this does not occur, there is not problem with Bob using Alice's output from the first move to generate his share. So two-round protocols are fine when only one party is needed in the second round.

It would be interesting if you could provide some examples of other key exchange protocols that are eligible for conversion. I think you'll find the majority are either based on adding properties to Diffie-Helman that assists in making it a better key exchange but doesn't assist you in a conversion, or they don't lend themselves to conversion (too many rounds, they already use public key encryption, etc.)


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.