A modified Host Identity Protocol, HIP, base exchange method is provided for use by first and second HIP hosts (Initiator and Responder) having a shared state from a pre-existing relationship. In the modified HIP base exchange method, an authentication message (I2′) is sent (S2) from the first host (Initiator) to the second host (Responder) comprising an identifier (HITI) of the first host (Initiator) and a cryptographic item (PF). The authentication message (I2′) is received (S3) at the second host (Responder). Following receipt, the identifier and information relating to the shared state are used (S4) to authenticate the cryptographic item (PF). If the cryptographic item, and the rest of the authentication message, is authenticated, a confirmation message (R2′) is sent from the second host (Responder) to the first host (Initiator) to indicate successful authentication. These two messages (I2′ and R2′) are equivalent to the I2 and R2 messages of the standard HIP base exchange protocol, and the requirement for the I1 and R1 messages from the standard HIP base exchange protocol is eliminated.