Collusion-resistant outsourcing of private set intersection

A non-transitory computer-readable storage medium coupled to one or more processors and having instructions stored thereon which, when executed by the one or more processors, cause the one or more processors to perform operations for determining a set intersection using a third party, the operations comprising:

• receiving an encrypted first data set from a first entity;
• storing the encrypted first data set;
• receiving an encrypted second data set from a second entity;
• storing the encrypted second data set;
• receiving public encryption information associated with the encrypted first data set and the encrypted second data set;
• storing the public encryption information;
• and
• processing, using the one or more processors, the encrypted first data set and the encrypted second data set to provide the set intersection, wherein:
• Adv
• A
• <
• 1
• poly
• ⁡
• (
• λ
• )
• where:
• γ is a security parameter;
• poly( )refers to any positive polynomial;
• and
• AdvA is provided as an advantage of a first adversary in guessing data elements of the encrypted first data set and is determined based on a probability of the first adversary guessing the data elements and a second adversary guessing the data elements, the first adversary comprising the third party and the second entity, and the second adversary having access to the encrypted first data set and the public encryption information.

A system, comprising:

• a computing device;
• and
• a computer-readable storage device coupled to the computing device and having instructions stored thereon which, when executed by the computing device, cause the computing device to perform operations for determining a set intersection using a third party, the operations comprising:
• storing the encrypted first data set;
• receiving an encrypted second data set from a second entity;
• storing the encrypted second data set;
• receiving public encryption information associated with the encrypted first data set and the encrypted second data set;
• storing the public encryption information;
• and
• processing, using the one or more processors, the encrypted first data set and the encrypted second data set to provide the set intersection, wherein:
• Adv
• A
• <
• 1
• poly
• ⁡
• (
• λ
• )
• where:
• γ is a security parameter;
• poly( )refers to any positive polynomial;
• and
• AdvA is provided as an advantage of a first adversary in guessing data elements of the encrypted first data set and is determined based on a probability of the first adversary guessing the data elements and a second adversary guessing the data elements, the first adversary comprising the third party and the second entity, and the second adversary having access to the encrypted first data set and the public encryption information.