Server-side encrypted pattern matching
AssigneeMicrosoft Corporation
InventorsMelissa E. Chase, Emily H. Shen
Life of this patent
Estimating the term…
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.
Claims20
A computer-readable device storing computer-executable instructions that, when executed by the computer-readable device, 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;
- generating an encrypted suffix tree based on the data string;
- constructing an encrypted dictionary that includes information on edges of the 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, the encrypted suffix tree, and the encrypted data string, wherein each encrypted entry in the encrypted dictionary corresponds to a respective edge of the encrypted suffix tree.
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.
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 and the encrypted suffix tree to locate encrypted entries in the encrypted dictionary that correspond to label keys of a plurality of symbols in the encrypted query token.
Dependencies are inferred from the claim text.