What, if anything, can be used to provide confidentiality and authenticity guarantees for the storage keys used to store data in a key-value store?
To be clear what I mean by the storage keys - I mean the "key" in "key-value" store - I do not mean an encryption key.
The key-value store is something like Amazon S3 and is not trusted.
The storage keys have to be considered to be just as sensitive as the value objects.
But the storage keys are used to retrieve data from the store so they must also have a construction which is repeatable.
I'm using PHP and libsodium (via ParagonIE's Halite) to encrypt the data and ideally I would use the same library to construct the storage keys.
A related question mentions HMAC, but I don't know if that is useful.
Based on the answers given so far, the following could be a good solution:-
use \ParagonIE\Halite\Symmetric\Crypto.authenticate use \ParagonIE\Halite\Symmetric\Crypto.encrypt use \ParagonIE\Halite\Symmetric\Crypto.decrypt // put map.put( authenticate(storage_key, secret_signing_key), encrypt(concat(storage_key, value), secret_encryption_key) ) // get ciphertext = map.get( authenticate(storage_key, secret_signing_key) ) plaintext = decrypt(ciphertext, secret_encryption_key) // ensure that the key that was hashed equals the key that was encrypted assert(equals(storage_key, substring(ciphertext, 0, len(storage_key))) return substring(ciphertext, len(storage_key)) // just the data