Systems and methods for securely deduplicating data owned by multiple entities

• US 8,495,392 B1
• Filed: 09/02/2010
• Issued: 07/23/2013
• Est. Priority Date: 09/02/2010
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Bardale, Trimbak
• Primary Examiner(s): Shaw, Yin-Chen
• Assistant Examiner(s): SCHMIDT, KARI L
• Application Number:
  US12/874,640
• Time in Patent Office: 1,055 Days
• Field of Search: 713/153, 713/168, 713/189, 713/193, 711/136, 711/133, 711/118, 711/117, 711/161, 711/162
• US Class Current: 713/193
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 21/62 Protecting access to data via a platform, e.g. using keys or access control rules

Abstract

A computer-implemented method for securely deduplicating data owned by multiple entities may include 1) identifying a first data segment to store on a third-party storage system, 2) identifying a client-specific database for fingerprints of deduplicated data segments stored on the third-party storage system, 3) identifying a third-party database for fingerprints of deduplicated data segments stored on the third-party storage system, 4) generating a fingerprint based on the first data segment, 5) determining that the fingerprint is not identified in the client-specific fingerprint database, 6) determining that the fingerprint is not identified in the third-party fingerprint database, 7) encrypting the first data segment with a third-party public encryption key, and then 8) transmitting the encrypted first data segment to the third-party storage system. Various other methods, systems, and computer-readable media are also disclosed.

Claims

1. A computer-implemented method for securely deduplicating data owned by multiple entities, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising:

identifying a first data segment to store on a third-party storage system that provides storage for a plurality of clients;

identifying a client-specific database maintained by the third-party storage system that contains fingerprints of deduplicated data segments stored on the third-party storage system by a client within the plurality of clients, wherein each fingerprint stored within the client-specific database is encrypted with a client-specific encryption key that is unique to the client;

identifying a third-party database maintained by the third-party storage system that contains fingerprints of deduplicated data segments stored on the third-party storage system by the plurality of clients, wherein each fingerprint stored within the third-party database is encrypted with a third-party public encryption key that is different from the client-specific encryption key;

generating a fingerprint based on the first data segment;

determining, by generating a query using the client-specific encryption key, that the fingerprint is not identified in the client-specific fingerprint database;

determining, by generating a query using the third-party public encryption key, that the fingerprint is not identified in the third-party fingerprint database;

in response to determining that the fingerprint is not identified in both the client-specific fingerprint database and the third-party fingerprint database;

encrypting the first data segment with the third-party public encryption key;

transmitting the encrypted first data segment to the third-party storage system.

2. The method of claim 1, wherein determining, by generating the query using the client-specific encryption key, that the fingerprint is not identified in the client-specific fingerprint database comprises:

encrypting the fingerprint with the client-specific encryption key;

querying the client-specific fingerprint database with the client-specific-key encrypted fingerprint.

3. The method of claim 2, further comprising adding the client-specific-key encrypted fingerprint to the client-specific fingerprint database.

4. The method of claim 1, wherein determining, by generating the query using the third-party public encryption key, that the fingerprint is not identified in the third-party fingerprint database comprises:

encrypting the fingerprint with the third-party public encryption key;

querying the third-party fingerprint database with the third-party-key encrypted fingerprint.

5. The method of claim 4, further comprising adding the third-party-key encrypted fingerprint to the third-party fingerprint database.

6. The method of claim 1, further comprising:

identifying a second data segment to store on the third-party storage system;

generating a second fingerprint based on the second data segment;

determining that the second fingerprint is not identified in the client-specific fingerprint database but is identified in the third-party fingerprint database;

in response to determining that the second fingerprint is not identified in the client-specific fingerprint database but is identified in the third-party fingerprint database, incrementing a reference count for the second fingerprint within the third-party fingerprint database.

7. The method of claim 6, wherein determining that the second fingerprint is not identified in the client-specific fingerprint database comprises consulting a local cache that records the results of past queries to the client-specific fingerprint database.

8. The method of claim 1, further comprising:

identifying a third data segment to store on the third-party storage system;

generating a third fingerprint based on the third data segment;

determining that the third fingerprint is identified in the client-specific fingerprint database;

in response to determining that the third fingerprint is identified in the client-specific fingerprint database, incrementing a reference count for the third fingerprint within the client-specific fingerprint database.

9. The method of claim 1, further comprising:

identifying a file that includes the first data segment;

identifying a client-specific metadata database for associating deduplicated data segments with files;

adding a reference linking the file to the first data segment to the client-specific metadata database.

10. The method of claim 1, further comprising:

identifying a fourth data segment to retrieve from the third-party storage system;

retrieving an encrypted fingerprint of the fourth data segment from the client-specific fingerprint database;

decrypting the encrypted fingerprint of the fourth data segment with the client-specific encryption key;

identifying the fingerprint of the fourth data segment within the third-party fingerprint database;

using the fingerprint of the fourth data segment to retrieve the fourth data segment from the third-party storage system;

wherein the third-party storage system decrypts the fourth data segment using a third-party private encryption key corresponding to the third-party public encryption key prior to providing the fourth data segment to the computing device.

11. The method of claim 10, wherein retrieving the fourth data segment comprises:

obtaining a session key;

receiving an encrypted version of the fourth data segment that has been encrypted using the session key;

decrypting the encrypted version of the fourth data segment using the session key.

12. The method of claim 1, wherein identifying the client-specific database comprises providing credentials required to access the client-specific database to the third-party storage system.

13. The method of claim 1, wherein generating the fingerprint comprises generating the fingerprint using a hash function that is identical to a hash function used by all other clients within the plurality of clients.

14. A system for securely deduplicating data owned by multiple entities, the system comprising:

at least one processor configured to execute;

an identification module that;

identifies a first data segment to store on a third-party storage system that provides storage for a plurality of clients;

identifies a client-specific database maintained by the third-party storage system that contains fingerprints of deduplicated data segments stored on the third-party storage system by a client within the plurality of clients, wherein each fingerprint stored within the client-specific database is encrypted with a client-specific encryption key that is unique to the client;

identifies a third-party database maintained by the third-party storage system that contains fingerprints of deduplicated data segments stored on the third-party storage system by the plurality of clients, wherein each fingerprint stored within the third-party database is encrypted with a third-party public encryption key that is different from the client-specific encryption key;

a generation module that generates a fingerprint based on the first data segment;

a determination module that;

determines, by generating a query using the client-specific encryption key, that the fingerprint is not identified in the client-specific fingerprint database;

determines, by generating a query using the third-party public encryption key, that the fingerprint is not identified in the third-party fingerprint database;

an encryption module and a transmission module that, in response to the determination that the fingerprint is not identified in both the client-specific fingerprint database and the third-party fingerprint database;

encrypt the first data segment with a third-party public encryption key;

transmit the encrypted first data segment to the third-party storage system.

15. The system of claim 14, wherein the determination module determines, by generating the query using the client-specific encryption key, that the fingerprint is not identified in the client-specific fingerprint database by:

encrypting the fingerprint with the client-specific encryption key;

querying the client-specific fingerprint database with the client-specific-key encrypted fingerprint.

16. The system of claim 15, wherein the determination module further adds the client-specific-key encrypted fingerprint to the client-specific fingerprint database.

17. The system of claim 14, wherein the determination module determines, by generating the query using the third-party public encryption key, that the fingerprint is not identified in the third-party fingerprint database by:

encrypting the fingerprint with the third-party public encryption key;

querying the third-party fingerprint database with the third-party-key encrypted fingerprint.

18. The system of claim 17, wherein the determination module further adds the third-party-key encrypted fingerprint to the third-party fingerprint database.

19. The system of claim 14, wherein:

the identification module further identifies a second data segment to store on the third-party storage system;

the generation module further generates a second fingerprint based on the second data segment;

the determination module further;

determines that the second fingerprint is not identified in the client-specific fingerprint database but is identified in the third-party fingerprint database;

in response to determining that the second fingerprint is not identified in the client-specific fingerprint database but is identified in the third-party fingerprint database, increments a reference count for the second fingerprint within the third-party fingerprint database.

20. A non-transitory computer-readable-storage medium comprising one or more computer-executable instructions that, when executed by at least one processor of a computing device, cause the computing device to:

identify a first data segment to store on a third-party storage system that provides storage for a plurality of clients;

identify a client-specific database maintained by the third-party storage system that contains fingerprints of deduplicated data segments stored on the third-party storage system by a client within the plurality of clients, wherein each fingerprint stored within the client-specific database is encrypted with a client-specific encryption key that is unique to the client;

identify a third-party database maintained by the third-party storage system that contains fingerprints of deduplicated data segments stored on the third-party storage system by the plurality of clients, wherein each fingerprint stored within the third-party database is encrypted with a third-party public encryption key that is different from the client-specific encryption key;

generate a fingerprint based on the first data segment;

determine, by generating a query using the client-specific encryption key, that the fingerprint is not identified in the client-specific fingerprint database;

determine, by generating a query using the third-party public encryption key, that the fingerprint is not identified in the third-party fingerprint database;

in response to determining that the fingerprint is not identified in both the client-specific fingerprint database and the third-party fingerprint database;

encrypt the first data segment with the third-party public encryption key;

transmit the encrypted first data segment to the third-party storage system.