Searchable encryption enabling encrypted search based on document type

• US 10,063,528 B2
• Filed: 12/20/2017
• Issued: 08/28/2018
• Est. Priority Date: 07/24/2015
• Status: Active Grant

• Current Assignee: Skyhigh Security LLC
• Original Assignee: Skyhigh Networks Incorporated (McAfee, LLC)
• Inventors: Dawoud, Hani T.
• Primary Examiner(s): Gracia, Gary S
• Application Number:
  US15/849,347
• Publication Number:
  US 20180124026A1
• Time in Patent Office: 251 Days
• CPC Class Codes: G06F 16/93 Document management systems
• 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
• 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/067 using one-time keys cryptographic mechanisms or cryptographic arrangements for generation of one-time passwords H04L9/0863
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• 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 searchable encryption method enables encrypted search of encrypted documents based on document type. In some embodiments, the 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 searchable encryption method encodes document type information into the encrypted search index while preserving encryption security. Furthermore, the searchable encryption method enables search of encrypted documents using the same encrypted index, either for a particular document type or for all encrypted documents regardless of the document type.

Claims

1. A method comprising:

receiving, at a network intermediary device over a communication network, a received document destined for a cloud service provider, the received document having a received document type;

determining the received document type of the received document;

determining a received document type identifier corresponding to the received document type;

selecting one or more keywords in the received document;

for each selected one or more keywords in the received document;

deriving a plurality of keys for the selected keyword;

encrypting a document index identifying the received document using a first key of the plurality of keys;

generating an encrypted keyword label by using a second key of the plurality of keys to encode the received document type identifier and a selected keyword counter value indicative of a count of occurrences of the selected keyword in previously encrypted documents of the received document type, and by applying a pseudorandom function to the received document type identifier; and

generating a search index entry mapping the encrypted keyword label to the encrypted document index;

generating a search index in response to the search index entries generated for the one or more keywords in the received document;

encrypting the received document using a second encryption algorithm;

transmitting the encrypted document to the cloud service provider;

storing the encrypted document at the cloud service provider;

receiving, at the network intermediary device, a search request with a search term for all document types;

setting a search document type identifier to an initial search document type identifier value;

setting a search counter value to an initial search counter value;

generating a search term label by applying the pseudorandom function using a key being a function of the search term to encode the search document type identifier and the search counter value;

searching for the search term label in the search index;

in response to the search term label matching the encrypted keyword label in the search index;

retrieving from the search index the encrypted document index mapped to the encrypted keyword label;

incrementing the search counter value; and

after incrementing the search counter value, regenerating the search term label by applying the pseudorandom function using the key being a function of the search term to encode the search document type identifier and the search counter value;

in response to the search term label not matching any encrypted keyword label in the search index;

setting the search document type identifier to a next document type identifier;

resetting the search counter value to the initial search counter value;

after setting the search document type identifier to the next document type identifier and resetting the search counter value to the initial search counter value, regenerating the search term label by applying the pseudorandom function using the key being a function of the search term to encode the search document type identifier and the search counter value;

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.

2. The method of claim 1, wherein the document destined for a cloud service provider comprises a plurality of documents and the received document comprises a plurality of received documents, each of the plurality of received documents having a document type that identifies a logical definition of each of the plurality of received documents.

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

encrypting the document using a bulk encryption algorithm.

4. The method of claim 1, wherein receiving, at the network intermediary device over the communication network, the document destined for a cloud service provider further comprises:

receiving, at a network intermediary device, 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, the document having a document type comprising a logical definition of the document.

5. The method of claim 1:

wherein receiving, at the network intermediary device over the communication network, the document destined for a cloud service provider comprises receiving, at the network intermediary device, a plurality of documents of the same or different document types destined for a cloud service provider, each document type identifying a logical definition of the respective document as defined by a computing system; and

wherein the search index is stored in the network intermediary device.

6. A system comprising:

memory;

at least one hardware processor that is coupled to the memory and that is configured to;

receive a received document destined for a cloud service provider, the received document having a received document type;

determine the received document type of the received document;

determine a received document type identifier corresponding to the received document type;

select one or more keywords in the received document;

for each selected one or more keywords in the received document;

derive a plurality of keys for the selected keyword;

encrypt a document index identifying the received document using a first of the plurality of keys;

generate an encrypted keyword label by using a second of the plurality of keys to encode the received document type identifier and a selected keyword counter value indicative of a count of occurrences of the selected keyword in previously encrypted documents of the received document type, and by applying a pseudorandom function to the received document type identifier; and

generate a search index entry mapping the encrypted keyword label to the encrypted document index;

generate a search index in response to the search index entries generated for the one or more keywords in the received document;

encrypt the received document using a second encryption algorithm;

transmit the encrypted document to the cloud service provider;

store the encrypted document at the cloud service provider;

receive a search request with a search term for all document types;

set a search document type identifier to an initial search document type identifier value;

set a search counter value to an initial search counter value;

generate a search term label by applying the pseudorandom function using a key being a function of the search term to encode the search document type identifier and the search counter value;

search for the search term label in the search index;

in response to the search term label matching the encrypted keyword label in the search index;

retrieve from the search index the encrypted document index mapped to the encrypted keyword label;

increment the search counter value; and

after incrementing the search counter value, regenerate the search term label by applying the pseudorandom function using the key being a function of the search term to encode the search document type identifier and the search counter value;

in response to the search term label not matching any encrypted keyword label in the search index;

set the search document type identifier to a next document type identifier;

reset the search counter value to the initial search counter value;

after setting the search document type identifier to the next document type identifier and resetting the search counter value to the initial search counter value, regenerate the search term label by applying the pseudorandom function using the key being a function of the search term to encode the search document type identifier and the search counter value;

decrypt the retrieved encrypted document index;

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

decrypt the retrieved document; and

provide the decrypted document as the search result.

7. The system of claim 6, wherein the document destined for a cloud service provider comprises a plurality of documents and the received document comprises a plurality of received documents, each of the plurality of received documents having a document type that identifies a logical definition of each of the plurality of received documents.

8. The system of claim 6, wherein encrypting the document using the second encryption algorithm comprises:

encrypting the document using a bulk encryption algorithm.

9. The system of claim 6, wherein receiving the document destined for a cloud service provider further comprises:

receiving 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, the document having a document type comprising a logical definition of the document.

10. The system of claim 6:

wherein receiving the document destined for a cloud service provider comprises receiving a plurality of documents of the same or different document types destined for a cloud service provider, each document type identifying a logical definition of the respective document as defined by a computing system; and

wherein the search index is stored in the memory.

11. A non-transitory computer-readable medium containing computer-executable instructions that, when executed by a processor, cause the processor to perform a method comprising:

receiving a received document destined for a cloud service provider, the received document having a received document type;

determining the received document type of the received document;

determining a received document type identifier corresponding to the received document type;

selecting one or more keywords in the received document;

for each selected one or more keywords in the received document;

deriving a plurality of keys for the selected keyword;

encrypting a document index identifying the received document using a first key of the plurality of keys;

generating an encrypted keyword label by using a second key of the plurality of keys to encode the received document type identifier and a selected keyword counter value indicative of a count of occurrences of the selected keyword in previously encrypted documents of the received document type, and by applying a pseudorandom function to the received document type identifier; and

generating a search index entry mapping the encrypted keyword label to the encrypted document index;

generating a search index in response to the search index entries generated for the one or more keywords in the received document;

encrypting the received document using a second encryption algorithm;

transmitting the encrypted document to the cloud service provider;

storing the encrypted document at the cloud service provider;

receiving, at the network intermediary device, a search request with a search term for all document types;

setting a search document type identifier to an initial search document type identifier value;

setting a search counter value to an initial search counter value;

generating a search term label by applying the pseudorandom function using a key being a function of the search term to encode the search document type identifier and the search counter value;

searching for the search term label in the search index;

in response to the search term label matching the encrypted keyword label in the search index;

retrieving from the search index the encrypted document index mapped to the encrypted keyword label;

incrementing the search counter value; and

after incrementing the search counter value, regenerating the search term label by applying the pseudorandom function using the key being a function of the search term to encode the search document type identifier and the search counter value;

in response to the search term label not matching any encrypted keyword label in the search index;

setting the search document type identifier to a next document type identifier;

resetting the search counter value to the initial search counter value;

after setting the search document type identifier to the next document type identifier and resetting the search counter value to the initial search counter value, regenerating the search term label by applying the pseudorandom function using the key being a function of the search term to encode the search document type identifier and the search counter value;

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.

12. The non-transitory computer-readable medium of claim 11, wherein the document destined for a cloud service provider comprises a plurality of documents and the received document comprises a plurality of received documents, each of the plurality of received documents having a document type that identifies a logical definition of each of the plurality of received documents.

13. The non-transitory computer-readable medium of claim 11, wherein encrypting the document using the second encryption algorithm comprises:

encrypting the document using a bulk encryption algorithm.

14. The non-transitory computer-readable medium of claim 11, wherein the document destined for a cloud service provider further comprises:

receiving 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, the document having a document type comprising a logical definition of the document.

15. The non-transitory computer-readable medium of claim 11:

wherein receiving the document destined for a cloud service provider comprises receiving a plurality of documents of the same or different document types destined for a cloud service provider, each document type identifying a logical definition of the respective document as defined by a computing system; and

wherein the search index is stored a memory coupled to the processor.