Techniques are provided to implement a key management service using key proxies and generational indexes, which allows client applications to obtain data cryptographic services without having to utilize or otherwise have knowledge of cryptographic keys. For example, a key management service receives a data decryption request from a client application. The data decryption request includes encrypted data and a key proxy assigned to the client application. The key management service determines a generational index associated with the encrypted data. The generational index identifies a generation of a cryptographic key which is associated with the key proxy and which was used to create the encrypted data. The key management service obtains a cryptographic key from a secure key vault, which is mapped to the received key proxy and the determined generational index, decrypts the encrypted data using the obtained cryptographic key, and sends the decrypted data to the client application.