Providing secure indexes for searching encrypted data

Patent metadata

Field	Value
Publication number	US-10037435-B2
Application number	US-201615234134-A
Country	US
Kind code	B2
Filing date	Aug 11, 2016
Priority date	Aug 26, 2015
Publication date	Jul 31, 2018
Grant date	Jul 31, 2018

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 searching phrases in an encrypted search index, the method comprising:
providing, to a computing device, an encrypted search index including a plurality of encrypted phrases;
providing, to the computing device, a search query to be applied on the search index, the search query including a set of unencrypted phrase(s) to be searched;
providing, to the computing device, a master key;
determining, by the computing device, a first frequency parameter for a first unencrypted phrase of the set of encrypted phrase(s) based on a frequency evaluation scheme, the first frequency parameter indicating the number of encryption key(s) to be included in the set of encryption key(s) corresponding to the first unencrypted phrase, and wherein the frequency evaluation scheme used in determining the number of encryption key(s) for the first unencrypted phrase is based on a frequency of usage of the first unencrypted phrase as indicated by a reference frequency list;
providing, to the computing device and based on the master key, a set of encryption key(s) for each phrase of the set of unencrypted phrase(s);
generating, by the computing device, a set of encrypted phrase(s) respectively corresponding to the set of unencrypted phrase(s) by encrypting the each unencrypted phrase of the set of unencrypted phrase(s) respectively based on its corresponding set of encryption key(s);
generating, by the computing device, a set of encrypted search query(ies) corresponding to the set of encrypted phrase(s); and
providing, by the computing device, the set of encrypted search query(ies) to a search engine designed to perform searches on the encrypted search index.

2. The computer-implemented method of claim 1 , wherein the set of encrypted search query(ies) includes a plurality of synonymous encrypted search queries, each synonymous encrypted search query having a similar logical structure and being constituted by encrypting phrase synonymous with a corresponding phrase of the set of unencrypted phrase(s).

3. The computer-implemented method of claim 1 , wherein:
the set of encrypted search query(ies) includes a first operator, a first query portion and a second query portion;
in the first search query, the first query portion and the second query portion are logically linked by the first operator; and
the set of encrypted search query(ies) further includes all permutations of the first query portion as encrypted by a first set of encryption keys and second query portion are encrypted by a second set of encryption keys.

4. The computer-implemented method of claim 1 , further comprising:
performing a query permutation function to forward the set of encrypted search query(ies) to the search engine in a statistically distributed manner.

5. The computer-implemented method of claim 1 , further comprising:
performing a query permutation function being adapted to include random search phrases which are designed to avoid having any influence on the search result.

6. The computer-implemented method of claim 1 , further comprising:
splitting the set of encrypted search queries into a plurality of subsets; and
distributing the subsets among a plurality of search engines.

Assignees

• IBM

Inventors

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

Classifications

• G06F17/30619

  Physics · mapped topic

• G06F17/30657

  Physics · mapped topic

• H04L2463/061

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

• H04L9/14

  using a plurality of keys or algorithms · CPC title

• H04L63/0428

  wherein the data content is protected, e.g. by encrypting or encapsulating the payload · CPC title