A cryptography service allows for management of cryptographic keys in multiple environments. The service allows for specification of policies applicable to cryptographic keys, such as what cryptographic algorithms should be used in which contexts. In some contexts, the cryptography service, upon receiving a request for a key, provides a referral to another system to obtain the key.