A secure key manager enclave is provided on a host computing system to send an attestation quote to a secure key store system identifying attributes of the key manager enclave and signed by a hardware-based key of the host computing system to attest to trustworthiness of the secure key manager enclave. The secure key manager enclave receives a request to provide a root key for a particular virtual machine to be run on the host computing system, generates a secure data structure in secure memory of the host computing system to be associated with the particular virtual machine, and provisions the root key in the secure data structure using the key manager enclave, where the key manager enclave is to have privileged access to the secure data structure.