Searchable encryption enabling encrypted search based on document type

• US 10,498,706 B2
• Filed: 08/27/2018
• Issued: 12/03/2019
• 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:
  US16/113,929
• Publication Number:
  US 20190124052A1
• Time in Patent Office: 463 Days
• Field of Search: 713150, 713154, 713165, 713168, 713189, 707759, 380 30
• 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;

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 of the plurality of keys using a first encryption algorithm;

generating an encrypted keyword label based on a second of the plurality of keys, the determined document type, 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 a pseudorandom function; 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 that is different from the first 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;

generating a search term label based on the pseudorandom function, a key that is a function of the search term, a document type, and a search value;

searching for the search term label in the search index;

in response to finding the search term label in the search index;

retrieving from the search index the encrypted document index corresponding to the search term label;

changing the search value; and

after changing the search value, regenerating the search term label based on the pseudorandom function, the key, the document type, and the search value;

in response to not finding the search term label in the search index;

changing the document type;

after changing the document type, regenerating the search term label based on at least the pseudorandom function, the key, and the document type;

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;

a memory; and

at least hardware processor collectively 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;

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 using a first encryption algorithm;

generate an encrypted keyword label based on a second of the plurality of keys, the determined document type, 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 a pseudorandom function; 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 that is different from the first 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;

generate a search term label based on the pseudorandom function, a key that is a function of the search term, a document type, and a search value;

search for the search term label in the search index;

in response to finding the search term label in the search index;

retrieve from the search index the encrypted document index corresponding to the search term label;

change the search value; and

after changing the search value, regenerate the search term label based on the pseudorandom function, the key, the document type, and the search value;

in response to not finding the search term label in the search index;

change the document type;

after changing the document type, regenerate the search term label based on at least the pseudorandom function, the key, and the document type;

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 the at least one hardware processor, in encrypting the document using the second encryption algorithm, encrypts the document using a bulk encryption algorithm.

9. The system of claim 6, wherein the at least one hardware processor, in receiving the document destined for a cloud service provider, receives 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 the at least one hardware processor, in receiving the document destined for a cloud service provider, receives 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.

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;

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 of the plurality of keys using a first encryption algorithm;

generating an encrypted keyword label based on a second of the plurality of keys, the determined document type, 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 a pseudorandom function; 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 that is different from the first encryption algorithm;

transmitting the encrypted document to the cloud service provider;

storing the encrypted document at the cloud service provider;

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

generating a search term label based on the pseudorandom function, a key that is a function of the search term, a document type, and a search value;

searching for the search term label in the search index;

in response to finding the search term label in the search index;

retrieving from the search index the encrypted document index corresponding to the search term label;

changing the search value; and

after changing the search value, regenerating the search term label based on the pseudorandom function, the key, the document type, and the search value;

in response to not finding the search term label in the search index;

changing the document type;

after changing the document type, regenerating the search term label based on at least the pseudorandom function, the key, and the document type;

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 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.

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 in the network intermediary device.