Disclosed herein are systems, methods, and non-transitory computer-readable storage media for initiating a backup, backing up encrypted data, and restoring backed up encrypted data. The method for initiating a backup includes sending a backup secret to a backup device having an encrypted file system, receiving from the backup device a backup ticket created based on the backup secret, and storing the backup ticket. The method for backing up encrypted data includes receiving a backup ticket and a backup secret, retrieving an escrow key bag containing protection class keys, decrypting the protection class keys with the backup ticket, generating a backup key bag containing new protection class keys, selecting a set of encrypted files to back up, decrypting the file encryption keys with corresponding decrypted protection class keys, re-encrypting the file encryption keys with new protection class keys, and transferring the selected encrypted files, the backup key bag, and metadata.