Deduplication of encrypted data using multiple keys includes responding to a request to store a predetermined set of data in an electronic data store by receiving a hash corresponding to the predetermined set of data, receiving encrypted data generated by encrypting the predetermined set of data using an encryption key, and receiving a key index corresponding to the encryption key. The hash may be determined to match a previously stored hash, the previously stored hash indicating that a previously encrypted version of the predetermined set of data is stored at a physical location in the electronic data store. Based on determining that the hash matches a previously stored hash, the hash, encrypted data, and key index are discarded.