An encrypted data storage system includes a storage system that is configured to store encrypted data, and a first client device that is coupled to the storage system. The first client device performs a hash operation on first data to generate a Data Encryption Key (DEK), and uses the DEK to perform a data encryption operation on the first data to generate encrypted first data. The first client device then uses a first Key Encryption Key (KEK) to perform a first key encryption operation on the DEK to generate a first encrypted DEK, associates the first encrypted DEK with the encrypted first data, and transmits the encrypted first data to the storage system for storage.