Department of Computer Sciences Secure Set Intersection Protocols for Databases CS526 Research Report Presented by Ilya Figotin Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences Secure Set Intersection He should be smart good looking funny Does he have some traits from my list Can I find it out without letting him know what I m looking for Purdue University is an Equal Opportunity Equal Access institution I am good looking funny strong tall Department of Computer Sciences Motivating Applications E commerce Two companies may wish to find common customers without revealing any other information Healhcare Sharing patient s records We can not reveal additional information by law Government organizations Data mining in general Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences Motivations Continued There is a number of Secure Set Protocols available Can we implement some of these in practice What are the main ideas What are the constrains What are the differences Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences Problem Statement Alice owns a relation list A Bob owns a relation list B We may assume that lists contain values of some common attribute of two relations Secure Set Intersection or Private Matching Protocol is a two party protocol which at the end lets Alice to find the intersection of A and B without revealing any additional information to either parties Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences Problem Statement This is somewhat unfair since the result is returned only to Alice There are other variations of the problem where intersection is returned to both parties or when some additional information is revealed such as the sizes of relations lists Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences A note on set elements vs database tuples Note that we can represent each tuple in the relation as a number Therefore an algorithm may only consider lists of numbers if needed The only problem with applicability is then scalabitly i e time complexity of the algorithm and the constants involved Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences Types of Secure Set Intersection Protocols Absolutely secure no info is revealed except for the result itself Secure Multiparty Computation Solution Third party peers solution Less secure may reveal some additional categories of information such as set sizes Based on Commutative encryption Based on Homomorphic ecnryption Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences Higly Secure Protocols Actually do not reveal ANY additional information except from the information which can be inferred from the result itself Parties are assumed to either follow the protocol properly but be curious or to be malicious and do not follow protocol These protocols are expensive due to the reliance on such tools as zero knowledge proofs oblivious transfers etc Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences Highly Secure Solutions Secure Set Intersection via Secure Multiparty Computation Idea represent the function to compute i e intersection function as a boolean circuit Evaluate circuit securely This is prohibitive for large databases since the circuit size depend on the input size Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences Highly Secure Solutions There is a specialized and more efficient solution Emekci et al Use peer to peer third parties Distribute the shares of your secret input i e input list to n parties such that we need at least k parties to reconstruct the secret Shamir s method This allows parties to calculate the result Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences Solutions that reveal additional information We may reveal such information as set size in some cases This may improve the efficiency of a specialized protocol Two major ideas in the literature Use commutative encryption Use homomorphic encryption Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences Commutative Encryption Solutions f and g are commutative encryption functions if f g x g f x Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences Commutative Encryption Protocol due to Agrawal et al Assume Alice has f Bob has g Alice computes f A and sends it to Bob Bob computes g B and g f A and send back to Alice Alice computes f g B g f B and finds g f B g f A Since she knows the order of elements in g f A she can find the intersection This solution requires linear communication complexity This can be easily applied to databases Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences Additive Homomorphic Encryption E is an additive homomorphic encryption if Knowing E a and E b we can obtain E a b as E a E b For a constant c if E a is known we can obtain E c a as c E a Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences Solutions utilizing Homomorphic Encryption due to Kissner et al Assume sets are of size n and consist of numbers Represent each element as a root of polynomial of degree n E g Alice constructs Pa x and Bob constructs Pb x If r is in both lists Pa r Pb r 0 Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences Solutions utilizing Homomorphic Encryption due to Kissner et al Homomorphic encryption allows parties to manipulate polynomials while these are encrypted Therefore based on the previous observations the parties may securely obtain the solution The algorithm also takes linear communication complexity Purdue University is an Equal Opportunity Equal Access institution Department of Computer Sciences Concluding Remarks Secure Set Intersection protocols are beneficial to variety of applications ecommerce healthcare etc If one needs higher security and is not willing to reveal any info use solution due to Emekci et al For applications where we can reveal sizes of datasets use Commutative encryption solution Agrawal et al Homomorphic encryption