A computing device sends a request for an attestation certificate to an attestation service along with information regarding the hardware and/or software of the device. The attestation service processes the request and verifies the information received from the device. After verifying the information, the attestation service selects a public/private key pair from a collection of reusable public/private key pairs and generates an attestation certificate for the device and public key of the public/private key pair. This attestation certificate is digitally signed by the attestation service and returned to the device. The private key of the selected public/private key pair is also encrypted to a trusted secure component of the device, ensuring that the key cannot be stolen by malware and re-used on another device, and is returned to the device. The device uses this attestation certificate to access relying parties, and optionally generates additional public/private key pairs and attestation certificates.