A request to perform one or more operations using a second key that is inaccessible to a customer of a computing resource service provider is received from the customer, with the request including information that enables the computing resource service provider to select the second key from other keys managed on behalf of customers of the computing resource service provider. A first key, and in addition to the first key, an encrypted first key, is provided to the customer. Data encrypted under the first key is received from the customer. The encrypted first key and the data encrypted under the first key is caused to be stored in persistent storage, such that accessing the data, in plaintext form, from the persistent storage requires use of both a third key and the second key that is inaccessible to the customer.