Systems and methods are provided for encrypting data at a customer for storage at a hosted service provider. In addition to the data being encrypted by the client, the secret encryption key used to encrypt the data is also encrypted. Both the encrypted data and the encrypted secret encryption key are transmitted to the service provider who may further encrypt the data with another encryption key and who stores the further encrypted data, the encrypted secret encryption key and the another encryption key.