Certification of a key, which a Trusted Platform Module (TPM) has attested as being non-migratable, can be performed in a single round trip between the certificate authority (CA) and the client that requests the certificate. The client creates a certificate request, and then has the TPM create an attestation identity key (AIK) that is bound to the certificate request. The client then asks the TPM to sign the new key as an attestation of non-migratability. The client then sends the certificate request, along with the attestation of non-migratability to the CA. The CA examines the certificate request and attestation of non-migratability. However, since the CA does not know whether the attestation has been made by a trusted TPM, it certifies the key but includes, in the certificate, an encrypted signature that can only be decrypted using the endorsement key of the trusted TPM.