Systems and methods for privacy-assured similarity joins over encrypted datasets

Abstract

Systems and methods which provide secure queries with respect to encrypted datasets are described. Embodiments provide privacy-assured similarity join techniques operable with large-scale encrypted datasets. A privacy-assured similarity join technique of embodiments enables a storage system to answer similarity join queries without learning the content of the query dataset and the target dataset. One or more secure query schemes may be implemented in accordance with a privacy-assured similarity join technique herein. For example, embodiments may utilize an individual similarity query scheme, a frequency hiding query scheme, and/or a result sharing query scheme. A particular secure query scheme of the foregoing secure query schemes may be utilized to address different considerations with respect to security, efficiency, and deployability with respect to various applications and scenarios with different requirements.

What is claimed is: 
     
       1. A method for providing secure queries of encrypted datasets, the method comprising:
 storing, by a processor-based storage system, an encrypted similarity index for a source dataset; 
 processing, by the processor-based storage system, secure tokens of a secure query using a similarity join process on the encrypted similarity index to identify one or more pairwise encrypted similar data records, wherein the secure tokens are generated from a query dataset, wherein processing the secure tokens of the secure query using a similarity join process comprises processing the secure tokens over the encrypted similarity index to identify collided data points; and 
 identifying, by the processor-based storage system, a pairwise encrypted similar data record of the one or more pairwise encrypted similar data records as a candidate pair for indicating data of an encrypted dataset relative to the secure query without learning content of the query dataset and the source dataset, wherein identifying the pairwise encrypted similar data record filters the collided data points for identifying the candidate pair by determining that a number of collisions for a data point of the collided data points is greater than a predefined threshold. 
 
     
     
       2. The method of  claim 1 , further comprising:
 generating the encrypted similarity index using a locality-sensitive hashing (LSH) based inverted index, wherein each LSH hash value of the LSH based inverted index are treated as keywords and link to a list of identifiers of data points of the encrypted dataset. 
 
     
     
       3. The method of  claim 2 , wherein generating the encrypted similarity index utilizes a searchable symmetric encryption (SSE) based encrypted dictionary. 
     
     
       4. The method of  claim 2 , wherein the LSH based inverted index includes a set of encrypted key-value pairs stored on top of a dictionary. 
     
     
       5. The method of  claim 1 , further comprising:
 generating a set of secure tokens from query points of the query dataset, wherein the secure tokens of the secure query processed using the similarity join process comprise one or more secure tokens of the set of secure tokens. 
 
     
     
       6. The method of  claim 5 , wherein generating the set of secure tokens from the query points of the query dataset comprises:
 generating the set of secure tokens from LSH hash values of query points of the query dataset. 
 
     
     
       7. The method of  claim 5 , wherein the secure query comprises an individual similarity query in which the one or more secure tokens of the set of secure tokens processed using the similarity join process comprises all secure tokens of the set of secure tokens. 
     
     
       8. The method of  claim 5 , wherein the secure query comprises a frequency hiding query in which the one or more secure tokens of the set of secure tokens processed using the similarity join process comprises a subset of tokens of the set of secure tokens that are not redundant to previous secure queries. 
     
     
       9. The method of  claim 8 , further comprising:
 processing the set of secure tokens to generate the secure query by filtering secure tokens of the set of secure tokens that are redundant to previous secure queries. 
 
     
     
       10. The method of  claim 5 , wherein the secure query comprises a result sharing query in which the one or more secure tokens of the set of secure tokens processed using the similarity join process comprises a secure token for a query data point of the query dataset representative of a plurality of query data points in proximity determined likely to yield similar result sets. 
     
     
       11. The method of  claim 10 , further comprising:
 selecting the query data point of the query dataset; and 
 performing a self-query to identify similar data points of the query dataset that share result sets. 
 
     
     
       12. A system for providing secure queries of encrypted datasets, the system comprising:
 an encrypted similarity index for a source dataset stored by a storage system; and 
 storage system server logic configured to cause one or more processors of the storage system to process secure tokens of a secure query using a similarity join process on the encrypted similarity index, to identify one or more pairwise encrypted similar data records, and to identify a pairwise encrypted similar data record of the one or more pairwise encrypted similar data records as a candidate pair for indicating data of an encrypted dataset relative to the secure query without learning content of a query dataset and the source dataset, wherein the secure tokens are generated from the query dataset, wherein the storage system server logic configured to process the secure tokens of the secure query using a similarity join process is configured to process the secure tokens over the encrypted similarity index to identify collided data points, and wherein the storage system server logic configured to identify the pairwise encrypted similar data record is configured to filter the collided data points for identifying the candidate pair by determining that a number of collisions for a data point of the collided data points is greater than a predefined threshold. 
 
     
     
       13. The system of  claim 12 , further comprising:
 data owner system logic configured to cause one or more processors of a data owner system to generate the encrypted similarity index using a locality-sensitive hashing (LSH) based inverted index, wherein each LSH hash value of the LSH based inverted index are treated as keywords and link to a list of identifiers of data points of the encrypted dataset. 
 
     
     
       14. The system of  claim 13 , wherein the data owner system logic configured to cause the one or more processors of the data owner system to generate the encrypted similarity index utilizes a searchable symmetric encryption (SSE) based encryption dictionary. 
     
     
       15. The system of  claim 13 , wherein the LSH based inverted index includes a set of encrypted key-value pairs stored on top of a dictionary. 
     
     
       16. The system of  claim 12 , further comprising:
 client system logic configured to cause one or more processors of a client system to generate a set of secure tokens from query points of the query dataset, wherein the secure tokens of the secure query processed by the storage system server logic using the similarity join process comprise one or more secure tokens of the set of secure tokens. 
 
     
     
       17. The system of  claim 16 , wherein the client system logic configured to cause the one or more processors of the client system to generate the set of secure tokens from the query points of the query dataset is further configured to cause the one or more processors of the client system to generate the set of secure tokens from LSH hash values of query points of the query dataset. 
     
     
       18. The system of  claim 16 , wherein the secure query comprises an individual similarity query and the storage system server logic is configured to use all secure tokens of the set of secure tokens in the similarity join process. 
     
     
       19. The system of  claim 16 , wherein the secure query comprises a frequency hiding query and the storage system server logic is configured to use a subset of tokens of the set of secure tokens in the similarity join process, wherein the subset of tokens comprise secure tokens that are not redundant to previous secure queries. 
     
     
       20. The system of  claim 19 , wherein the client system logic is further configured to process the set of secure tokens to generate the secure query by filtering secure tokens of the set of secure tokens that are redundant to previous secure queries. 
     
     
       21. The system of  claim 16 , wherein the secure query comprises a result sharing query and the client system logic is configured to a secure token for a query data point of the query dataset representative of a plurality of query data points in proximity determined likely to yield similar result sets. 
     
     
       22. The system of  claim 21 , wherein the client system logic is further configured to select the query data point of the query dataset and perform a self-query to identify similar data points of the query dataset that share result sets. 
     
     
       23. A method for providing secure queries of encrypted datasets, the method comprising:
 storing an encrypted similarity index for a source dataset, wherein the encrypted similarity index is generated using a locality-sensitive hashing (LSH) based inverted index and a searchable symmetric encryption (SSE) based encrypted dictionary; 
 processing secure tokens of a secure query using a similarity join process on the encrypted similarity index to identify one or more pairwise encrypted similar data records from collided data points, wherein the secure tokens are generated from a query dataset using LSH hash values of query points of the query dataset; and 
 identifying a pairwise encrypted similar data record of the one or more pairwise encrypted similar data records as a candidate pair using a predefined threshold of collisions for a data point of the collided data points. 
 
     
     
       24. The method of  claim 23 , wherein each LSH hash value of the LSH based inverted index are treated as keywords and link to a list of identifiers of data points of an encrypted dataset, and wherein the LSH based inverted index includes a set of encrypted key-value pairs stored on top of a dictionary. 
     
     
       25. The method of  claim 23 , wherein the secure query comprises an individual similarity query in which the secure tokens of a set of secure tokens processed using the similarity join process comprises all secure tokens of the set of secure tokens. 
     
     
       26. The method of  claim 23 , wherein the secure query comprises a frequency hiding query in which the secure tokens of a set of secure tokens processed using the similarity join process comprises a subset of tokens of the set of secure tokens that are not redundant to previous secure queries. 
     
     
       27. The method of  claim 26 , further comprising:
 processing the set of secure tokens to generate the secure query by filtering secure tokens of the set of secure tokens that are redundant to previous secure queries. 
 
     
     
       28. The method of  claim 23 , wherein the secure query comprises a result sharing query in which the secure tokens of a set of secure tokens processed using the similarity join process comprises a secure token for a query data point of the query dataset representative of a plurality of query data points in proximity determined likely to yield similar result sets. 
     
     
       29. The method of  claim 28 , further comprising:
 selecting the query data point of the query dataset; and 
 performing a self-query to identify similar data points of the query dataset that share result sets.