Exclusive encryption

• US 7,571,327 B2
• Filed: 11/10/2004
• Issued: 08/04/2009
• Est. Priority Date: 01/17/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R., Adya, Atul, Benaloh, Josh D., Yuval, Gideon A.
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): POLTORAK, PIOTR
• Application Number:
  US10/985,200
• Publication Number:
  US 20050066183A1
• Time in Patent Office: 1,728 Days
• Field of Search: 713/165, 713189-190
• US Class Current: 713/189
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload

Abstract

An exclusive encryption system is established using multiple computing devices. The exclusive encryption system allows for the exclusion of certain plaintext (e.g., by one of the computing devices) and ciphertext (e.g., by another of the computing devices) while at the same time maintaining the privacy created by the encryption (e.g., so the other computing device cannot see the plaintext). The exclusive encryption system may be implemented as part of a serverless distributed file system with directory entries (e.g., file names or folder names) being the plaintext, or alternatively as part of other systems.

Claims

1. A completely computer-implemented method comprising:

receiving an encrypted identifier;

checking a part of the encrypted identifier to verify, without decrypting the encrypted identifier, that the encrypted identifier is an encryption of an identifier that conforms to a specified syntax, wherein verifying that the encrypted identifier is an encryption of the identifier that conforms to the specified syntax comprises;

checking whether a first block of the encrypted identifier is zero;

determining that the encrypted identifier conforms to the syntax when the first block is not equal to zero; and

determining that the encrypted identifier does not conform to the syntax when the first block is equal to zero;

accessing one or more other encrypted identifiers that are each an encryption of an associated other identifier;

verifying, without decrypting the encrypted identifier, that the encrypted identifier is not an encryption that matches any of the associated other identifiers of the one or more other encrypted identifiers; and

determining, in the event that the verifying indicates that the encrypted identifier is an encryption of an identifier that conforms to the specified syntax and the verifying indicates that the encrypted identifier is not an encryption that matches any of the associated other identifiers, that the encrypted identifier is an encryption of a valid identifier,

wherein in the event the encrypted identifier is an encryption of a valid identifier, the encrypted identifier is processed, the processing comprising;

storing the encrypted identifier;

or

forwarding the encrypted identifier.

2. A method as recited in claim 1, wherein verifying that the encrypted identifier is not an encryption that matches any of the associated other identifiers of the one or more other encrypted identifiers comprises:

comparing the encrypted identifier to the one or more other encrypted identifiers; and

determining that the encrypted identifier is the same as one or more other encrypted identifiers if the comparing indicates that the encrypted identifier is equal to one of the other encrypted identifiers.

3. A method as recited in claim 2,

wherein the one or more other encrypted identifiers correspond to files that are stored in a same folder,

wherein a file corresponds to the encrypted identifier,

wherein the processing further comprises storing the file that corresponds to the encrypted identifier in the same folder.

4. One or more computer storage media having stored thereon a plurality of instructions that, when executed by one or more processors, causes the one or more processors to perform a method, the method comprising:

receiving an encrypted identifier;

checking a part of the encrypted identifier to verify, without decrypting the encrypted identifier, that the encrypted identifier is an encryption of an identifier that conforms to a specified syntax, wherein to verify that the encrypted identifier is an encryption of the identifier that conforms to the specified syntax comprises;

checking whether a first block of the encrypted identifier is zero;

determining that the encrypted identifier conforms to the syntax when the first block is not equal to zero; and

determining that the encrypted identifier does not conform to the syntax when the first block is equal to zero;

accessing one or more other encrypted identifiers that are each an encryption of an associated other identifier; and

verifying, without decrypting the encrypted identifier, that the encrypted identifier is not an encryption that matches any of the associated other identifiers of the one or more other encrypted identifiers;

processing the encrypted identifier based on the verifying, wherein the processing comprises;

storing the encrypted identifier;

forwarding the encrypted identifier;

or

determining that the encrypted identifier is invalid.

5. The method as recited in claim 4, wherein to verify that the encrypted identifier is not an encryption that matches any of the associated other identifiers of the one or more other encrypted identifiers is to:

compare the encrypted identifier to the one or more other encrypted identifiers; and

determine that the encrypted identifier is not the same as one or more other encrypted identifiers if the comparison indicates that the encrypted identifier is not equal to one of the other encrypted identifiers.

6. The method as recited in claim 5,

wherein the one or more other encrypted identifiers correspond to files that are stored in a same folder,

wherein a file corresponds to the encrypted identifier,

wherein the processing further comprises storing the file that corresponds with the encrypted identifier in the same folder.

7. A system comprising:

a memory;

a processor;

means for receiving an encrypted identifier;

means for checking a part of the encrypted identifier to verify, without decrypting the encrypted identifier, that the encrypted identifier is an encryption of an identifier that conforms to a specific syntax, wherein the means for verifying that the encrypted identifier is an encryption of the identifier that conforms to the specific syntax comprises;

means for checking whether a first block of the encrypted identifier is zero; and

means for determining that the encrypted identifier conforms to the syntax when the first block is not equal to zero, and determining that the encrypted identifier does not conform to the syntax when the first block is equal to zero; and

means for verifying, without decrypting the encrypted identifier, that the encrypted identifier is not an encryption that matches any other identifier associated with one or more other encrypted identifiers;

means for processing the encrypted identifier based on the verifying.

8. A system as recited in claim 7,

wherein the means for verifying that the encrypted identifier is not an encryption that matches any other identifier of one or more other encrypted identifiers comprises:

means for comparing the encrypted identifier to the one or more other encrypted identifiers; and

means for determining that the encrypted identifier is not the same as one or more other encrypted identifiers if the means for comparing indicates that the encrypted identifier is not equal to one of the other encrypted identifiers.

9. A system as recited in claim 8,

wherein the one or more other encrypted identifiers correspond to files that are stored in a same folder,

wherein a file corresponds to the encrypted identifier,

wherein the means for processing the encrypted identifier comprises storing the file that corresponds with the encrypted identifier in the same folder.

10. A system comprising:

a processor;

a memory;

a plurality of encrypted identifiers;

a syntax verifier to determine whether a newly received encrypted identifier is an encryption of a legal name without decrypting the newly received encrypted identifier, wherein the determination comprises;

checking a part of the newly received encrypted identifier;

checking whether a first block of the newly received encrypted identifier is zero;

determining that the newly received encrypted identifier is an encryption of a legal name when the first block is not equal to zero; and

determining that the newly received encrypted identifier is not an encryption of a legal name when the first block is equal to zero; and

a duplication identifier to determine whether the newly received encrypted identifier is an encryption of the same name as any of the plurality of encrypted identifiers without decrypting either the newly received encrypted identifier or any of the plurality of encrypted identifiers,

whereby the newly received encrypted identifier is processed based on the determination made by the syntax verifier and the determination made by the duplication identifier.

11. A system as recited in claim 10, wherein the duplication identifier is to:

compare the newly received encrypted identifier to the plurality of encrypted identifiers; and

determine that the newly received encrypted identifier is not the same as one of the plurality of encrypted identifiers if the comparison indicates that the newly received encrypted identifier is not equal to one of the plurality of encrypted identifiers.

12. A system as recited in claim 11,

wherein the plurality of encrypted identifiers correspond to files that are stored in a same folder,

wherein a file corresponds to the newly received encrypted identifier,

wherein the processing of the newly received encrypted identifier comprises storing the file that corresponds with the newly received encrypted identifier in the same folder.

13. A method implemented completely by an electronic computing device, the method comprising:

receiving a directory entry that is encrypted, wherein the electronic computing device does not have a key needed for decrypting the encrypted directory entry;

checking a part of the encrypted directory entry to verify, without decrypting the encrypted directory entry, that the encrypted directory entry is an encryption of a name that is a syntactically legal name, wherein verifying that the encrypted directory entry is an encryption of a syntactically legal name comprises;

checking whether a first block of the directory entry is zero;

determining that the name is syntactically legal if the first block is not equal to zero; and

determining that the name is not syntactically legal if the first block is equal to zero;

accessing one or more other encrypted directory entries that are each an encryption of an associated other name;

verifying, without decrypting the encrypted directory entry, that the encrypted directory entry is not an encryption that matches any of the associated other names of any of the other encrypted directory entries maintained by the electronic computing device; and

processing the encrypted directory entry based on the verifying,

wherein the electronic computing device comprises a memory and a processor.

14. A method as recited in claim 13, wherein verifying that the encrypted directory entry is not an encryption that matches any of the associated other names of any of the other encrypted directory entries maintained by the electronic computing device further comprises:

determining, via the accessing of the one or more other encrypted directory entries, that each of the associated other name maps to a file stored in a same directory; and

verifying that the encrypted directory entry is not an encryption of a name that maps to a file that is already stored in the same directory, wherein in the event that the encrypted directory entry is not an encryption of a name that maps to a file that is already stored in the same directory, the file that is mapped to the name that the encrypted directory entry is an encryption of is stored in the same directory.

15. A method as recited in claim 13, wherein verifying that the encrypted directory entry is not an encryption that matches any of the associated other names of any of the other encrypted directory entries maintained by the electronic computing device comprises:

comparing the encrypted directory entry to other directory entries maintained by the electronic computing device; and

determining that the encrypted directory entry is the same as any other encrypted directory entry maintained by the electronic computing device if the comparing indicates that the encrypted directory entry is equal to any other encrypted directory entry maintained by the electronic computing device.

16. One or more computer storage media having stored thereon a plurality of instructions that, when executed by one or more processors of a computing device, causes the one or more processors to:

receive a directory entry that is encrypted, wherein the computing device does not have a key needed for decrypting the directory entry;

check a part of the encrypted directory entry to verify that the directory entry is an encryption of a name that is a syntactically legal name, wherein to verify that the directory entry is an encryption of a syntactically legal name is to;

check whether a first block of the directory entry is zero;

determine that the name is syntactically legal if the first block is not equal to zero; and

determine that the name is not syntactically legal if the first block is equal to zero;

verify that the directory entry is not an encryption of a same name as any other directory entry maintained by the computing device; and

process the directory entry based on the verifying.

17. One or more computer readable media as recited in claim 16, wherein the verification that the directory entry is an encryption of a syntactically legal name and the verification that the directory entry is not an encryption of the same name as any other directory entry maintained by the computing device is made without decrypting the directory entry.

18. One or more computer readable media as recited in claim 16,

wherein to verify that the directory entry is not an encryption of the same name as any other directory entry maintained by the computing device is to verify that the directory entry is not an encryption of the same name as any other directory entry corresponding to a file stored in a same directory as a file corresponding to the directory entry,

wherein in the event the directory entry is not an encryption of the same name as any other directory entry corresponding to a file stored in a same directory, the file corresponding to the directory entry is stored in the same directory.

19. One or more computer readable media as recited in claim 16, wherein to verify that the directory entry is not an encryption of the same name as any other directory entry maintained by the computer device is to:

compare the directory entry to other directory entries maintained by the computing device; and

determine that the directory entry is the same as any other directory entry maintained by the computing device if the comparing indicates that the directory entry is equal to any other directory entry maintained by the computing device.

20. A system comprising:

a processor;

a memory;

a plurality of encrypted directory entries;

a syntax verifier to determine whether a new encrypted directory entry is an encryption of a legal name without decrypting the new encrypted directory entry, wherein the determination comprises;

checking a part of the new encrypted directory entry;

checking whether a first block of the new encrypted directory entry is zero;

determining that the new encrypted directory entry is an encryption of a legal name when the first block is not equal to zero; and

determining that the new encrypted directory entry is not an encryption of a legal name when the first block is equal to zero; and

a duplication identifier to determine whether the new encrypted directory entry is an encryption of the same name as any of the plurality of encrypted directory entries without decrypting either the new encrypted directory entry or any of the plurality of encrypted directory entries,

whereby the new encrypted directory entry is processed based on the determination made by the syntax verifier and the determination made by the duplication identifier.

21. A system as recited in claim 20, wherein the duplication identifier is to:

compare the new encrypted directory entry to the plurality of encrypted directory entries; and

determine that the new encrypted directory entry is the same as any of the plurality of encrypted directory entries if the comparison indicates that the new encrypted directory entry is equal to one of the plurality of encrypted directory entries.

22. A system as recited in claim 21,

wherein the plurality of encrypted directory entries correspond to files that are stored in a same folder,

wherein a file corresponds to the new encrypted directory entry,

wherein the processing of the new encrypted directory entry comprises storing the file that corresponds to the new encrypted directory entry in the same folder.