Systems and methods for generating and processing secure search queries

Patent metadata

Field	Value
Publication number	US-11775683-B2
Application number	US-202117385355-A
Country	US
Kind code	B2
Filing date	Jul 26, 2021
Priority date	Mar 12, 2019
Publication date	Oct 3, 2023
Grant date	Oct 3, 2023

Abstract

Generating a first signature value corresponding to a first dataset stored in a first data region having a first access permission level. Determining a signature anonymization value. Truncating the first signature value based on the signature anonymization value. Generating a secure search query for identifying, based on the truncated first signature value, second signature values corresponding to entries of a second dataset stored in one or more second data regions having one or more second access permission levels. Receiving a response to the secure search query including the plurality of second signature values. Determining the entries of the second dataset from the second signature values. Comparing the respective entries of the second dataset to the at least a portion of the first dataset. Generating one or more notifications based on the comparisons indicating a potential match between a particular respective entry of the second dataset and the at least a portion of a first dataset.

First claim

The invention claimed is:

1. A system comprising:
one or more processors; and
a memory storing instructions that, when executed by the one or more processors, cause the system to perform:
generating a signature value corresponding to a search term by applying a cryptographic hash function on the search term, wherein the search term corresponds to a portion of a dataset;
truncating the signature value by truncating a number of characters from the signature value, wherein the number of characters to be truncated from the signature value is determined based on a number of entries in the dataset such that a length of the truncated signature value increases when the number of entries in the dataset is larger;
generating, based on the truncated signature value, a secure search query for the search term with which to search the dataset;
receiving a response to the secure search query, wherein the response comprises second signature values corresponding to respective selected entries of the dataset that are associated with the truncated signature value;
disambiguating the second signature values based on the cryptographic function to reveal the selected entries of the dataset that are associated with the truncated signature value; and
removing, from the selected entries, false positive results that correspond to the truncated signature value and fail to correspond to the signature value.

2. The system of claim 1 , wherein each of the second signature values comprises a hash value.

3. The system of claim 1 , wherein the second signature values comprise respective untruncated hash values, and wherein respective subsets of the untruncated hash values match the truncated signature value.

4. The system of claim 3 , wherein the removal of the false positive results comprises determining respective subsets of the untruncated hash values that match the truncated signature value but fail to match the signature value and removing the selected entries corresponding to the respective subsets of the untruncated hash values that fail to match the signature value.

5. The system of claim 1 , wherein the instructions that, when executed by the one or more processors, cause the system to perform:
storing the dataset, the signature value, and the truncated signature value in a region; and
restricting the dataset and the signature value from being transmitted out of the region while permitting the truncated signature value to be transmitted out of the region.

6. The system of claim 1 , wherein the dataset has a heightened security constraint compared to an other dataset.

7. A method comprising:
generating a signature value corresponding to a search term by applying a cryptographic hash function on the search term, wherein the search term corresponds to a portion of a dataset;
truncating the signature value by removing a number of characters from the signature value, wherein the number of characters to be truncated from the signature value is determined based on a number of entries in the dataset such that a length of the truncated signature value increases when the number of entries in the dataset is larger;
generating, based on the truncated signature value, a secure search query for the search term with which to search the dataset;
receiving a response to the secure search query, wherein the response comprises second signature values corresponding to respective selected entries of the dataset that are associated with the truncated signature value;
disambiguating the second signature values based on the cryptographic function to reveal the selected entries of the dataset that are associated with the truncated signature value; and
removing, from the selected entries, false positive results that correspond to the truncated signature value and fail to correspond to the signature value.

8. The method of claim 7 , wherein each of the second signature values comprises a hash value.

9. The method of claim 7 , wherein the second signature values comprise respective untruncated hash values, and wherein respective subsets of the untruncated hash values match the truncated signature value.

10. The method of claim 9 , wherein the removal of the false positive results comprises determining respective subsets of the untruncated hash values that match the truncated signature value but fail to match the signature value and removing the selected entries corresponding to the respective subsets of the untruncated hash values that fail to match the signature value.

11. The method of claim 7 , further comprising:
storing the dataset, the signature value, and the truncated signature value in a region; and
restricting the dataset and the signature value from being transmitted out of the region while permitting the truncated signature value to be transmitted out of the region.

12. The method of claim 7 , wherein the dataset has a heightened security constraint compared to an other dataset.

13. A non-transitory computer readable medium comprising instructions that, when executed, cause one or more processors to perform:
generating a signature value corresponding to a search term by applying a cryptographic hash function on the search term, wherein the search term corresponds to a portion of a dataset;
truncating the signature value by removing a number of characters from the signature value, wherein the number of characters to be truncated from the signature value is determined based on a number of entries in the dataset such that a length of the truncated signature value increases when the number of entries in the dataset is larger;
generating, based on the truncated signature value, a secure search query for the search term with which to search the dataset;
receiving a response to the secure search query, wherein the response comprises second signature values corresponding to respective selected entries of the dataset that are associated with the truncated signature value;
disambiguating the second signature values based on the cryptographic function to reveal the selected entries of the dataset that are associated with the truncated signature value; and
removing, from the selected entries, false positive results that correspond to the truncated signature value and fail to correspond to the signature value.

14. The non-transitory computer readable medium of claim 13 , wherein each of the second signature values comprises a hash value.

15. The non-transitory computer readable medium of claim 13 , wherein the second signature values comprise respective untruncated hash values, and wherein respective subsets of the untruncated hash values match the truncated signature value.

16. The non-transitory computer readable medium of claim 15 , wherein the removal of the false positive results comprises determining respective subsets of the untruncated hash values that match the truncated signature value but fail to match the signature value and removing the selected entries corresponding to the respective subsets of the untruncated hash values that fail to match the signature value.

17. The non-transitory computer readable medium of claim 13 , wherein the instructions that, when executed, cause one or more processors to perform:
storing the dataset, the signature value, and the truncated signature value in a region; and
restricting the dataset and the signature value from being transmitted out of the region while permitting the truncated signature value to be transmitted out of the region.

Assignees

• Palantir Technologies Inc

Inventors

• Doyle John
• Free Jason
• Magid Jacob
• Rochlin Michael
• Hacker Sean

Classifications

• G06F21/6254 Primary

  by anonymising data, e.g. decorrelating personal data from the owner's identification · CPC title

• G06F16/9014

  hash tables · CPC title

• G06F16/90335

  Query processing · CPC title

• G06F21/602

  Providing cryptographic facilities or services · CPC title

• H04L63/105

  Multiple levels of security · CPC title