Wildcard search in encrypted text

• US 10,176,207 B1
• Filed: 06/09/2015
• Issued: 01/08/2019
• Est. Priority Date: 06/09/2015
• Status: Active Grant

• Current Assignee: Skyhigh Security LLC
• Original Assignee: Skyhigh Networks Incorporated (McAfee, LLC)
• Inventors: Dawoud, Hani T.
• Primary Examiner(s): Jami, Hares
• Application Number:
  US14/734,880
• Time in Patent Office: 1,309 Days
• Field of Search: 707741, 707758, 707790, 707803
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/9032 Query formulation
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries

Abstract

A wildcard searchable encryption method enables wildcard search of encrypted text in a cloud-stored encrypted file. In some embodiments, the wildcard searchable encryption method is implemented in a network intermediary, such as a proxy server. The network intermediary encrypts files on behalf of a user or an enterprise destined to be stored on a cloud storage service. The wildcard searchable encryption method performs keyword pre-processing of the file to be encrypted to generate a set of keyword-wildcard combinations in plaintext for some or all of the keywords in the file. The processed file is encrypted using an exact match searchable encryption algorithm. As a result of the encryption process, a search index is generated to include the keyword-wildcard combinations. As thus configured, the wildcard searchable encryption method enables wildcard search of the encrypted text, such as searches for prefixes or suffixes of the keywords.

Claims

1. A method for wildcard searchable encryption of cloud stored data, comprising:

receiving, using a hardware processor, a file destined for a cloud storage service;

processing, using the hardware processor, the content of the file to generate a plurality of keyword-wildcard combinations in plaintext for some or all of the keywords in the file;

generating a processed file including the original file content and the keyword-wildcard combinations in plaintext appended to the original file;

encrypting the processed file using an exact match searchable encryption algorithm;

generating a search index stored using the hardware processor and including a mapping of encrypted keywords of the processed file to a document index identifying the file being encrypted, the encrypted keywords of the processed file including encrypted keywords of the original file content and encrypted keyword-wildcard combinations appended to processed file; and

transmitting the encrypted file to the cloud storage service.

2. The method of claim 1, wherein processing, using the hardware processor, the content of the file to generate a plurality of keyword-wildcard combinations in plaintext for some or all of the keywords in the file comprises:

processing, using the hardware processor, the content of the file to generate the plurality of keyword-wildcard combinations in plaintext for some or all of the words in the file, each of the words in the file including one or more characters of the uppercase and lower case English alphabet, numbers 0-9, punctuation symbols, alphabet and symbols of languages other than English, and other ASCII characters.

3. The method of claim 1, wherein processing, using the hardware processor, the content of the file to generate a plurality of keyword-wildcard combinations in plaintext for some or all of the keywords in the file comprises:

processing the content of the file to generate a plurality of prefix combinations in plaintext for some or all of the keywords in the file.

4. The method of claim 3, wherein processing the content of the file to generate a plurality of prefix combinations in plaintext for some or all of the keywords in the file comprises:

processing the content of the file to generate the plurality of prefix combinations for a keyword including one or more leading characters of the keyword forming prefixes of the keyword, one or more remaining characters being a wildcard.

5. The method of claim 1, wherein processing, using the hardware processor, the content of the file to generate a plurality of keyword-wildcard combinations in plaintext for some or all of the keywords in the file comprises:

processing the content of the file to generate a plurality of suffix combinations in plaintext for some or all of the keywords in the file.

6. The method of claim 5, wherein processing the content of the file to generate a plurality of suffix combinations in plaintext for some or all of the keywords in the file comprises:

processing the content of the file to generate the plurality of suffix combinations for a keyword including one or more trailing characters of the keyword forming suffixes of the keyword, one or more remaining characters being a wildcard.

7. The method of claim 1, wherein generating a processed file including the original file content and the keyword-wildcard combinations in plaintext appended to the original file comprises:

appending the keyword-wildcard combinations in plaintext to the tail of the original file content.

8. The method of claim 1, further comprising:

receiving, using the hardware processor, a search request with a search term;

encrypting the search term in the search request using the exact match searchable encryption algorithm;

searching for the encrypted search term in the search index;

receiving a search result from the search index in response to the encrypted search term matching an encrypted keyword in the search index, the search result comprising a document index associated with the matched encrypted keyword;

retrieving the encrypted file from the cloud storage service using the document index in the search result;

decrypting the retrieved file; and

providing the decrypted file as the search result.

9. A system for wildcard searchable encryption of cloud stored data, comprising:

a memory; and

a hardware processor coupled to the memory, wherein the hardware processor is configured to receive a file destined for a cloud storage service, to process the content of the file to generate a plurality of keyword-wildcard combinations in plaintext for some or all of the keywords in the file, to generate a processed file including the original file content and the keyword-wildcard combinations in plaintext appended to the original file, to encrypt the processed file using an exact match searchable encryption algorithm, to generate a search index stored in the network intermediary and including a mapping of encrypted keywords of the processed file to a document index identifying the file being encrypted where the encrypted keywords of the processed file include encrypted keywords of the original file content and encrypted keyword-wildcard combinations appended to processed file, and to transmit the encrypted file to the cloud storage service.

10. The system of claim 9, wherein the hardware processor is further configured to process the content of the file to generate a plurality of keyword-wildcard combinations in plaintext for some or all of the words in the file, each of the words in the file including one or more characters of the uppercase and lower case English alphabet, numbers 0-9, punctuation symbols, alphabet and symbols of languages other than English, and other ASCII characters.

11. The system of claim 9, wherein the hardware processor is further configured to process the content of the file to generate a plurality of prefix combinations in plaintext for some or all of the keywords in the file.

12. The system of claim 11, wherein the hardware processor is further configured to process the content of the file to generate the plurality of prefix combinations in plaintext for a keyword including one or more leading characters of the keyword forming prefixes of the keyword, one or more remaining characters being a wildcard.

13. The system of claim 9, wherein the hardware processor is further configured to process the content of the file to generate a plurality of suffix combinations in plaintext for some or all of the keywords in the file.

14. The system of claim 13, wherein the hardware processor is further configured to process the content of the file to generate the plurality of suffix combinations in plaintext for a keyword including one or more trailing characters of the keyword forming suffixes of the keyword, one or more remaining characters being a wildcard.

15. The system of claim 9, wherein the hardware processor is further configured to append the keyword-wildcard combinations in plaintext to the tail of the original file content.

16. The system of claim 9, wherein the hardware processor is further configured to receive a search request with a search term, to encrypt the search term in the search request using the exact match searchable encryption algorithm, to search for the encrypted search term in the search index, to receive a search result from the search index in response to the encrypted search term matching an encrypted keyword in the search index where the search result includes a document index associated with the matched encrypted keyword, to retrieve the encrypted file from the cloud storage service using the document index in the search result, to decrypt the retrieved file, and to provide the decrypted file as the search result.