TPM remote attestation allows to verify the integrity of the boot sequence of a remote device. Deep Attestation extends that concept to virtualized platforms by allowing to attest virtual components, the hypervisor, and the link between them. In multi-tenant environments, traditional deep attestation schemes offer either security or efficiency, and no privacy for both the infrastructure and the tenants. In this paper, we propose a privacy preserving TPM-based deep attestation solution in multi-tenant environments, which provably guarantees: (i) Inter-tenant privacy: a tenant is unaware of whether or not the physical machine hosting its VMs also contains other VMs (belonging to other tenants); (ii) Configuration hiding: the hypervisor’s configuration, used in the attestation process, remains private with respect to the tenants requiring a hypervisor attestation; and (iii) Layer linking: our protocol enables tenants to link hypervisors with the VMs, thus obtaining a guarantee that their VMs are running on specific physical machines. We also implement our scheme and show that it is efficient despite the heaviness of the used cryptographic tools.