A computer-implemented method according to one embodiment includes using a first symmetric key to encrypt a second symmetric key. The first symmetric key is securely loaded inside a hardware security module (HSM) by a key management service before the encryption of the second symmetric key, and a cloud provider only has access to encrypted bits of the first symmetric key. Key data of a key-value-pair of the second symmetric key is used as additional authenticated data (AAD) for the encryption of the second symmetric key. The second symmetric key is used to encrypt value data of the key-value-pair. The method further includes storing the encrypted second symmetric key, the AAD used in the encryption of the second symmetric key, and tag bits created during the encryption of the second symmetric key, to thereafter use for verifying node related data.