A cloud storage system stores data objects from different customers. Each customer has their own encryption key to encrypt the data objects for storage and the key is not shared. To deduplicate the data objects, a set of base fingerprints associated with a set of base data objects is stored. A first fingerprint associated with a data object from a customer is compared with a base fingerprint. The first and base fingerprints are generated by applying an identical fingerprinting algorithm to unencrypted versions of the data objects. If the fingerprints match, the first fingerprint is associated with a base data object corresponding to the matching base fingerprint, and the data object from the customer is not stored. If the fingerprints do not match, the data object from the customer is stored.