Constructing secure key exchange protocol

Question

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

Thanks, Nick.

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.