Providing secure indexes for searching encrypted data

Patent metadata

Field	Value
Publication number	US-9633219-B2
Application number	US-201514835816-A
Country	US
Kind code	B2
Filing date	Aug 26, 2015
Priority date	Aug 26, 2015
Publication date	Apr 25, 2017
Grant date	Apr 25, 2017

Abstract

Providing an encrypted search index for performing searches on encrypted documents, the method comprising: (i) providing a set of documents, the documents comprising a plurality of unencrypted phrases; (ii) providing a master key; (iii) providing, based on the master key, for each phrase a set of encryption keys comprising one or more encryption keys; (iv) selecting, for each phrase, one encryption key of the set of encryption keys; (v) encrypting each phrase with the selected encryption key; and (vi) building an index based on the encrypted phrases, the index comprising information regarding which encrypted phrase is comprised within a certain document.

First claim

What is claimed is:

1. A computer-implemented method for providing an encrypted search index for performing searches on encrypted documents, the method comprising:
providing, to a computing device, a set of electronic documents, the electronic documents including a plurality of unencrypted phrases, wherein the unencrypted phrases are words and/or word fragments included in the set of documents;
providing, to the computing device, a master key;
determining, by the computing device, a frequency parameter for each unencrypted phrase included in the documents based on a frequency evaluation scheme, with the frequency parameter indicating the number of encryption key(s) to be included in a set of encryption key(s) for each unencrypted phrase, and wherein the number of encryption key(s) to be included in the set of encryption key(s) is based on a frequency of usage of the unencrypted phrase as indicated by a reference frequency list;
providing, by the computing device, based on the master key and respectively for each unencrypted phrase, the set of encryption key(s), wherein the set of encryption key(s) is different for each unencrypted phrase;
selecting, by the computing device, for each unencrypted phrase, a selected encryption key of the set of encryption key(s) respectively corresponding to the unencrypted phrase;
encrypting, by the computing device, each unencrypted phrase with the selected encryption key corresponding to the unencrypted phrase to yield an encrypted phrase corresponding to the unencrypted phrase; and
building, by the computing device, an index based on the encrypted phrases, the index including information indicating which encrypted phrase is included within each electronic document of the set of electronic documents.

2. The computer-implemented method of claim 1 , wherein the selection of the selected encryption key is based on a statistical method.

3. The computer-implemented method of claim 1 , wherein at least some of the word fragments correspond to a front portion of a word corresponding to the word fragment.

4. The computer-implemented method of claim 3 , wherein each word is segmented in one, or more, front portions, with each front portion having a word fragment length above a certain threshold value.

5. The computer-implemented method of claim 1 , wherein the word fragments are formed by choosing word segments based on a sliding window moving across the words.

6. A computer program product for providing an encrypted search index for performing searches on encrypted documents, the computer program product comprising a non-transitory computer-readable storage device with computer-executable instructions stored thereon that, when executed by one or more computer processors, cause the one or more computer processors to perform operations comprising:
receiving a set of electronic documents, the electronic documents including a plurality of unencrypted phrases, wherein the unencrypted phrases are words and/or word fragments included in the set of documents;
receiving a master key;
determining, by the computing device, a frequency parameter for each unencrypted phrase included in the documents based on a frequency evaluation scheme, with the frequency parameter indicating the number of encryption key(s) to be included in a set of encryption key(s) for each unencrypted phrase, and wherein the number of encryption key(s) to be included in the set of encryption key(s) is based on a frequency of usage of the unencrypted phrase as indicated by a reference frequency list;
providing, based on the master key and respectively for each unencrypted phrase, the set of encryption key(s), wherein the set of encryption key(s) is different for each unencrypted phrase;
selecting, for each unencrypted phrase, a selected encryption key of the set of encryption key(s) respectively corresponding to the unencrypted phrase;
encrypting each unencrypted phrase with the selected encryption key corresponding to the unencrypted phrase to yield an encrypted phrase corresponding to the unencrypted phrase; and
building an index based on the encrypted phrases, the index including information indicating which encrypted phrase is included within each electronic document of the set of electronic documents.

7. A computer system comprising one or more computer processors and a non-transitory computer-readable storage device with computer-executable instructions stored thereon that, when executed by the one or more computer processors, cause the one or more computer processors to perform operations comprising:
receiving a set of electronic documents, the electronic documents including a plurality of unencrypted phrases, wherein the unencrypted phrases are words and/or word fragments included in the set of electronic documents;
receiving a master key;
determining, by the computing device, a frequency parameter for each unencrypted phrase included in the documents based on a frequency evaluation scheme, with the frequency parameter indicating the number of encryption key(s) to be included in a set of encryption key(s) for each unencrypted phrase, and wherein the number of encryption key(s) to be included in the set of encryption key(s) is based on a frequency of usage of the unencrypted phrase as indicated by a reference frequency list;
providing, based on the master key and respectively for each unencrypted phrase, the set of encryption key(s), wherein the set of encryption key(s) is different for each unencrypted phrase;
selecting, for each unencrypted phrase, a selected encryption key of the set of encryption key(s) respectively corresponding to the unencrypted phrase;
encrypting each unencrypted phrase with the selected encryption key corresponding to the unencrypted phrase to yield an encrypted phrase corresponding to the unencrypted phrase; and
building an index based on the encrypted phrases, the index including information indicating which encrypted phrase is included within each electronic document of the set of electronic documents.

Assignees

• IBM

Inventors

• Baessler Michael
• Doerre Jochen
• Hampp-Bahnmueller Thomas A P
• Hoffmann Philipp
• Pittner Daniel
• Schollenberger Werner

Classifications

• G06F21/6227 Primary

  where protection concerns the structure of data, e.g. records, types, queries · CPC title

• H04L9/14

  using a plurality of keys or algorithms · CPC title

• G06F17/30619

  Physics · mapped topic

• H04L2463/061

  applying further key derivation, e.g. deriving traffic keys from a pair-wise master key · CPC title

• H04L63/06

  for supporting key management in a packet data network (cryptographic mechanisms or cryptographic arrangements for key management H04L9/08) · CPC title