I have $\Pi=(Gen,Enc,Dec)$ and let it be semantically secure public-key encryption scheme. Security parameter is $n$, then the message space of plaintext is always $\lbrace 0, 1 \rbrace^n$.

By using $\Pi$ I want to construct key exchange protocol $\Theta$. There should be 2 rounds (i.e. one for Alice and one for Bob). It must be secure against eavesdroppers (and it'd should be possible to prove it :) ).

Of course the only assumption is security of $\Pi$. For example Diffie–Hellman key exchange protocol fits to this exercise (if we assume somethink), but I don't know how to generalize it.

P.S. The key Alice and Bob establish $\in \lbrace 0, 1 \rbrace^n$.

  • $\begingroup$ CurveCP is a protocol with properties similar to TLS, but that uses only DH-Keyexchange and authenticated symmetric encryption. $\endgroup$ Oct 24, 2012 at 20:03

1 Answer 1


Well, the obvious way to do this is:

  • Before the protocol occurs, Alice runs the $Gen$ procedure to create a public and a private key

  • For her round, Alice sends her public key to Bob

  • For his round, Bob selects a random symmetric key $\in \{0,1\}^n$, encrypts it with Alice's public key, and sends that encryption to Alice.

  • Alice decrypts the message that Bob sent her with her private key.

Now, Alice and Bob share a random symmetric key (Bob knows it because he created it, Alice knows it because she decrypted it). In addition, Eve has no information on the key; the only thing that could possibly give her information about it is the encrypted version in round 2; and because we assume $\Pi$ is semantically secure, that gives her no information.

  • 1
    $\begingroup$ It has the usual problem of MitM-attacks if there is no additional authentication (e.g. a certificate for Alice's public key). $\endgroup$ Sep 26, 2012 at 7:58
  • $\begingroup$ Yes that's vulnerable to a MitM, as any key exchange protocol without authentication. Further, if the MitM can induce Bob to perform the protocol the way Alice does it, the attack needs to be active only in an initial step, then can become passive eavesdropping; the MitM intercepts and mutes the messages sent by Alice and Bob, and sends one message to each deciding the shared key. $\endgroup$
    – fgrieu
    Sep 26, 2012 at 10:56
  • 1
    $\begingroup$ @PaŭloEbermann: yes, that is vulnerable to a MITM. HOwever, standard DH is also equally vulnerable, and the submitter specifically said that DH solved the problem. Yeah, I probably should have mentioned that MITM needs to be addressed somehow in real life. $\endgroup$
    – poncho
    Sep 26, 2012 at 11:02

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.