US 8,819,451 B2Granted

Techniques for representing keywords in an encrypted search index to prevent histogram-based attacks

AssigneeMicrosoft Corporation

InventorsSatyanarayana V. Lokam, Ajay Manchepalli, Balasubramanyan Ashok, Sandeep P. Karanth, Raghav Bhaskar

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method and system for cryptographically indexing, searching for, and retrieving documents is provided. In some embodiments, an encryption system is provided that generates a document index that allows users to retrieve documents by performing encrypted queries for keywords associated with the documents. In some embodiments, each keyword maps to the same number of encrypted document identifiers. In some embodiments, an extractor graph is employed to map an indication of each keyword to a number of buckets storing encrypted document identifiers. In some embodiments, an order-preserving encryption system is provided. The encryption system uses an ordered index that maps encrypted instances of ordered attribute values to documents that are associated with those values. The ordered index enables queries containing query operators that rely on order, such as less than (“<”) or greater than (“>”), to be successfully performed on encrypted attribute values.

Claims21

Dependent claims

A method in a networked computer system having a memory and a processor for searching for documents, the method comprising:

generating a searchable encrypted keyword index for a plurality of documents by
identifying a plurality of keywords, and
for each of the identified plurality of keywords,
encrypting the keyword to generate an encrypted instance of the keyword;
identifying the documents that contain the keyword,
for each of the identified documents,
determining a document identifier,
with a processor, generating a concatenated string by sequentially joining a string of the keyword to a string of the determined document identifier into the concatenated string, and
encrypting the concatenated string by applying an encryption function to the concatenated string, and
sending to a document storage service the encrypted instance of the keyword along with each of the encrypted concatenated strings wherein the document storage server associates the encrypted instance of the keyword with each of the encrypted concatenated strings that is an encryption of that keyword concatenated with a document identifier;
and
identifying an encrypted document that matches a query by
inputting a keyword received from a user,
encrypting the inputted keyword to generate an encrypted instance of the inputted keyword,
sending the encrypted instance of the inputted keyword to the document storage service,
receiving from the document storage service at least one encrypted concatenated string associated with the encrypted instance of the inputted keyword, and
decrypting the received at least one encrypted concatenated string to identify both the keyword of the encrypted concatenated string and the document identifier of the encrypted concatenated string.

14 more elements

A computing system configured to process a query, the computing system comprising:

a memory storing computer-executable instructions of:
a mapping component configured to, for each of a plurality of keywords,
identify documents associated with that keyword,
for each of the identified documents,
determine a document identifier associated with that document,
generate a concatenated string by concatenating an indication of that keyword to the document identifier to sequentially join a string of the keyword and a string of the document identifier into a single string that is the concatenated string,
encrypt the concatenated string, and
cause to be stored at a document storage server an association of that keyword to the encrypted concatenated string;
a query component configured to submit an indication of search terms to the document storage server;
a receive component configured to receive a plurality of encrypted concatenated strings from the document storage server;
a decrypt component configured to, for each of the plurality of received encrypted concatenated strings,
decrypt that encrypted concatenated string, and
retrieve a document identifier from the decrypted concatenated string, and
a display component configured to display an indication of the retrieved document identifiers;
and
a processor that executes the computer-executable instructions stored in the memory.

13 more elements

A computer-readable storage device storing computer-executable instructions for causing a computing device to generate encrypted keyword-document identifier pairs for an index, by a method comprising:

for each of a plurality of keywords,
identifying the documents that contain the keyword;
for each of the identified documents,
retrieving a document identifier for the document;
generating keyword-document identifier pair that contains the keyword and the retrieved document identifier as a combined string formed by sequentially joining a string of the keyword and a string of the retrieved document identifier;
and
encrypting the generated keyword-document identifier pair by applying an encryption function to the combined string such that the keyword and the retrieved document identifier of the combined string are encrypted as a single combined string so that the keyword and the retrieved document identifier of the encrypted keyword-document identifier pair cannot be separately decrypted;
and
sending to a document storage service a mapping of each of the plurality of keywords to the one or more encrypted keyword-document identifier pairs that contain the keyword of the encrypted keyword-document identifier pairs.

6 more elements

Dependencies are inferred from the claim text.