Embodiments are directed to securing data in the cloud, securely encrypting data that is to be stored in the cloud and to securely decrypting data accessed from the cloud. In one scenario, an instantiated trust service receives information indicating that a trust server is to be instantiated. The trust service instantiates the trust server, which is configured to store key references and encrypted keys. The trust service receives the public key portion of a digital certificate for each publisher and subscriber that is to have access to various specified portions of encrypted data. A data access policy is then defined that specifies which encrypted data portions can be accessed by which subscribers.