Granted Patent B1

US 9,679,160 · App. 14/199,240 · Granted Jun 13, 2017

Abstract

Claims (40)

1. A computer-implemented method for maintaining encrypted search indexes on third-party storage systems, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising:

identifying, at a server-side computing system, a plurality of encrypted files that were previously transmitted from a client-side computing system of a user to the server-side computing system in an unencrypted state, wherein the server-side computing system encrypted and stored each of the plurality of encrypted files;

identifying, at the server-side computing system, a plurality of unencrypted keywords, wherein each of the plurality of unencrypted keywords is contained in at least one of the plurality of encrypted files;

generating, at the server-side computing system, an encrypted search index for searching the plurality of encrypted files by:

identifying, at the server-side computing system for each unencrypted keyword in the plurality of unencrypted keywords, a list of encrypted files in the plurality of encrypted files that contain the unencrypted keyword;

identifying, at the server-side computing system, a single cryptographic key designated for the user;

encrypting, at the server-side computing system, the list of encrypted files of each unencrypted keyword in the plurality of unencrypted keywords using the single cryptographic key designated for the user; and

storing, at the server-side computing system, the encrypted list of encrypted files of each unencrypted keyword in the plurality of unencrypted keywords in association with a lookup key that is generated by applying a pseudo-random function to the unencrypted keyword associated with the encrypted list of encrypted files;

receiving, at the server-side computing system, a request from the user to search the plurality of encrypted files for a search keyword;

generating, at the server-side computing system, a lookup key from the search keyword by applying the pseudo-random function to the search keyword;

using the lookup key generated from the search keyword to identify, at the server-side computing system, an encrypted list of encrypted files associated with the search keyword;

decrypting, at the server-side computing system, the encrypted list of encrypted files associated with the search keyword using the single cryptographic key designated for the user;

using, at the server-side computing system, the decrypted list of encrypted files associated with the search keyword to generate a response to the request from the user.

2. The method of claim 1 , wherein the step of identifying the plurality of unencrypted keywords is performed as part of encrypting the plurality of encrypted files.

3. The method of claim 1 , further comprising detecting the deletion of at least one encrypted file contained in the encrypted list of encrypted files associated with the search keyword, wherein using the decrypted list of encrypted files associated with the search keyword to generate the response to the request from the user comprises ensuring that the deleted encrypted file is not included in the response.

4. The method of claim 3 , further comprising updating the list of encrypted files associated with the search keyword to reflect the deletion of the encrypted file.

5. The method of claim 1 , wherein identifying the plurality of unencrypted keywords comprises extracting the plurality of unencrypted keywords from the plurality of encrypted files after using the single cryptographic key designated for the user to decrypt the plurality of encrypted files.

6. The method of claim 1 , wherein encrypting the list of encrypted files of each unencrypted keyword in the plurality of unencrypted keywords comprises encrypting the list of encrypted files of each unencrypted keyword in the plurality of unencrypted keywords using a mode of operation with a randomized counter.

7. The method of claim 6 , wherein encrypting the list of encrypted files of each unencrypted keyword in the plurality of unencrypted keywords comprises generating the randomized counter by applying the pseudo-random function to the unencrypted keyword.

8. The method of claim 1 , wherein storing the encrypted list of encrypted files of each unencrypted keyword in the plurality of unencrypted keywords comprises storing the encrypted list of each unencrypted keyword in the plurality of unencrypted keywords in a data structure that maps lookup keys to lists of encrypted files.

9. The method of claim 8 , wherein the data structure comprises a hash table.

10. A system for maintaining encrypted search indexes on third-party storage systems, the system comprising:

a file-identifying module, stored in memory, that identifies, at a server-side computing system, a plurality of encrypted files that were previously transmitted from a client-side computing system of a user to the server-side computing system in an unencrypted state, wherein the server-side computing system encrypted and stored each of the plurality of encrypted files;

a keyword-identifying module, stored in memory, that identifies, at the server-side computing system, a plurality of unencrypted keywords, wherein each of the plurality of unencrypted keywords is contained in at least one of the plurality of encrypted files;

a generating module, stored in memory, that generates, at the server-side computing system, an encrypted search index for searching the plurality of encrypted files by:

identifying, at the server-side computing system for each unencrypted keyword in the plurality of unencrypted keywords, a list of encrypted files in the plurality of encrypted files that contain the unencrypted keyword;

identifying, at the server-side computing system, a single cryptographic key designated for the user;

encrypting, at the server-side computing system, the list of encrypted files of each unencrypted keyword in the plurality of unencrypted keywords using the single cryptographic key designated for the user; and

storing, at the server-side computing system, the encrypted list of encrypted files of each unencrypted keyword in the plurality of unencrypted keywords in association with a lookup key that is generated by applying a pseudo-random function to the unencrypted keyword associated with the encrypted list of encrypted files; and

at least one processor that executes the file-identifying module, the keyword-identifying module, and the generating module.

11. The system of claim 10 , further comprising:

a search-index identifying module, stored in memory, that identifies, as part of a plugin of a search engine, a search index used by the search engine, wherein:

the search index comprises a plurality of data chunks;

each of the plurality of data chunks comprises one or more data blocks; and

a search-index initialization vector is designated for encrypting the search index; and

a search-index encrypting module, stored in memory, that encrypts, as part of the plugin of the search engine, the search index by, for each data chunk in the plurality of data chunks:

calculating an initialization vector for encrypting the data chunk such that no two data chunks in the plurality of data chunks have identical initialization vectors by:

calculating a unique nonce for the data chunk; and

calculating the initialization vector by summing the search-index initialization vector with a product of the unique nonce and a number of the one or more data blocks; and

using the initialization vector to encrypt the data chunk.

Assignments (18)