Techniques for searching encrypted files

Abstract

Techniques for efficiently searching encrypted searchable spaces. For example, embodiments of the present invention provide techniques for searching a plurality of files that are stored in encrypted (or ciphertext) form. According to embodiments of the present invention, the search can usually be performed by decrypting only a portion of the encrypted searchable space. According to an embodiment of the present invention, the search techniques determine a set of files comprising one or more files from the plurality of encrypted files that contain a user-specified query element. The set of files is usually determined by decrypting only a subset of the plurality of encrypted files.

1 . A method of performing a query search over a plurality of encrypted files for which a data structure storing information related to contents of the plurality of encrypted files is provided, the method comprising:
 receiving information identifying a query element;   determining a first set of files that are in the plurality of encrypted files, wherein membership of the first set is based upon the query element and unencrypted information from the data structure, the first set of files comprising less than all of the plurality of encrypted files;   decrypting each file in the first set of files;   searching unencrypted data in each decrypted file in the first set of files using an unencrypted form of the query element;   identifying a second set of files that is a subset of the first set based on matching the unencrypted form of the query element with unencrypted data, wherein the second set of files comprises files that contain the query element and further comprises a fewer set of files for at least one instance of the query element such that the first set of files can contain a document that does not contain the at least one instance of the query element; and   outputting information identifying files in the second set of files.   
   
   
       2 . The method of  claim 1 , wherein at least some of the data structure is encrypted and wherein determining the first set of files that are in the plurality of encrypted files comprises:
 decrypting a portion of the data structure; and   determining the membership of the first set of files based upon the decrypted portion of the data structure.   
   
   
       3 . The method of  claim 1 , wherein the plurality of encrypted files is partitioned into one or more entities, each entity comprising portions of one or more files of the plurality of encrypted files, and wherein the data structure is a structure that includes first mapping information that maps contents of the plurality of encrypted files to one or more entities that contain the contents, and second mapping information that maps each entity to one or more files from the plurality of encrypted files whose portions are included in the entity, wherein the first mapping information is encrypted. 
   
   
       4 . The method of  claim 3 , wherein the one or more entities are of a first size and the first size is user configurable. 
   
   
       5 . The method of  claim 3 , wherein each entity in the one or more entities corresponds to a file in the plurality of encrypted files. 
   
   
       6 . The method of  claim 3 , wherein determining the first set of files from the plurality of encrypted files comprises:
 decrypting first mapping information;   determining, based upon the decrypted first mapping information, a set of one or more entities that contain the query element; and   determining the first set of files from the second mapping information, wherein the first set of files includes one or more files whose portions are included in the set of one or more entities.   
   
   
       7 . The method of  claim 6 , wherein the second mapping information is encrypted and wherein determining the first set of files from the second mapping information comprises:
 decrypting the second mapping information; and   determining the first set of files based upon the decrypted second mapping information.   
   
   
       8 . The method of  claim 1 , wherein the plurality of encrypted files is partitioned into one or more entities, each entity comprising portions of one or more files from the plurality of encrypted files, and wherein the data structure is a structure that includes hashing information and indexing information, wherein the indexing information maps contents of the plurality of encrypted files to one or more entities that contain the contents, the hashing information hashing the query element to a portion of the indexing information, wherein the indexing information is encrypted. 
   
   
       9 . The method of  claim 8 , wherein the one or more entities are of a first size and the first size is user configurable. 
   
   
       10 . The method of  claim 8 , wherein each entity in the one or more entities corresponds to a file in the plurality of encrypted files. 
   
   
       11 . The method of  claim 8 , wherein determining the first set of files from the plurality of encrypted files comprises:
 determining, based upon the hashing information, a portion of the indexing information for the query element;   decrypting the portion of the indexing information;   determining, from the decrypted portion of the indexing information, a set of one or more entities that contain the query element;   accessing mapping information that maps each entity to one or more files from the plurality of encrypted files whose portions are included in the entity; and   determining the first set of files from the mapping information, wherein the first set of files includes one or more files whose portions are included in the set of one or more entities.   
   
   
       12 . The method of  claim 11 , wherein the mapping information is encrypted and wherein determining the first set of files from the mapping information comprises:
 decrypting the mapping information; and   determining the first set of files based upon the decrypted mapping information.   
   
   
       13 . The method of  claim 1 , wherein files included in the first set of files are also included in the second set of files. 
   
   
       14 . A computer program product stored on a computer readable storage medium for performing a query search over a plurality of encrypted files for which a data structure storing information related to contents of the plurality of encrypted files is provided, the computer program product comprising:
 code for receiving information identifying a query element;   code for determining a first set of files that are in the plurality of encrypted files, wherein membership of the first set is based upon the query element and unencrypted information from the data structure, the first set of files comprising less than all of the plurality of encrypted files;   code for decrypting each file in the first set of files;   code for searching unencrypted data in each decrypted file in the first set of files using an unencrypted form of the query element;   code identifying a second set of files that is a subset of the first set based on matching the unencrypted form of the query element with unencrypted data, wherein the second set of files comprises files that contain the query element and further comprises a fewer set of files for at least one instance of the query element such that the first set of files can contain a document that does not contain the at least one instance of the query element; and   code for outputting information identifying files in the second set of files.   
   
   
       15 . The computer program product of  claim 14 , wherein at least some of the data structure is encrypted and wherein the code for determining the first set of files from the plurality of encrypted files comprises:
 code for decrypting a portion of the data structure; and   code for determining the membership of the first set of files based upon the decrypted portion of the data structure.   
   
   
       16 . The computer program product of  claim 14 , wherein the plurality of encrypted files is partitioned into one or more entities, each entity comprising portions of one or more files of the plurality of encrypted files, and wherein the data structure is a structure that includes first mapping information that maps contents of the plurality of encrypted files to one or more entities that contain the contents, and second mapping information that maps each entity to one or more files from the plurality of encrypted files whose portions are included in the entity, wherein the first mapping information is encrypted. 
   
   
       17 . The computer program product of  claim 16 , wherein the code for determining the first set of files from the plurality of encrypted files comprises:
 code for decrypting first mapping information;   code for determining, based upon the decrypted first mapping information, a set of one or more entities that contain the query element; and   code for determining the first set of files from the second mapping information, wherein the first set of files includes one or more files whose portions are included in the set of one or more entities.   
   
   
       18 . A system of performing a query search over a plurality of encrypted files for which a data structure storing information related to contents of the plurality of encrypted files is provided, the system comprising:
 a processor; and   a memory coupled to the processor, wherein the memory is configured to store a plurality of code modules for execution by the processor, the plurality of code modules comprising:   a code module for receiving information identifying a query element;   a code module for determining a first set of files that are in the plurality of encrypted files, wherein membership of the first set is based upon the query element and unencrypted information from the data structure, the first set of files comprising less than all of the plurality of encrypted files;   a code module for decrypting each file in the first set of files;   a code module for searching unencrypted data in each decrypted file in the first set of files using an unencrypted form of the query element;   a code module for identifying a second set of files that is a subset of the first set based on matching the unencrypted form of the query element with unencrypted data, wherein the second set of files comprises files that contain the query element and further comprises a fewer set of files for at least one instance of the query element such that the first set of files can contain a document that does not contain the at least one instance of the query element; and   a code module for outputting information identifying files in the second set of files.   
   
   
       19 . The system of  claim 18 , wherein at least some of the data structure is encrypted and wherein the code module for determining the first set of files from the plurality of encrypted files comprises:
 a code module for decrypting a portion of the data structure; and   a code module for determining the membership of the first set of files based upon the decrypted portion of the data structure.   
   
   
       20 . The system of  claim 18 , wherein the plurality of encrypted files is partitioned into one or more entities, each entity comprising portions of one or more files of the plurality of encrypted files, and wherein the data structure is a structure that includes first mapping information that maps contents of the plurality of encrypted files to one or more entities that contain the contents, and second mapping information that maps each entity to one or more files from the plurality of encrypted files whose portions are included in the entity, wherein the first mapping information is encrypted.