Server-side Encrypted Pattern Matching

• US 20120159180A1
• Filed: 12/17/2010
• Published: 06/21/2012
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chase, Melissa E., Shen, Emily H.
• Granted Patent: US 8,429,421 B2
• Time in Patent Office: Days
• US Class Current: 713/183
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: H04L 2209/046 of operations, operands or results of the operations
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds

Abstract

Server-side encrypted pattern matching may minimize the risk of data theft due to server breach and/or unauthorized data access. In various implementations, a server for performing the server-side encrypted pattern matching may include an interface component to receive an encrypted query token. The server may further include a query component to find a match for the encrypted query token in the encrypted data string. The query component may find such a match without decrypting the encrypted data string and the encrypted query token by using an encrypted dictionary that includes information on the edges of the encrypted suffix tree.

Claims

1. A computer-readable medium storing computer-executable instructions that, when executed, cause one or more processors to perform operations comprising:

receiving a data string that includes a plurality of symbols;

generating a secret that includes one or more random strings and a symmetric key;

constructing an encrypted dictionary that includes information on the edges of an encrypted suffix tree for the data string based on the one or more random strings using an integer comparison encryption scheme and a symmetric key scheme;

encrypting each of the plurality of symbols symbol-wise based on the symmetric key using a symmetric encryption scheme to produce an encrypted data string; and

outputting the encrypted dictionary and the encrypted data string.

2. The computer-readable medium of claim 1, further comprising propagating the encrypted dictionary with dummy entries to obfuscate information regarding number of edges in the encrypted suffix tree.

3. The computer-readable medium of claim 2, wherein the propagating includes creating a dummy entry by choosing random strings R₁, R₂, R₃, R₄ and storing (R₂, ε

_comp·

Enc (R₃, R₄,

     1) with search key R₁, in which ε

_comp·

Enc is an encryption algorithm of the integer comparison encryption scheme.

4. The computer-readable medium of claim 2, wherein |{e}| is a number of edges in the encrypted suffix tree, and 2n−

|{e}| is a number of the dummy entries, so that the encryption dictionary contains 2n total number of entries.

5. The computer-readable medium of claim 1, further comprising generating an encrypted query token that includes a query pattern string for comparison with the encrypted data string.

6. The computer-readable medium of claim 5, wherein the generating the encrypted query token is defined as Token(K,p) that constructs a token for a pattern p=p₁ . . . p_m by outputting

T=({T_1,i=F_K1(p₁ . . . p_i), T_2,i=F_K2(p₁ . . . p_i), T_3,i=ε

_comp·

Token(F_K3(p₁ . . . p_i),m−

i+1)}_i=1^m))

in which K₂ and K₃ are random strings, and ε

_comp·

Token is a tokenization algorithm of the integer comparison encryption scheme.

7. The computer-readable medium of claim 5, further comprising:

decrypting a candidate encrypted substring into a decrypted substring, the candidate encrypted substring being extracted from the encrypted data string using the encrypted query token;

verifying the encrypted substring is identical to the query pattern string;

presenting an indication that no query result is found when the decrypted substring is not identical to the query pattern string; and

presenting the decrypted substring when the decrypted substring is identical to the query pattern string.

8. The computer-readable medium of claim 1, wherein the integer comparison encryption scheme is a CQA2-secure scheme.

9. The computer-readable medium of claim 1, wherein each encrypted entry in the encrypted dictionary corresponds to a respective edge of the encrypted suffix tree, each encrypted entry storing a search key for locating the encrypted entry, and a first value for an encryption of a length of a prefix through the edge, and a second value for the encryption of an index position of a first occurrence of a corresponding substring to the edge.

10. The computer-readable medium of claim 9, wherein the search key is stored as F_K1(p_e∥

e₁), in which K₁ is random string, p_e denote a string on a path from a root to an edge e, F_K1 is a pseudorandom function.

11. The computer-readable medium of claim 9, wherein the first value and the second value are stored as ((|p_e∥

e|+1)⊕

F_K2(p_e∥

e₁),ε

_comp·

Enc(F_K3(p_e∥

e₁),ind_e,|e|)), in which K₂ and K₃ are random strings, p_e denotes a string on a path from a root to an edge e, F_K2 and F_K3 are pseudorandom functions, ind_e denotes a start index in the data string of a first occurrence of a substring p_e∥

e, ε

_comp·

Enc is an encryption algorithm of the integer comparison encryption scheme.

12. A method, comprising:

receiving an encrypted query token from a client device that includes a query pattern string for comparison with an encrypted data string at one or more cloud servers;

parsing the encrypted query token to obtain label keys and secret keys;

parsing the encrypted data string into a plurality of symbols based on an encrypted dictionary;

locating encrypted records in the encrypted dictionary that corresponds to the label keys of the plurality of symbols in the encrypted query token using an encrypted suffix tree;

returning a candidate encrypted substring to the client device when a corresponding encrypted record for each of the label keys is located in the encrypted dictionary; and

returning an indication that no query result is found to the client device when a corresponding encrypted record for each of the label keys is not located in the encrypted dictionary.

13. The method of claim 12, where the locating the encrypted entries includes locating a next encrypted entry in the encrypted query token using information that is extracted from an encrypted record of the encrypted dictionary via one of the secret keys.

14. The method of claim 12, wherein each of the encrypted records include an index position in the encrypted data string that corresponds to each encrypted record and information for locating a next encrypted entry in the encrypted query token.

15. The method of claim 14, wherein the returning a candidate encrypted substring includes using an index position in the encrypted data string that corresponds to a first symbol in the plurality of symbols to extract the candidate encrypted substring from the encrypted data string.

16. The method of claim 12, wherein the encrypted suffix tree and the encrypted dictionary are generated for the encrypted data string based on one or more random strings using an integer comparison encryption scheme.

17. The method of claim 12, wherein the encrypted data string is produced from an unencrypted data string by encrypting each of the plurality of symbols symbol-wise based on a symmetric key using a symmetric encryption scheme.

18. The method of claim 12, wherein the encrypted dictionary includes dummy entries that obfuscate information regarding number of edges in the encrypted suffix tree.

19. A server, comprising:

one or more processors; and

a memory that includes components that are executable by the one or more processors, the components comprising;

an interface component to receive an encrypted query token from a client device that includes a query pattern string for comparison with an encrypted data string; and

a query component to find a match for the encrypted query token in the encrypted data string without decrypting the encrypted data string and the encrypted query token by using an encrypted dictionary that includes information on edges of an encrypted suffix tree.

20. The server of claim 19, wherein the query component is to find the match by locating encrypted entries in the encrypted dictionary that corresponds to label keys of a plurality of symbols in the encrypted query token, the query component to further return a candidate encrypted substring to the client device when a corresponding encrypted record for each of the label keys is located in the encrypted dictionary or return an indication that no query result is found to the client device when a corresponding encrypted record for each of the label keys is not located in the encrypted dictionary.