WILDCARD SEARCH IN ENCRYPTED TEXT USING ORDER PRESERVING ENCRYPTION

• US 20170078251A1
• Filed: 09/11/2015
• Published: 03/16/2017
• Est. Priority Date: 09/11/2015
• Status: Active Grant

• Current Assignee: Skyhigh Security LLC
• Original Assignee: Skyhigh Networks Incorporated (McAfee, LLC)
• Inventors: Grubbs, Paul
• Granted Patent: US 9,760,637 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: H04L 63/0281 Proxies
• CPC Class Codes: H04L 63/0471 applying encryption by an intermediary, e.g. receiving clear information at the intermediary and encrypting the received information at the intermediary before forwarding

Abstract

A encrypted text wildcard search method enables wildcard search of encrypted text by using a permuterm index storing permuted keyword strings that are encrypted using an order preserving encryption algorithm. The permuted keyword strings are encrypted using an order preserving encryption algorithm or a modular order preserving encryption algorithm and stored in the permuterm index. In response to a search query containing a wildcard search term, the encrypted text wildcard search method transforms the wildcard search term to a permuted search term having a prefix search format. The permuted search term having the prefix search format is then used to perform a range query of the permuterm index to retrieve permuted keyword strings having ciphertext values that fall within the range query. In some embodiments, the encrypted text wildcard search method enables prefix search, suffix search, inner-wildcard search, substring search and multiple wildcard search of encrypted text.

Claims

1. A method for performing wildcard search of encrypted cloud stored data comprising:

receiving, at a network intermediary, a document destined for a cloud service provider;

encrypting, at a network intermediary, the document using a document encryption algorithm;

generating a set of permuted keyword strings for each of some or all of the keywords in the document, the set of permuted keyword strings for each keyword being generated by adding a first character delimiter before the first character of the keyword and applying cyclic rotation of the characters of the keyword, including the first character limiter;

encrypting the permuted keyword strings using an order preserving encryption algorithm;

storing the encrypted permuted keyword strings in a database; and

transmitting the encrypted document to the cloud service provider.

2. The method of claim 1, further comprising:

receiving, at a network intermediary, a search request with a search term directed to encrypted documents stored in a cloud service provider, the search term comprising a wildcard search term;

transforming the search term to a permuted search term having a prefix search format;

generating a minimum plaintext string using the permuted search term as prefix and padding the permuted search term to a first character length using one or more trailing characters indicative of a minimum possible value related to the search term;

generating a maximum plaintext string using the permuted search term as prefix and padding the permuted search term to the first character length using one or more trailing characters indicative of a maximum possible value related to the search term;

encrypting the minimum plaintext string and the maximum plaintext string using the order-preserving encryption algorithm used to encrypt the permuted keyword strings;

generating a minimum ciphertext from the minimum possible plaintext string and a maximum ciphertext from the maximum possible plaintext string;

determining a set of common leading digits from the minimum ciphertext and the maximum ciphertext;

generating a range query including the set of common leading digits;

sending the range query to the database of encrypted permuted keyword strings; and

receiving a search result from the database including encrypted permuted keyword strings having ciphertext values that fall within the range query.

3. The method of claim 1, wherein encrypting, at a network intermediary, the document using a document encryption algorithm comprises:

encrypting, at a network intermediary, the document using an AES256-GCM authenticated encryption algorithm.

4. The method of claim 1, wherein encrypting the permuted keyword strings using an order preserving encryption algorithm comprises:

encrypting the permuted keyword strings using a modular order preserving encryption algorithm.

5. The method of claim 2, wherein the wildcard search term comprises one of a prefix search term, a suffix search term, an inner-wildcard search term, a substring search and a multiple wildcard search term, the wildcard search term being a character string including a wildcard term;

and wherein transforming the search term to a permuted search term having a prefix search format comprises adding the first character delimiter to the character string of the wildcard search term and rotating the characters of the character string until the wildcard term is at an end of the character string.

6. The method of claim 2, further comprising:

decrypting the encrypted permuted keyword strings in the search result using the order preserving encryption algorithm; and

unpermuting, using the first character delimiter, the decrypted permuted keyword strings to obtain plaintext keyword strings with the first character of each plaintext keyword string in a first position in the keyword string.

7. The method of claim 6, further comprising:

encrypting the plaintext keyword strings of the search result using the document encryption algorithm;

formulating a second search request using the encrypted keyword strings;

transmitting the second search request including the encrypted keyword strings to the cloud service provider;

receiving a second search result including an encrypted document stored in the cloud service provider having an encrypted text matching at least one of the encrypted keyword strings;

decrypting the returned encrypted document; and

providing the decrypted document in response to the search request.

8. The method of claim 2, further comprising:

providing the encrypted permuted keyword strings of the search result to a searchable encryption search index;

searching for the encrypted permuted keyword strings in the searchable encryption search index;

retrieving from the search index an encrypted document index mapped to a matching encrypted permuted keyword string;

decrypting the encrypted document index;

retrieving an encrypted document from the cloud service provider using the decrypted document index;

decrypting the retrieved document; and

providing the decrypted document in response to the search request.

9. The method of claim 2, wherein generating a minimum plaintext string using the permuted search term as prefix and padding the permuted search term to a first character length using one or more trailing characters indicative of a minimum possible value related to the search term comprises:

determining the character type of the permuted search term; and

padding one or more trailing characters to the permuted search term using the minimum possible value associated with the character type of the permuted search term.

10. The method of claim 2, wherein generating a maximum plaintext string using the permuted search term as prefix and padding the permuted search term to the first character length using one or more trailing characters indicative of a maximum possible value related to the search term comprises:

determining the character type of the permuted search term; and

padding one or more trailing characters to the permuted search term using the maximum possible value associated with the character type of the permuted search term.

11. A system for performing wildcard search of encrypted cloud stored data, comprising:

a network proxy server configured as a network intermediary between a user device and a cloud service provider storing encrypted files on behalf of the user device; and

a database in communication with the network proxy server,

wherein the network proxy server is configured to receive a document destined for the cloud service provider, to encrypt the document using a document encryption algorithm, to generate a set of permuted keyword strings for each of some or all of the keywords in the document, the set of permuted keyword strings for each keyword being generated by adding a first character delimiter before the first character of the keyword and applying cyclic rotation of the characters of the keyword, including the first character limiter, to encrypt the permuted keyword strings using an order preserving encryption algorithm, to store the encrypted permuted keyword strings in the database, and to transmit the encrypted document to the cloud service provider.

12. The system of claim 11, wherein the network proxy server is further configured to receive a search request with a search term directed to encrypted documents stored in a cloud service provider, the search term comprising a wildcard search term, to transform the search term to a permuted search term having a prefix search format, to generate a minimum plaintext string using the permuted search term as prefix and padding the permuted search term to a first character length using one or more trailing characters indicative of a minimum possible value related to the search term, to generate a maximum plaintext string using the permuted search term as prefix and padding the permuted search term to the first character length using one or more trailing characters indicative of a maximum possible value related to the search term, to encrypt the minimum plaintext string and the maximum plaintext string using the order-preserving encryption algorithm used to encrypt the permuted keyword strings, to generate a minimum ciphertext from the minimum possible plaintext string and a maximum ciphertext from the maximum possible plaintext string, to determine a set of common leading digits from the minimum ciphertext and the maximum ciphertext, to generate a range query including the set of common leading digits, to send the range query to the database of encrypted permuted keyword strings, and to receive a search result from the database including encrypted permuted keyword strings having ciphertext values that fall within the range query.

13. The system of claim 11, wherein the network proxy server is further configured to encrypt the document using an AES256-GCM authenticated encryption algorithm.

14. The system of claim 11, wherein the network proxy server is further configured to encrypt the permuted keyword strings using a modular order preserving encryption algorithm.

15. The system of claim 11, wherein the wildcard search term comprises one of a prefix search term, a suffix search term, an inner-wildcard search term, a substring search and a multiple wildcard search term, the wildcard search term being a character string including a wildcard term;

and wherein the network proxy server is further configured to transform the search term to a permuted search term having a prefix search format by adding the first character delimiter to the character string of the wildcard search term and rotating the characters of the character string until the wildcard term is at an end of the character string.

16. The system of claim 11, wherein the network proxy server is further configured to decrypt the encrypted permuted keyword strings in the search result using the order preserving encryption algorithm and to unpermute, using the first character delimiter, the decrypted permuted keyword strings to obtain plaintext keyword search result with the first character of each plaintext keyword string in a first position in the keyword string.