Searchable encryption enabling encrypted search based on document type

• US 9,894,042 B2
• Filed: 07/24/2015
• Issued: 02/13/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:
  US14/808,900
• Publication Number:
  US 20170026350A1
• Time in Patent Office: 935 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 for searchable encryption of cloud stored data encoding a document type, comprising:

receiving, at a network intermediary device over a communication network, a document of a first document type destined for a cloud service provider, the first document type identifying a logical definition of the document as defined by a computing system;

applying, at the network intermediary device, a searchable encryption algorithm to the document to generate a search index;

in response to the encryption of the document by the searchable encryption algorithm, generating, by the network intermediary device, one or more entries in the search index stored in the network intermediary, the one or more entries including a mapping of encrypted keyword labels for some or all of the keywords in the document to an encrypted document index identifying the document being encrypted, each encrypted keyword label being generated by applying a pseudorandom function using a key to encode a document type identifier into the encrypted keyword label, where the key relates to a respective keyword of the document, the document type identifier is indicative of the first document type of the document, the document type identifier identifying the logical definition of the document as defined by the computing system;

encrypting, by the network intermediary device, the document using a second encryption algorithm;

transmitting, over the communication network by the network intermediary device, the encrypted document to the cloud service provider to be stored at the cloud service provider;

receiving, at the network intermediary device over the communication network by a client device, a search request comprising a requested document type for documents stored at the cloud service provider; and

retrieving, by the network intermediary device, from the cloud service providers one or more documents matching the requested document type,

wherein generating, by the network intermediary device, one or more entries in the search index stored in the network intermediary comprises;

generating, by the network intermediary device, one or more entries in the search index stored in the network intermediary, the one or more entries including a mapping of encrypted keyword labels for some or all of the keywords in the document to the encrypted document index identifying the document being encrypted, each encrypted keyword label being generated by applying the pseudorandom function using a key to encode a document type identifier indicative of the document type of the document and a counter value indicative of a number of occurrences of the respective keyword in previously encrypted documents of the same document type as the document being encrypted.

2. The method of claim 1, wherein receiving, at the network intermediary device, the document of the first document type destined for a cloud service provider further 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 the computing system;

and wherein generating one or more entries in a search index stored in the network intermediary device comprises;

generating a first entry in the search index including a mapping of a first encrypted keyword label associated with a first keyword in a first document to an encrypted document index identifying the first document being encrypted, the first encrypted keyword label being generated by applying the pseudorandom function using a key being a function of the first keyword to encode a document type identifier indicative of the document type of the first document and a counter value indicative of a first occurrence of the first keyword in previously encrypted documents of the same document type as the first document; and

generating a second entry in the search index including a mapping of a second encrypted keyword label associated with the first keyword in a second document to an encrypted document index identifying the second document being encrypted, the second encrypted keyword label being generated by applying the pseudorandom function using a key being a function of the first keyword to encode a document type identifier indicative of a document type of the second document and a counter value indicative of a first occurrence of the first keyword in previously encrypted documents of the same document type as the second document, the first document and the second document having different document types and different document type identifiers.

3. The method of claim 1, wherein receiving, at the network intermediary device, the document of the first document type destined for a cloud service provider further 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 the computing system;

and wherein generating one or more entries in a search index stored in the network intermediary device comprises;

generating a first entry in the search index including a mapping of a first encrypted keyword label associated with a first keyword in a first document to an encrypted document index identifying the first document being encrypted, the first encrypted keyword label being generated by applying the pseudorandom function using a key being a function of the first keyword to encode g a document type identifier indicative of the document type of the first document and a counter value indicative of a first occurrence of the first keyword in previously encrypted documents of the same document type as the first document; and

generating a third entry in the search index including a mapping of a third encrypted keyword label associated with the first keyword in a third document to an encrypted document index identifying the third document being encrypted, the third encrypted keyword label being generated by applying the pseudorandom function using a key being a function of the first keyword to encode a document type identifier indicative of a document type of the third document and a counter value indicative of a second occurrence of the first keyword in previously encrypted documents of the same document type as the third document, the first document and the third document having the same document type and the same document type identifiers.

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

encrypting the document using a bulk encryption algorithm.

5. The method of claim 1, further comprising:

receiving, at the network intermediary device, a search request with a search term and a requested document type;

generating a search term label by applying the pseudorandom function using a key being a function of the search term in the search request to encode a document type identifier indicative of the requested document type in the search request;

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 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 of the requested document type as the search result.

6. The method of claim 1, further comprising:

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

generating a search term label by applying the pseudorandom function using a key being a function of the search term in the search request to encode a document type identifier indicative of a first document type;

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;

in response to the search term label not matching an encrypted keyword label in the search index, repeating the generating the search term label and the searching for the search term label for a next document type until the last of all document types;

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 of any document type as the search result.

7. The method of claim 1, further comprising:

receiving, at the network intermediary device, a search request with a search term and a requested document type;

setting the counter value to an initial value;

generating a search term label by applying the pseudorandom function using a key being a function of the search term in the search request to encode a document type identifier indicative of the requested document type in the search request and further encoding the counter value;

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, incrementing the counter value and repeating the generating a search term label using the current counter value;

in response to the search term label not matching an encrypted keyword label in the search index, stopping the searching of the search term label in the search index;

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.

8. The method of claim 1, further comprising:

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

setting the document type identifier to an initial value;

setting the counter value to an initial value;

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

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, incrementing the counter value and repeating the generating a search term label using the current counter value and the current document type identifier;

in response to the search term label not matching an encrypted keyword label in the search index, incrementing the document type identifier to the next document type identifier and repeating the setting the counter value to an initial value and the generating a search term label using the current counter value and the current document type identifier until the last of all document types;

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.

9. The method of claim 1, wherein receiving, at the network intermediary device, the document of a first document type destined for a cloud service provider 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 type comprising a logical definition of the document.

10. A system for searchable encryption of cloud stored data encoding a document type, comprising:

a network proxy server configured as a network intermediary device to receive, over a communication network, a document of a first document type destined for a cloud service provider, the first document type identifying a logical definition of the document as defined by a computing system, the network proxy server being configured to apply a searchable encryption algorithm to the document to generate a search index, in response to the encryption of the document by the searchable encryption algorithm, the network proxy server is being configured to generate one or more entries in a search index stored in the network intermediary device where the one or more entries include a mapping of encrypted keyword labels for some or all of the keywords in the document to an encrypted document index identifying the document being encrypted, each encrypted keyword label being generated by applying a pseudorandom function using a key to encode a document type identifier into the encrypted keyword label, where the key relates to a respective keyword of the document, the document type identifier is indicative of the first document type of the document, the document type identifier identifying the logical definition of the document as defined by the computing system, the network proxy server further configured to encrypt the document using a second encryption algorithm, to transmit, over the communication network, the encrypted document to the cloud service provider to be stored at the cloud service provider, to receive, over the communication network by a client device, a search request comprising a requested document type for documents stored at the cloud service provider, and to retrieve from the cloud service providers one or more documents matching the requested document type,

wherein the network proxy server is further configured to generate one or more entries in the search index stored in the network intermediary device where the one or more entries including a mapping of encrypted keyword labels for some or all of the keywords in the document to the encrypted document index identifying the document being encrypted, each encrypted keyword label being generated by applying the pseudorandom function using a key to encode a document type identifier indicative of the document type of the document and a counter value indicative of a number of occurrences of the respective keyword in previously encrypted documents of the same document type as the document being encrypted.

11. The system of claim 10, wherein the network proxy server is further configured to encrypt the document using a bulk encryption algorithm.

12. The system of claim 10, wherein the network proxy server is further configured to receive a search request with a search term and a requested document type, to generating a search term label by applying the pseudorandom function using a key being a function of the search term in the search request to encode a document type identifier indicative of the requested document type in the search request, 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 decrypting the 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 of the requested document type as the search result.

13. The system of claim 10, wherein the network proxy server is further configured to receive a search request with a search term for all document types, to generate a search term label by applying the pseudorandom function using a key being a function of the search term in the search request to encode a document type identifier indicative of a first document type, 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, in response to the search term label not matching an encrypted keyword label in the search index, to repeat the generating the search term label and the searching for the search term label for a next document type until the last of all document types, 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 of any document type as the search result.

14. The system of claim 10, wherein the network proxy server is further configured to receive a search request with a search term and a requested document type, to set the counter value to an initial value, to generate a search term label by applying the pseudorandom function using a key being a function of the search term in the search request to encode a document type identifier indicative of the requested document type in the search request and further encoding the counter value, 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 and to increment the counter value and to repeat the generating a search term label using the current counter value, in response to the search term label not matching an encrypted keyword label in the search index, to stop the searching of the search term label in the search index, 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.

15. The system of claim 10, wherein the network proxy server is further configured to receive a search request with a search term for all document types, to set the document type identifier to an initial value, to set the counter value to an initial value, to generate a search term label by applying the pseudorandom function using a key being a function of the search term in the search request to encode the document type identifier and the counter value, 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 and to increment the counter value and to repeat the generating a search term label using the current counter value and the current document type identifier, in response to the search term label not matching an encrypted keyword label in the search index, to increment the document type identifier to the next document type identifier and to repeat the setting the counter value to an initial value and the generating a search term label using the current counter value and the current document type identifier until the last of all document types, 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.

16. The system of claim 10, wherein the network proxy server 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, the document type comprising a logical definition of the document.