A compute instance of a virtual computing service (VCS) is assigned first and second cryptographically verifiable identities (CVIs) within respective namespaces. A cryptographic key pair associated with the first CVI includes a non-transferable private key managed by a secure key store which does not permit the private key to be copied. The VCS enables the instance to use the private key for asserting the CVIs. In response to a first identity query, the instance indicates the first CVI. In response to a second identity query, the instance indicates the second CVI.