Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|improve this question
CurveCP is a protocol with properties similar to TLS, but that uses only DH-Keyexchange and authenticated symmetric encryption. – CodesInChaos Oct 24 '12 at 20:03
up vote 3 down vote accepted

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.

share|improve this answer
It has the usual problem of MitM-attacks if there is no additional authentication (e.g. a certificate for Alice's public key). – Paŭlo Ebermann Sep 26 '12 at 7:58
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. – fgrieu Sep 26 '12 at 10:56
@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. – poncho Sep 26 '12 at 11:02

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.