A key agreement protocol between a first party and a second party comprises the following steps from the first party perspective. An encrypted first random key component is directed to the second party, the first random key component having been computed at the first party and encrypted using a public key of the second party in accordance with an identity based encryption operation. An encrypted second random key component corresponding to the second party is received. The encrypted second random key component is decrypted using a private key of the first party. A session key for use in subsequent communications between the first party and the second party is computed based at least in part on the second random key component.