Systems and methods for enabling two parties to find an intersection between private data sets without learning anything other than the intersection of the datasets

Abstract

A system and method are disclosed for comparing private sets of data. The method includes encoding first elements of a first data set such that each element of the first data set is assigned a respective number in a first table, encoding second elements of a second data set such that each element of the second data set is assigned a respective number in a second table, applying a private compare function to compute an equality of each row of the first table and the second table to yield an analysis and, based on the analysis, generating a unique index of similar elements between the first data set and the second data set.

We claim: 
     
         1 . A method comprising:
 computing, via a private compare function, an equality of each row of a first table generated from a first data set on a first computing device and each row of a second table generated from a second data set on a second computing device to yield an analysis, wherein the private compare function comprises a table hash function that allows collisions in which more than one value in the first data set hashes to a same slot in the first table or that more than one value in the second data set hashes to a same slot in the second table; and   based on the analysis, generating a unique index of similar elements between the first data set and the second data set.   
     
     
         2 . The method of  claim 1 , wherein the first computing device is independent of the second computing device. 
     
     
         3 . The method of  claim 2 , further comprising:
 encoding, via a first processor associated with the first computing device, first elements of the first data set such that each element of the first data set is assigned a respective number in the first table; and   encoding, via a second processor associated with the second computing device, second elements of the second data set such that each element of the second data set is assigned a respective number in the second table.   
     
     
         4 . The method of  claim 3 , wherein encoding the first elements and encoding the second elements is performed using the table hash function. 
     
     
         5 . The method of  claim 4 , wherein the table hash function is known by a first party associated with the first data set and a second party associated with the second data set. 
     
     
         6 . The method of  claim 3 , wherein the respective number in the first table and the respective number in the second table are a result of applying a public hash function to each element in the first data set and the second data set, wherein the public hash function is publicly known and used by both the first computing device and the second computing device to generate the unique index of similar elements between the first data set and the second data set. 
     
     
         7 . The method of  claim 1 , wherein the unique index of similar elements between the first data set and the second data set comprises an intersection of the first data set and the second data set in a manner that neither the first computing device associated with the first data set nor the second computing device associated with the second data set learns anything other than about the intersection of the first data set and the second data set. 
     
     
         8 . The method of  claim 3 , wherein encoding the first elements further comprises applying a public hash function to generate first indices for the first data set and encoding the second elements further comprises applying the public hash function to generate second indices for the second data set, wherein the public hash function is publicly known and used by both the first computing device and the second computing device to generate the unique index of similar elements between the first data set and the second data set. 
     
     
         9 . The method of  claim 1 , wherein the private compare function comprises a table hash function. 
     
     
         10 . The method of  claim 3 , wherein the encoding of the first elements and the encoding of the second elements is performed using a public hash function, wherein the public hash function is publicly known and used by both the first computing device and the second computing device to generate the unique index of similar elements between the first data set and the second data set. 
     
     
         11 . A system comprising:
 a processor;   a computer-readable storage device storing instructions which, when executed by the processor, cause the processor to perform operations comprising:   computing, via a private compare function, an equality of each row of a first table generated from first data set on a first computing device and each row of a second table generated from second data set on a second computing device to yield an analysis, wherein the private compare function comprises a table hash function that allows collisions in which more than one value in the first data set hashes to a same slot in the first table or that more than one value in the second data set hashes to a same slot in the second table; and   based on the analysis, generating a unique index of similar elements between the first data set and the second data set.   
     
     
         12 . The system of  claim 11 , wherein the first computing device is independent of the second computing device. 
     
     
         13 . The system of  claim 11 , wherein the first computing device is independent of the second computing device. 
     
     
         14 . The system of  claim 11 , wherein the computer-readable storage device stores additional instructions which, when executed by the first processor, cause the first processor to perform operations further comprising:
 encoding first elements of the first data set such that each element of the first data set is assigned a respective number in the first table; and   encoding second elements of the second data set such that each element of the second data set is assigned a respective number in the second table.   
     
     
         15 . The system of  claim 14 , wherein the table hash function is known by a first party associated with the first data set and a second party associated with the second data set. 
     
     
         16 . The system of  claim 14 , wherein the respective number in the first table and the respective number in the second table are a result of applying a public hash function to each element in the first data set and the second data set, wherein the public hash function is publicly known and used by both the first computing device and the second computing device to generate the unique index of similar elements between the first data set and the second data set. 
     
     
         17 . The system of  claim 11 , wherein the unique index of similar elements between the first data set and the second data set comprises an intersection of the first data set and the second data set in a manner that neither the first computing device associated with the first data set nor the second computing device associated with the second data set learns anything other than about the intersection of the first data set and the second data set. 
     
     
         18 . The system of  claim 13 , wherein encoding the first elements further comprises applying a public hash function to generate first indices for the first data set and encoding the second elements further comprises applying the public hash function to generate second indices for the second data set, wherein the public hash function is publicly known and used by both the first computing device and the second computing device to generate the unique index of similar elements between the first data set and the second data set. 
     
     
         19 . The system of  claim 11 , wherein the private compare function comprises a table hash function. 
     
     
         20 . The system of  claim 14 , wherein the encoding of the first elements and the encoding of the second elements is performed using a public hash function, wherein the public hash function is publicly known and used by both the first computing device and the second computing device to generate the unique index of similar elements between the first data set and the second data set.