In response to determining that an encryption operation request includes no indication of a cryptographic key, an encryption service module performs an encryption operation using a current cryptographic key retrieved by the encryption service module, and creates and stores an encrypted data object that includes the resulting ciphertext and a key identifier that uniquely identifies the cryptographic key and the associated cryptographic algorithm used to perform the encryption. A subsequent decryption operation request to the encryption service module that indicates the encrypted data object is processed by retrieving the cryptographic key and identifying the associated cryptographic using the key identifier contained in the encrypted data object. The encrypted data object may also include an initialization vector used to generate the ciphertext contained in the encrypted data object, as well as an integrity check value generated across the ciphertext and initialization vector.