Encryption of data across an environment, such as a shared resource environment, can be updated using keys generated using one or more revocable stream cipher algorithms. Data stored in the environment can be encrypted under a first key, or other such secret. When it is desired to update the encryption, a second key can be generated under which the data is to be re-encrypted. Instead of distributing the second key, a revocable stream cipher generator can generate an intermediate key based on the first and second keys, that when processed with the first key will produce the second key. Such an approach enables data to be re-encrypted under the second key without distributing the second key. Further, the unencrypted data will not be exposed in the process. In some embodiments, the re-encryption can be performed on an as-needed basis in order to reduce processing requirements.