Cloud computing offers many advantages as flexibility or resource-efficiency and can significantly reduce costs. However, when sensitive medical data is outsourced to a cloud provider, classified records can leak. To protect the patients and application providers from a privacy breach data must be encrypted before it is uploaded. In this work, we present a distributed key management scheme that handles user-specific keys in a single-tenant scenario. The underlying database is encrypted and the secret key is only reconstructed temporarily in memory. Our scheme distributes shares of the key to the different entities. We address bootstrapping, key recovery, the attacker model and the resulting security guarantees.