Encryption systems and methods for identifying and coalescing identical objects encrypted with different keys

• US 6,983,365 B1
• Filed: 05/05/2000
• Issued: 01/03/2006
• Est. Priority Date: 05/05/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Theimer, Marvin M., Bolosky, William J., Douceur, John R.
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): HOFFMAN, BRANDON S
• Application Number:
  US09/565,821
• Time in Patent Office: 2,069 Days
• Field of Search: 713/181, 713/165, 713/167, 713/193, 713/161, 713/185, 713/201, 380/37, 380/277, 380/44, 707/204
• US Class Current: 713/165
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

Cryptographic protocols and methods of employing the same are described. The described protocols advantageously enable two or more identical encryptable objects that are coded for encryption with different keys to be identified as identical without access to either the unencrypted objects or the keys that are used in the encryption process. Additionally, the protocols enable two or more identical encryptable objects to be processed with different encryption keys, yet be stored in a manner so that the total required storage space is proportional to the space that is required to store a single encryptable object, plus a constant amount for each distinct encryption key. In various embodiments, the encryptable objects comprise files and the cryptographic protocols enable encrypted files to be used in connection with single instance store (SIS) systems.

Claims

1. An encryption method comprising:

computing a representation for each of two or more encryptable objects;

encrypting each of the encryptable objects using its own representation as an encryption key, said encrypting defining a plurality of cipher objects each of which corresponds to an encryptable object;

ascertaining from the cipher objects whether the corresponding encryptable objects are identical; and

further comprising;

encrypting each representation with a different key to provide a plurality of encrypted representations;

defining individual key identifiers;

associating each of the key identifiers with an individual key; and

building a plurality of ordered tuples, each of which comprises;

a single cipher object that represents all of the two or more encryptable objects;

at least one key identifier; and

at least one encrypted representation each of which being associated with a corresponding key identifier.

2. The encryption method of claim 1, wherein said computing of the representation comprises computing hashes of each of the two or more encryptable objects.

3. The encryption method of claim 1, wherein said computing of the representations comprises computing secure hashes of each of the two or more encryptable objects.

4. The encryption method of claim 1, wherein the two or more encryptable objects are identical.

5. The encryption method of claim 1, wherein said ascertaining comprises comparing only the single cipher objects for each of the ordered tuples.

6. The encryption method of claim 1 further comprising:

encrypting each representation using a one-way encryption function to provide a plurality of undecryptable encrypted representations; and

using the undecryptable encrypted representations to build said plurality of ordered tuples, each of the undecryptable encrypted representations comprising an element of an ordered tuple.

7. The encryption method of claim 6, wherein said ascertaining comprises comparing, for each of the ordered tuples:

the single cipher objects; and

the undecryptable encrypted representations.

8. One or more computer-readable media having computer-readable instructions thereon which, when executed by a computer, implement the method of claim 1.

9. A computer system programmed to implement the method of claim 1.

10. One or more computer-readable media having computer-readable instructions thereon which, when executed by a computer, cause the computer to:

compute hashes of each of a plurality of identical objects;

encrypt each of the identical objects with its hash;

encrypt each hash with a different key; and

form at least one ordered tuple each of which comprising;

a single encrypted object that represents all of the identical objects; and

a list that contains information about each of the different keys,

wherein the instructions cause the computer to;

form multiple ordered tuples; and

determine whether objects that correspond to the multiple ordered tuples appear to be identical by comparing at least the single encrypted objects for each ordered tuple.

11. The computer-readable media of claim 10, wherein the list contains at least one identifier that uniquely identifies a key.

12. The computer-readable media of claim 10, wherein the list contains at least one encrypted hash.

13. The computer-readable media of claim 10, wherein the list contains a plurality of order pairs, each ordered pair containing:

an identifier that identifies a key; and

an encrypted hash that was encrypted with the key that is identified by the identifier.

14. The computer-readable media of claim 10, wherein the instructions cause the computer to:

encrypt the hash with a one-way encryption function to provide an undecryptable encrypted hash; and

form at least one ordered tuple to contain the undecryptable encrypted hash.

15. The computer-readable media of claim 14, wherein the instructions cause the computer to:

form multiple ordered tuples; and

determine whether objects that correspond to the multiple ordered tuples appear to be identical by comparing the single encrypted objects and the undecryptable encrypted hashes for each ordered tuple.

16. The computer-readable media of claim 10, wherein the identical objects comprise files.

17. An encryption method comprising:

computing representations of each of two or more identical encryptable objects;

encrypting each of the encryptable objects with its own representation, said encrypting defining a plurality of cipher objects each of which corresponds to an encryptable object;

encrypting each representation with one of a plurality of keys to provide a plurality of encrypted representations;

defining key identifiers for each of the plurality of keys;

forming a plurality of ordered pairs, each of which comprising;

an encrypted representation; and

a key identifier associated with a key that encrypted the encrypted representation of the ordered pair;

associating the ordered pairs with a single cipher object to provide a convergent cipher object.

18. The encryption method of claim 17 further comprising storing the convergent cipher object as a representative of all of the encryptable objects.

19. The encryption method of claim 18, wherein the storage space that is necessary to store the convergent cipher object is proportional to the size of one of the encryptable objects plus a constant value times the number of keys.

20. The encryption method of claim 17, wherein said computing of the representation comprises computing a hash of the encryptable objects.

21. The encryption method of claim 17, wherein said computing of the representation comprises computing a secure hash of the encryptable objects.

22. The encryption method of claim 17, wherein said encrypting each representation comprises encrypting said representations with different keys.

23. The encryption method of claim 17 further comprising encrypting each representation with a one way encryption function to provide a plurality of undecryptable encrypted representations.

24. The encryption method of claim 23, wherein said associating comprises associating the undecryptable encrypted representations with said single cipher object to provide the convergent cipher object.

25. A computer system programmed to implement the method of claim 17.

26. One or more computer-readable media having computer-readable instructions thereon which, when executed by a computer, cause the computer to:

compute hashes of each of two or more identical encryptable objects;

encrypt each of the encryptable objects with its own hash, said encrypting defining a plurality of cipher objects each of which corresponds to an encryptable object;

encrypt each hash with one of a plurality of different keys to provide a plurality of encrypted hashes;

form a plurality of ordered pairs, each of which comprising;

an encrypted representation; and

a key identifier associated with a key that encrypted the encrypted representation of the ordered pair;

define key identifiers for each of the plurality of keys;

associate the ordered pairs with a single cipher object to provide a convergent cipher object.

27. The computer-readable media of claim 26, wherein the instructions cause the computer to:

encrypt each hash using a one way encryption function to provide a plurality of undecryptable encrypted hashes; and

associate each undecryptable encrypted hash with the single cipher object to provide the convergent cipher object.

28. The computer-readable media of claim 26, wherein the encryptable objects comprise files.

29. A file system encryption method comprising:

computing representations of two or more files;

encrypting each of the files with its own representation, said encrypting defining a plurality of cipher objects each of which corresponds to a file;

ascertaining from the cipher objects whether the corresponding files are identical; and

further comprising;

encrypting each representation with a different key to provide a plurality of encrypted representations;

defining individual key identifiers;

associating each of the key identifiers with an individual key; and

building a plurality of ordered tuples, each of which comprises;

a single cipher object that represents all of the two or more files;

at least one key identifier; and

at least one encrypted representation each of which being associated with a corresponding key identifier.

30. The file system encryption method of claim 29, wherein said computing of the representations comprises computing hashes of the two or more files.

31. The file system encryption method of claim 29, wherein said computing of the representations comprises computing secure hashes of the two or more files.

32. The file system encryption method of claim 29, wherein the two or more files are identical.

33. The file system encryption method of claim 29, wherein said ascertaining comprises comparing only the single cipher objects for each of the ordered tuples.

34. The file system encryption method of claim 29 further comprising:

encrypting each representation using a one-way encryption function to provide a plurality of undecryptable encrypted representations; and

using the undecryptable encrypted representations to build said plurality of ordered tuples, each of the undecryptable encrypted representations comprising an element of an ordered tuple.

35. The file system encryption method of claim 34, wherein said ascertaining comprises comparing, for each of the ordered tuples;

the single cipher objects; and

the undecryptable encrypted representations.

36. One or more computer-readable media having computer-readable instructions thereon which, when executed by a computer, implement the method of claim 29.

37. A computer system programmed to implement the method of claim 29.