A method for performing an identity based authenticated key agreement protocol between a computer system of a first party (the first party) and a computer system of a second party (the second party), the method at the first party comprising the steps of: sending an encrypted first random key component from the first party 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; receiving an encrypted random key component pair at the first party from the second party, the random key component pair having been encrypted at the second party using a public key of the first party in accordance with the identity based encryption operation, and the random key component pair having been formed from the first random key component, xP, and a second random key component, yP, computed at the second party; and sending the second random key component, in encrypted form, from the first party to the second party, the second random key component having been encrypted using the public key of the second party in accordance with the identity based encryption operation; wherein a key for use in subsequent communications between the first party and the second party is computable at the first party based on the second random key component; wherein the first random key component, xP, has been computed from a random number x chosen by the first party and a point P of large prime order on an elliptic curve over a finite field, wherein the key, xyP, for use in subsequent communications between the first party and the second party is computed at the first party from the random number x chosen by the first party and the second key random component yP, wherein the second random key component yP has been computed at the second party from a random number y chosen by the second party, and the point P of large prime order on the elliptic curve over the finite field, wherein the elliptic curve used to compute the first random key component and the second random key component is independent of an elliptic curve used for the identity based encryption operation. sending an encrypted first random key component from the first party 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; receiving an encrypted random key component pair at the first party from the second party, the random key component pair having been encrypted at the second party using a public key of the first party in accordance with the identity based encryption operation, and the random key component pair having been formed from the first random key component, xP, and a second random key component, yP, computed at the second party; and sending the second random key component, in encrypted form, from the first party to the second party, the second random key component having been encrypted using the public key of the second party in accordance with the identity based encryption operation; wherein a key for use in subsequent communications between the first party and the second party is computable at the first party based on the second random key component; wherein the first random key component, xP, has been computed from a random number x chosen by the first party and a point P of large prime order on an elliptic curve over a finite field, wherein the key, xyP, for use in subsequent communications between the first party and the second party is computed at the first party from the random number x chosen by the first party and the second key random component yP, wherein the second random key component yP has been computed at the second party from a random number y chosen by the second party, and the point P of large prime order on the elliptic curve over the finite field, wherein the elliptic curve used to compute the first random key component and the second random key component is independent of an elliptic curve used for the identity based encryption operation.