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

• US 20040215962A1
• Filed: 05/26/2004
• Published: 10/28/2004
• Est. Priority Date: 05/05/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Theimer, Marvin M., Bolosky, William J., Douceur, John R.
• Granted Patent: US 7,437,555 B2
• Time in Patent Office: Days
• US Class Current: 713/167
• 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 object extraction method comprising:

defining an ordered tuple that comprises;

a single cipher object that corresponds to an encryptable object; and

a list of ordered pairs, each ordered pair comprising a key identifier that is associated with a key, and an encrypted representation that has been encrypted with the key;

comparing at least some of the key identifiers of the list with a key identifier for which a match is desired; and

in the event a match is found, forming a second ordered tuple that comprises the single cipher object, and the list that corresponds to the key identifier for which the match was found;

2. The object extraction method of claim 1, wherein the ordered tuple comprises an undecryptable encrypted representation, and said forming of the second ordered tuple comprises forming said second tuple to comprise the undecryptable encrypted representation.

3. The object extraction method of claim 1, wherein said encrypted representation comprises an encrypted hash of the encryptable object.

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

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

6. A data object embodied on a computer-readable medium comprising:

a single cipher object comprising an encryptable object that has been encrypted with a representation of the encryptable object; and

a list comprising at least one ordered pair, each ordered pair comprising;

a key identifier that is associated with a particular key; and

an encrypted representation that comprises the representation having been encrypted with the particular key that is associated with the key identifier.

7. The data object of claim 6, wherein the list comprises a plurality of ordered pairs, at least some of the ordered pairs corresponding to different keys.

8. The data object of claim 6, wherein the data object comprises an undecryptable encrypted representation that comprises the representation having been encrypted with a one-way encryption function.

9. The data object of claim 6, wherein the representation comprises a hash of the encryptable object.

10. A file system encryption method comprising:

computing representations of each of two or more identical 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;

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.

11. The file system encryption method of claim 10, further comprising storing the convergent cipher object as a representative of all of the files.

12. The file system encryption method of claim 11, wherein the storage space that is necessary to store the convergent cipher object is proportional to the size of one of the files plus a constant value times the number of keys.

13. The file system encryption method of claim 10, wherein said computing of the representation comprises computing a hash of the files.

14. The file system encryption method of claim 10 further comprising encrypting each representation with a one way encryption function to provide a plurality of undecryptable encrypted representations.

15. The file system encryption method of claim 14, wherein said associating comprises associating the undecryptable encrypted representations with said single cipher object.

16. A computer system programmed to implement the method of claim 10.

17. A file system file extraction method comprising:

defining an ordered tuple that comprises;

a single cipher object that corresponds to a file; and

a list of ordered pairs, each ordered pair comprising a key identifier that is associated with a key, and an encrypted representation that has been encrypted with the key;

comparing at least some of the key identifiers of the list with a key identifier for which a match is desired; and

in the event a match is found, forming a second ordered tuple that comprises the single cipher object, and the list that corresponds to the key identifier for which the match was found.

18. The file system file extraction method of claim 17, wherein the ordered tuple comprises an undecryptable encrypted representation, and said forming of the second ordered tuple comprises forming said second tuple to comprise the undecryptable encrypted representation.

19. The file system file extraction method of claim 17, wherein said encrypted representation comprises an encrypted hash of the file.

20. One or more computer-readable media comprising computer-readable instructions thereon which, when executed by a computer, implement the method of claim 17.

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