Key management providing high availability without key replication

A computer implemented method for obtaining a decrypted data encryption key from an instance of a key management system (KMS), the method comprising:

• receiving, at a first instance of a KMS, a request for a data encryption key (DEK) from a user, the first instance of the KMS configured with a first symmetric key, a first public-private key pair that is associated with the first instance of the KMS, and a second public key that is obtained from a different second instance of a KMS system via a key agreement scheme between the first and second instances of the KMS, the request including a blob, the blob comprising:
• a first instance of the DEK that has been previously encrypted with a symmetric key;
• and
• a second instance of the DEK that has been previously encrypted based on a negotiated key that is generated based on the key agreement scheme;
• and
• metadata;
• in response to determining that the blob was previously generated by the second instance of the KMS,
• generating the negotiated key based on the key agreement scheme;
• and
• performing a decryption of the second instance of the DEK that has been previously encrypted based on the negotiated key using the generated negotiated key to generate the decrypted DEK;
• and
• sending the decrypted DEK to the user.

A non-transitory computer readable storage medium for storing instructions that when executed by a computer processor cause the computer processor to perform steps for obtaining an encrypted data encryption key from an instance of a key management system (KMS), the steps comprising:

• receiving, at a first instance of a KMS, a request for a data encryption key (DEK) from a user, the first instance of the KMS configured with a first symmetric key, a first public-private key pair that is associated with the first instance of the KMS, and a second public key that is obtained from a different second instance of a KMS system to be used in a key agreement scheme between the first and second instances of the KMS;
• generating, at the first instance of the KMS, the DEK;
• generating, at the first instance of the KMS, a blob, wherein the blob comprises:
• a first instance of the generated DEK that is subsequently encrypted by the first symmetric key, and
• a second instance of the generated DEK that is subsequently encrypted by a negotiated key that is generated based on the key agreement scheme;
• and
• sending the blob to the user, wherein the first instance of the KMS is configured to decrypt the first instance of the generated DEK and the second instance of the KMS is configured to decrypt the second instance of the DEK.

A non-transitory computer readable storage medium for storing instructions that when executed by a computer processor cause the computer processor to perform steps for obtaining a decrypted data encryption key from an instance of a key management system (KMS), the steps comprising:

• receiving, at a first instance of a KMS, a request for a data encryption key (DEK) from a user, the first instance of the KMS configured with a first symmetric key, a first public-private key pair that is associated with the first instance of the KMS, and a second public key that is obtained from a different second instance of a KMS system via a key agreement scheme between the first and second instances of the KMS, the request including a blob, the blob comprising:
• a first instance of the DEK that has been previously encrypted with a symmetric key;
• and
• a second instance of the DEK that has been previously encrypted based on a negotiated key that is generated based on the key agreement scheme;
• and
• metadata;
• in response to determining that the blob was previously generated by the second instance of the KMS,
• generating the negotiated key based on the key agreement scheme;
• and
• performing a decryption of the second instance of the DEK that has been previously encrypted based on the negotiated key using the generated negotiated key to generate the decrypted DEK;
• and
• sending the decrypted DEK to the user.