Privacy preserving data search
Database entries can be protected by indexing the entries using a plurality of indexes, each associated with a level of access rights. A level of access rights can be determined from a search query, and an index can be selected based on the determined level of access rights. A search key can be generated based on the received query, and the selected index can be searched using the search query. Database entries mapped to the values of the selected index returned in response to the search can be outputted. Each index is associated with a different granularity defining the number and/or ambiguity of search results returned in response to searching an index.
1. A method for data protection in a computer system associated with a plurality of levels of access rights, the method comprising:
indexing a portion of a database stored in memory with a plurality of indexes, each index including a plurality of values each mapped to a different one or more database entries, each index associated with a different access rights level;
receiving a query to search the indexed portion of the database from a user;
generating, by a hardware processor, a search key based on the received query;
hashing the generated search key using a hash table;
hashing, for each index, the values of an index corresponding to an access rights level associated with the user using the hash table;
truncating the hashed search key and each hashed index value, wherein truncating the hashed search key comprises maintaining a leading portion of the hashed search key and discarding the remainder of the hashed search key;
after truncating the hashed search key and the hashed index values, searching, by the hardware processor, the truncated hashed index values using the truncated hashed search key to identify truncated hashed index values associated with the truncated hashed search key; and
outputting database entries mapped to the identified truncated hashed index values.
2. The method of claim 1 , wherein each index of the plurality of indexes is associated with an index granularity defined by an average number of database entries mapped to the same index value.
3. The method of claim 2 , wherein a first access rights level associated with a first index of a first granularity is associated with a greater amount of permissible access to the database than a second access rights level associated with a second index of a second granularity lower than the first granularity.
4. The method of claim 3 , further comprising:
selecting the first index for hashing responsive to a determination that the user is associated with the first access rights level; and
selecting the second index for hashing responsive to a determination that the user is associated with the second access rights level.
5. The method of claim 1 , wherein the database entries are encrypted, and further comprising:
decrypting the outputted database entries.
6. The method of claim 1 , wherein the generated search key is based on text included within the received query.
7. A information retrieval system associated with a plurality of levels of access rights, the system comprising:
a non-transitory computer-readable storage medium storing executable computer instructions that, when executed, perform steps comprising:
indexing a portion of a database stored in memory with a plurality of indexes, each index including a plurality of values each mapped to a different one or more database entries, each index associated with a different access rights level;
receiving a query to search the indexed portion of the database from a user;
generating a search key based on the received query;
hashing the generated search key using a hash table;
hashing, for each index, the values of an index corresponding to an access rights level associated with the user using the hash table;
truncating the hashed search key and each hashed index value, wherein truncating the hashed search key comprises maintaining a leading portion of the hashed search key and discarding the remainder of the hashed search key;
after truncating the hashed search key and the hashed index values, searching, by the hardware processor, the truncated hashed index values using the truncated hashed search key to identify truncated hashed index values associated with the truncated hashed search key; and
outputting database entries mapped to the identified truncated hashed index values; and
a hardware processor configured to execute the instructions.
8. The system of claim 7 , wherein each index of the plurality of indexes is associated with an index granularity defined by an average number of database entries mapped to the same index value.
9. The system of claim 8 , wherein a first access rights level associated with a first index of a first granularity is associated with a greater amount of permissible access to the database than a second access rights level associated with a second index of a second granularity lower than the first granularity.
10. The system of claim 9 , wherein the instructions, when executed, are further configured to perform steps comprising:
selecting the first index for hashing responsive to a determination that the user is associated with the first access rights level; and
selecting the second index for hashing responsive to a determination that the user is associated with the second access rights level.
11. The system of claim 7 , wherein the database entries are encrypted, and wherein the instructions, when executed, are further configured to perform steps comprising:
decrypting the outputted database entries.
12. The system of claim 7 , wherein the generated search key is based on text included within the received query.
13. A non-transitory computer-readable storage medium storing executable computer instructions that, when executed, are configured to perform steps comprising:
indexing a portion of a database stored in memory with a plurality of indexes, each index including a plurality of values each mapped to a different one or more database entries, each index associated with a different access rights level;
receiving a query to search the indexed portion of the database from a user;
generating a search key based on the received query;
hashing the generated search key using a hash table;
hashing, for each index, the values of an index corresponding to an access rights level associated with the user using the hash table;
truncating the hashed search key and each hashed index value, wherein truncating the hashed search key comprises maintaining a leading portion of the hashed search key and discarding the remainder of the hashed search key;
after truncating the hashed search key and the hashed index values, searching, by the hardware processor, the truncated hashed index values using the truncated hashed search key to identify truncated hashed index values associated with the truncated hashed search key; and
outputting database entries mapped to the identified truncated hashed index values.
14. The non-transitory computer-readable storage medium of claim 13 , wherein each index of the plurality of indexes is associated with an index granularity defined by an average number of database entries mapped to the same index value.
15. The non-transitory computer-readable storage medium of claim 14 , wherein a first access rights level associated with a first index of a first granularity is associated with a greater amount of permissible access to the database than a second access rights level associated with a second index of a second granularity lower than the first granularity.
16. The non-transitory computer-readable storage medium of claim 15 , wherein the instructions, when executed, are further configured to perform steps comprising:
selecting the first index for hashing responsive to a determination that the user is associated with the first access rights level; and
selecting the second index for hashing responsive to a determination that the user is associated with the second access rights level.
17. The non-transitory computer-readable storage medium of claim 13 , wherein the database entries are encrypted, and wherein the instructions, when executed, are further configured to perform steps comprising:
decrypting the outputted database entries.
18. The non-transitory computer-readable storage medium of claim 13 , wherein the generated search key is based on text included within the received query.