A key protector for a storage volume is created by generating an intermediate key and protecting, based at least in part on a public/private key pair, the intermediate key. A volume master key for encrypting and decrypting one or more volume encryption keys that are used to encrypt the storage volume can be encrypted in different manners, including being encrypted based at least in part on the intermediate key. A key protector for the storage volume is stored that includes both the encrypted volume master key and information indicating how to obtain the intermediate key. Subsequently, the key protector can be accessed and, based at least in part on a private key of the entity associated with the key protector, the intermediate key can be decrypted. The intermediate key can then be used to decrypt the volume master key.