Exclusive Encryption

• US 20060107048A1
• Filed: 12/19/2005
• Published: 05/18/2006
• 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,475,258 B2
• Time in Patent Office: Days
• US Class Current: 713/168
• 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. One or more computer-readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a computer, causes the one or more processors to perform acts comprising:

receiving an identifier;

generating, based on the identifier, a mapped identifier;

encoding the mapped identifier, wherein encoding the mapped identifier comprises;

reversing an order of characters in the mapped identifier;

removing, from the reversed mapped identifier, all trailing characters of a particular type;

initializing the encoded identifier with a string of one bits equal in number to a number of trailing characters removed from the reversed identifier followed by a zero bit;

selecting a first character from the reversed identifier;

encoding the first character using a first coding table;

adding, to the encoded identifier, a series of zero bits followed by the encoded first character;

for each additional character in the reversed identifier,

selecting a next character in the reversed identifier,

encoding the next character using a second coding table,

adding, to the encoded identifier, a series of zero bits followed by the encoded next character; and

removing any trailing zero bits and the one bit preceding the trailing zero bits from the encoded identifier; and

encrypting the encoded mapped identifier.

2. One or more computer-readable media as recited in claim 1, wherein the identifier comprises one of:

a file name, a folder name, and a directory name.

3. One or more computer-readable media as recited in claim 1, the acts further comprising:

generating, based on the mapped identifier, a decasified identifier and corresponding case information;

wherein the encoding comprises encoding the decasified identifier; and

wherein the encrypting comprises encrypting both the encoded decasified identifier and the case information.

4. One or more computer-readable media as recited in claim 1, wherein the generating comprises generating the mapped identifier only if the received identifier is syntactically legal.

5. One or more computer-readable media as recited in claim 1, wherein generating the mapped identifier comprises:

checking whether the identifier is equal to one of a plurality of illegal identifiers;

if the identifier is not equal to one of the plurality of illegal identifiers, then checking whether the identifier is equal to one of the plurality of illegal identifiers followed by one or more particular characters;

if the identifier is not equal to one of the plurality of illegal identifiers followed by one or more particular characters, then using the identifier as the mapped identifier; and

if the identifier is equal to one of the plurality of illegal identifiers followed by one or more particular characters, then using as the mapped identifier the identifier with one of the particular characters removed.

6. One or more computer-readable media as recited in claim 1, wherein each coding in the first coding table is the same as a corresponding coding in the second coding table, but the second coding table codes additional characters not coded by the first coding table.

7. One or more computer-readable media as recited in claim 1, wherein the encrypting comprises encrypting the encoded mapped identifier to generate, is using a block cipher, a ciphertext having a fixed size.

8. A computer comprising:

a processor;

a computer storage media, coupled to the processor, to store instructions that, when executed by the processor, cause the processor to perform acts comprising;

receiving an identifier;

generating, based on the identifier, a mapped identifier;

encoding the mapped identifier, wherein encoding the mapped identifier comprises;

reversing an order of characters in the mapped identifier;

removing, from the reversed mapped identifier, all trailing characters of a particular type;

initializing the encoded identifier with a string of one bits equal in number to a number of trailing characters removed from the reversed identifier followed by a zero bit;

selecting a first character from the reversed identifier;

encoding the first character using a first coding table;

adding, to the encoded identifier, a series of zero bits followed by the encoded first character;

for each additional character in the reversed identifier,

selecting a next character in the reversed identifier,

encoding the next character using a second coding table,

adding, to the encoded identifier, a series of zero bits followed by the encoded next character; and

removing any trailing zero bits and the one bit preceding the trailing zero bits from the encoded identifier; and

encrypting the encoded mapped identifier.

9. A computer as recited in claim 8, the acts further comprising:

generating, based on the mapped identifier, a decasified identifier and corresponding case information;

wherein the encoding comprises encoding the decasified identifier; and

wherein the encrypting comprises encrypting both the encoded decasified identifier and the case information.

10. A computer as recited in claim 8, wherein the encoding comprises encoding the mapped identifier only if the received identifier is syntactically legal.

11. A computer as recited in claim 8, wherein generating the mapped identifier comprises:

checking whether the identifier is equal to one of a plurality of illegal identifiers;

if the identifier is not equal to one of the plurality of illegal identifiers, then checking whether the identifier is equal to one of the plurality of illegal identifiers followed by one or more particular characters;

if the identifier is not equal to one of the plurality of illegal identifiers followed by one or more particular characters, then using the identifier as the mapped identifier; and

if the identifier is equal to one of the plurality of illegal identifiers followed by one or more particular characters, then using as the mapped identifier the identifier with one of the particular characters removed.

12. A computer as recited in claim 8, wherein the characters of a particular type are the characters that are coded to zero using the first coding table.

13. A computer as recited in claim 8, wherein the first coding table and the second coding table are Huffman coding tables.

14. A computer as recited in claim 8, wherein encrypting the encoded mapped identifier comprises using a block cipher to encrypt the encoded identifier.

15. A system comprising:

means for receiving an identifier;

means for generating, based on the identifier, a mapped identifier;

means for encoding the mapped identifier, wherein the means for encoding the mapped identifier comprises;

means for reversing an order of characters in the mapped identifier;

means for removing, from the reversed mapped identifier, all trailing characters of a particular type;

means for initializing the encoded identifier with a string of one bits equal in number to a number of trailing characters removed from the reversed identifier followed by a zero bit;

means for selecting a first character from the reversed identifier;

means for encoding the first character using a first coding table;

a means for adding, to the encoded identifier, a series of zero bits followed by the encoded first character;

means for, for each additional character in the reversed identifier,

selecting a next character in the reversed identifiers

encoding the next character using a second coding table,

adding, to the encoded identifier, a series of zero bits

followed by the encoded next character; and

means for removing any trailing zero bits and the one bit preceding the trailing zero bits from the encoded identifier; and

means for encrypting the encoded mapped identifier.

16. A system as recited in claim 15, further comprising:

means for generating, based on the mapped identifier, a decasified identifier and corresponding case information;

wherein the means for encoding comprises means for encoding the decasified identifier; and

wherein the means for encrypting comprises means for encrypting both the encoded decasified identifier and the case information.

17. A system as recited in claim 16, wherein the means for generating the decasified identifier and corresponding case information comprises:

means for, for each character that has both an upper-case and a lower-case form, storing the character in upper-case form and recording in the case information whether the character was in upper-case form or lower-case form.

18. A system as recited in claim 15, wherein the means for generating the mapped identifier comprises:

means for checking whether the identifier is equal to one of a plurality of illegal identifiers;

means for, if the identifier is not equal to one of the plurality of illegal identifiers, checking whether the identifier is equal to one of the plurality of illegal identifiers followed by one or more particular characters;

means for, if the identifier is not equal to one of the plurality of illegal identifiers followed by one or more particular characters, using the identifier as the mapped identifier; and

means for, if the identifier is equal to one of the plurality of illegal identifiers followed by one or more particular characters, using as the mapped identifier the identifier with one of the particular characters removed.

19. A system as recited in claim 15, wherein for the first character and each additional character, the means for encoding comprises means for encoding the character only if a set of leading bits of the character are zero, and further comprising means for adding the character to the encoded identifier if the set of leading bits of the character are not zero.

20. A system as recited in claim 15, wherein the means for encrypting the encoded mapped identifier comprises means for using cipher block chaining to encrypt the encoded identifier.