Wildcard search in encrypted text

• US 10,404,669 B2
• Filed: 07/24/2015
• Issued: 09/03/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): Burke, Jeff A
• Assistant Examiner(s): Nguyen, Cindy
• Application Number:
  US14/808,850
• Publication Number:
  US 20160366113A1
• Time in Patent Office: 1,502 Days
• CPC Class Codes: G06F 16/14 Details of searching files based on file metadata
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/33 Querying
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 2221/2107 File encryption
• 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
• CPC Class Codes: H04L 63/062 for key distribution, e.g. centrally by trusted party cryptographic mechanisms or cryptographic arrangements for key distribution involving a central third party H04L9/0819
• CPC Class Codes: H04L 63/0876 based on the identity of the terminal or configuration, e.g. MAC address, hardware or software configuration or device fingerprint
• CPC Class Codes: H04L 9/0637 Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM]

Abstract

A wildcard searchable encryption method enables wildcard search of encrypted text in a cloud-stored encrypted document. In some embodiments, the wildcard searchable encryption method is implemented in a network intermediary, such as a proxy server. The network intermediary encrypts documents on behalf of a user or an enterprise destined to be stored on a cloud service provider. The wildcard searchable encryption method performs keyword pre-processing of the document to be encrypted to generate a set of keyword-wildcard combinations in plaintext for some or all of the keywords in the document. The processed document 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, at a network intermediary, a document destined for a cloud service provider;

processing, at the network intermediary, the content of the document to generate a plurality of keyword-wildcard combinations in plaintext for some or all of the keywords in the document;

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

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

generating one or more entries in a search index stored in the network intermediary, the one or more entries including a mapping of encrypted keyword labels to an encrypted document index identifying the document being encrypted, the encrypted keyword labels being generated using at least some keywords of the original document content and at least some keyword-wildcard combinations appended to processed document;

encrypting the original document using a second encryption algorithm; and

transmitting the encrypted document to the cloud service provider.

2. The method of claim 1, wherein processing, at the network intermediary, the content of the document to generate a plurality of keyword-wildcard combinations in plaintext for some or all of the keywords in the document comprises:

processing, at the network intermediary, the content of the document to generate the plurality of keyword-wildcard combinations in plaintext for some or all of the words in the document, each of the words in the document 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, at the network intermediary, the content of the document to generate a plurality of keyword-wildcard combinations in plaintext for some or all of the keywords in the document comprises:

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

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

processing the content of the document 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, at the network intermediary, the content of the document to generate a plurality of keyword-wildcard combinations in plaintext for some or all of the keywords in the document comprises:

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

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

processing the content of the document 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 document including the original document content and the keyword-wildcard combinations in plaintext appended to the original document comprises:

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

8. The method of claim 1, wherein encrypting the original document using the second encryption algorithm comprises:

encrypting the original document using a bulk encryption algorithm.

9. The method of claim 1, further comprising:

receiving, at the network intermediary, a search request with a search term;

generating a search term label using the search term in the search request being applied to the exact match searchable encryption algorithm;

searching for the search term label in the search index;

in response to the search term label matching an encrypted keyword label in the search index, retrieving from the search index the encrypted document index mapped to the matching encrypted keyword label;

decrypting the retrieved encrypted document index;

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

decrypting the retrieved document; and

providing the decrypted document as the search result.

10. The method of claim 1, wherein receiving, at the network intermediary, the document destined for the cloud service provider comprises:

receiving, at the network intermediary, the document destined for the cloud service provider, the document comprising one of a file, a data record, a data field, a data with structured data format, or a data with unstructured data format.

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

a memory;

a hardware processor coupled to the memory and configured to receive a document destined for a cloud service provider, to process the content of the document to generate a plurality of keyword-wildcard combinations in plaintext for some or all of the keywords in the document, to generate a processed document including the original document content and the keyword-wildcard combinations in plaintext appended to the original document, to encrypt the processed document using an exact match searchable encryption algorithm, to generate one or more entries in a search index stored in the network intermediary, the one or more entries including a mapping of encrypted keyword labels to an encrypted document index identifying the document being encrypted where the encrypted keyword labels are generated using at least some keywords of the original document content and at least some keyword-wildcard combinations appended to processed document, to encrypt the original document using a second encryption algorithm, and to transmit the encrypted document to the cloud service provider.

12. The system of claim 11, wherein the hardware processor is further configured to process the content of the document to generate a plurality of keyword-wildcard combinations in plaintext for some or all of the words in the document, each of the words in the document 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.

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

14. The system of claim 13, wherein the hardware processor is further configured to process the content of the document 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.

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

16. The system of claim 15, wherein the hardware processor is further configured to process the content of the document 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.

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

18. The system of claim 11, wherein the hardware processor is further configured to encrypting the original document using a bulk encryption algorithm.

19. The system of claim 11, wherein the hardware processor is further configured to receive a search request with a search term, to generate a search term label using the search term in the search request being applied to the exact match searchable encryption algorithm, to search for the search term label in the search index, in response to the search term label matching an encrypted keyword label in the search index, to retrieve from the search index the encrypted document index mapped to the matching encrypted keyword label, to decrypt the retrieved encrypted document index, to retrieve the encrypted document from the cloud service provider using the decrypted document index, to decrypt the retrieved document, and to provide the decrypted document as the search result.

20. The system of claim 11, wherein the hardware processor is further configured to receive the document destined for the cloud service provider, the document comprising one of a file, a data record, a data field, a data with structured data format, or a data with unstructured data format.