Regulatory policies such as EU privacy, HIPAA, and PCI-DSS place requirements on availability, integrity, migration, retention, and access of data, and compliance with such policies on stored data remains a key hurdle to cloud computing. This paper proposes a policy management service that offers scalable management of data retention policies attached to data objects stored in a cloud environment. An important aspect of any data retention service is permanent deletion of data. We achieve secure data deletion by encrypting the data when stored, and then deleting the encryption key at a specified retention time. Thus, we effectively delete the data object and its copies stored in online and offline environments. Our data retention service includes a highly scalable and secure encryption key store to manage encryption keys on-line. A prototype deployed on a 16-machine Linux cluster currently supports 56 MB/sec for encryption, 76 MB/sec for decryption, 31,000 retention policies/sec read and 15,000 retention policies/sec write.