Patent ID: 8199911

Claim:
A method of performing data deduplication on an untrusted storage device, the method comprising: generating an encryption key for use in encrypting data, wherein the encryption key is based upon a hash of the data to be encrypted; generating an identifier for the data, based upon the hash of the data to be encrypted; detecting whether an encrypted copy of the data is already stored by a storage system, based upon the identifier, wherein the storage system comprises the untrusted storage device; selectively encrypting the data, based upon whether the encrypted copy of the data is already stored by the storage system, wherein the encrypting comprises selecting a sampled subset of the data by sampling the data, and applying a cryptographic hash function to the sampled subset; generating a catalog, wherein the catalog comprises the identifier, the encryption key, and a name associated with the data; and encrypting the catalog using a user-specific encryption key, wherein the encrypting produces an encrypted copy of the catalog.