Exclusive encryption

• US 20050066183A1
• Filed: 11/10/2004
• Published: 03/24/2005
• Est. Priority Date: 01/17/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R., Adya, Atul, Benaloh, Josh D., Yuval, Gideon A.
• Granted Patent: US 7,571,327 B2
• Time in Patent Office: Days
• US Class Current: 713/190
• 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 method comprising:

receiving an encrypted identifier;

verifying, without decrypting the encrypted identifier, that the encrypted identifier is an encryption of another identifier that conforms to a syntax; and

verifying, without decrypting the encrypted identifier, that the encrypted identifier is not an encryption of the same other identifier as one or more other encrypted identifiers.

2. A method as recited in claim 1, wherein verifying that the encrypted identifier is an encryption of another identifier that conforms to the syntax comprises:

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

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

determining that the encrypted identifier does not conform to the syntax if the first block is equal to zero.

3. A method as recited in claim 1, wherein verifying that the encrypted identifier is not an encryption of the same other identifier as 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.

4. A method as recited in claim 3, wherein the one or more other encrypted identifiers correspond to files that are stored in a same folder as a file corresponding to the encrypted identifier is to be stored in.

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

receive an encrypted identifier;

verify, without decrypting the encrypted identifier, that the encrypted identifier is an encryption of another identifier that conforms to a syntax; and

verify, without decrypting the encrypted identifier, that the encrypted identifier is not an encryption of the same other identifier as one or more other encrypted identifiers.

6. One or more computer readable media as recited in claim 5, wherein to verify that the encrypted identifier is an encryption of another identifier that conforms to the syntax is to:

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

determine that the encrypted identifier conforms to the syntax if the first block is not equal to zero; and

determine that the encrypted identifier does not conform to the syntax if the first block is equal to zero.

7. One or more computer readable media as recited in claim 5, wherein to verify that the encrypted identifier is not an encryption of the same other identifier as 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 the same as one or more other encrypted identifiers if the comparison indicates that the encrypted identifier is equal to one of the other encrypted identifiers.

8. One or more computer readable media as recited in claim 7, wherein the one or more other encrypted identifiers correspond to files that are stored in a same folder as a file corresponding to the encrypted identifier is to be stored in.

9. A system comprising:

means for receiving an encrypted identifier;

means for verifying, without decrypting the encrypted identifier, that the encrypted identifier is an encryption of another identifier that conforms to a syntax; and

means for verifying, without decrypting the encrypted identifier, that the encrypted identifier is not an encryption of the same other identifier as one or more other encrypted identifiers.

10. A system as recited in claim 9, wherein the means for verifying that the encrypted identifier is an encryption of another identifier that conforms to the 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 if the first block is not equal to zero, and determining that the encrypted identifier does not conform to the syntax if the first block is equal to zero.

11. A system as recited in claim 9, wherein the means for verifying that the encrypted identifier is not an encryption of the same other identifier as 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 the same as one or more other encrypted identifiers if the means for comparing indicates that the encrypted identifier is equal to one of the other encrypted identifiers.

12. A system as recited in claim 11, wherein the one or more other encrypted identifiers correspond to files that are stored in a same folder as a file corresponding to the encrypted identifier is to be stored in.

13. A system comprising:

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; 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.

14. A system as recited in claim 13, wherein the syntax verifier is to:

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

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

determine that the newly received encrypted identifier is not an encryption of a legal name if the first block is equal to zero.

15. A system as recited in claim 13, 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 the same as one of the plurality of encrypted identifiers if the comparison indicates that the newly received encrypted identifier is equal to one of the plurality of encrypted identifiers.

16. A system as recited in claim 15, wherein the plurality of encrypted identifiers correspond to files that are stored in a same folder as a file corresponding to the newly received encrypted identifier is to be stored in.

17. A method implemented at a computing device, the method comprising:

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

verifying that the directory entry is an encryption of a syntactically legal name; and

verifying that the directory entry is not an encryption of the same name as any other directory entry maintained by the computing device.

18. A method as recited in claim 17, further comprising:

verifying that the directory entry is an encryption of a syntactically legal name and verifying that the directory entry is not an encryption of the same name as any other directory entry maintained by the computing device without decrypting the directory entry.

19. A method as recited in claim 17, wherein verifying that the directory entry is not an encryption of the same name as any other directory entry maintained by the computing device further comprises verifying 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 is to be stored in.

20. A method as recited in claim 17, wherein verifying that the 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.

21. A method as recited in claim 17, wherein verifying that the directory entry is not an encryption of the same name as any other directory entry maintained by the computer device comprises:

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

determining 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.

22. One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors, 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;

verify that the directory entry is an encryption of a syntactically legal name; and

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

23. One or more computer readable media as recited in claim 22, 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.

24. One or more computer readable media as recited in claim 22, 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 is to be stored in.

25. One or more computer readable media as recited in claim 22, 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.

26. One or more computer readable media as recited in claim 22, 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.

27. A system comprising:

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; 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.

28. A system as recited in claim 27, wherein the syntax verifier is to:

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

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

determine that the new encrypted directory entry is not an encryption of a legal name if the first block is equal to zero.

29. A system as recited in claim 27, 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.

30. A system as recited in claim 29, wherein the plurality of encrypted directory entries correspond to files that are stored in a same folder as a file corresponding to the new encrypted directory entry is to be stored in.