Individuals, enterprises, and government agencies encrypt information before uploading to commodity cloud storage systems like Box or Amazon’s S3 to gain strong security in the event the storage provider is compromised. Regulations like HIPAA and PCI (and good security hygiene) require that encryption keys be rotated periodically. The current schemes in use for rotating encryption keys are either infeasible or insecure as we discuss in this presentation. We describe attacks against the current scheme and present two new encryption schemes that improve the security of key rotation offering different security and performance trade-offs.