Threshold encryption and decryption using a key management service in a provider network

Abstract

Techniques for using a key management service to provide K of N threshold encryption and decryption in a provider network. The techniques encompass a K of N threshold encryption process and a K of N threshold decryption process. The encryption process can include encrypting a plaintext datum using a first key to produce a ciphertext datum. A secret sharing algorithm can be used to produce N plaintext shares of the first key. The N plaintext shares can be encrypted using N public keys of N asymmetric key pairs to produce N ciphertext shares. The decryption process can include recovering K plaintext shares from K of the N ciphertext shares. The K ciphertext shares can be recovered by the key management service decrypting the K ciphertext shares using K private keys of the N asymmetric key pairs to recover the K plaintext shares. The first key can be recovered from the K plaintext shares. The plaintext datum can be recovered by decrypting the ciphertext datum using the recovered first key.