Third-party private set intersection with communication and computational efficiency
A private set intersection protocol in which a third party may determine intersections of a first set of a first party and a second set of a second party. The third party may not obtain any information regarding the first set or the second set other than the intersection result. The protocol may be communicatively efficient and computationally efficient to allow for secure private set intersection to be performed.
1 . A method for determining a private set intersection of respective sets of a first party and a second party by a third party, comprising:
receiving, at the third party, first information regarding a first key set generated by the first party using a key agreement protocol between the first party and the second party, the first key set comprising encoded keys for elements of a first set of the first party;
receiving, at the third party, second information regarding a second key set generated by the second party using the key agreement protocol between the first party and the second party, the second key set comprising encoded keys for elements of a second set of the second party; and
calculating, at the third party, solutions to an equation based on the first information and the second information, the solutions to the equation correspond to common elements of the respective sets of the first party and the second party, wherein the third party obtains no other information regarding the first set or the second set, and wherein the first party and the second party do not obtain information regarding the common elements of the respective sets during the determining the private set intersection by the third party or any information regarding the elements of a set of another participating party during the determining the private set intersection.
2 . The method of claim 1 , wherein the first information comprises a random shuffle of the first key set of the first party and the second information comprises a polynomial function that interpolates the second key set of the second party, and wherein the calculating comprises determining all solutions to the equation that equates the polynomial function to the random shuffle of the first key set.
3 . The method of claim 1 , wherein the first information comprises a first polynomial function that interpolates the first key set of the first party and the second information comprises a second polynomial function that interpolates the second key set of the first party, and wherein the calculating comprises determining all solutions to the equation that the first polynomial function subtracted from the second polynomial function equals zero.
4 . The method of claim 1 , further comprising:
receiving a first plurality of first communications from the first party, each of the first plurality of first communications comprising information regarding a subset of elements of the first set and one or more dummy elements, the first plurality of first communications collectively comprising the first information regarding an entirety of the first set;
receiving a second plurality of second communications from the second party, each of the second plurality of second communications comprising information regarding a subset of elements of the second set and one or more dummy elements, the second plurality of second communications collectively comprising the second information regarding an entirety of the second set; and
calculating solutions to a plurality of equations each based on respective ones of the first plurality of first communications and the second plurality of second communications, wherein the calculating iterates over the first plurality of communications and the second plurality of communications to determine the common elements of the respective sets of the first party and the second party.
5 . The method of claim 1 , wherein the key agreement protocol comprises a two-round key agreement protocol in which:
the first party generates a first message based on a random value within a space of randomness that the second party uses, in combination with respective random values from the space of randomness, to generate a plurality of second messages for elements of the second set,
the second party computes a unique polynomial function that interpolates the second messages, the unique polynomial function being sent to the first party,
the first party generates the first information based on the unique polynomial function, and
the second information is based on the plurality of second messages.
6 . The method of claim 1 , wherein computational complexity of the determining the private set intersection of respective sets of the first party and the second party by the third party approaches linearity.
7 . The method of claim 1 , wherein the first information is received at the third party for each of a plurality of first buckets of the first party, the plurality of first buckets comprising a distribution of the elements of the first set into the plurality of buckets.
8 . The method of claim 7 , wherein the first information is computed for each of the plurality of first buckets, wherein the key agreement protocol is used by the first party and the second party relative to each of the plurality of first buckets to compute the first information for each of the plurality of first buckets.
9 . The method of claim 7 , wherein the distributing comprises applying a hash function to the elements of the first party to hash the elements of the first set into the plurality of first buckets.
10 . The method of claim 7 , wherein the plurality of first buckets contain no more than an upper threshold number of elements of the first set and no less than a lower threshold number of elements of the first set.
11 . The method of claim 10 , wherein the upper threshold number of elements and the lower threshold number of elements are based on a distribution parameter based on a security parameter and a number of elements in the first set.
12 . The method of claim 1 , wherein the second information is received at the third party for each of a plurality of second buckets of the second party, the plurality of second buckets comprising a distribution of the elements of the second set into the plurality of second buckets.
13 . The method of claim 12 , wherein the second information is received at the second party for each of a plurality of second buckets of the second party, wherein the key agreement protocol is used by the first party and the second party relative to each of the plurality of second buckets to compute the second information for each of the plurality of second buckets.
14 . The method of claim 13 , wherein the distributing comprises applying a hash function to the elements of the first party to hash the elements of the second set into the plurality of second buckets.
15 . The method of claim 13 , wherein the plurality of second buckets contain no more than an upper threshold number of elements of the second set and no less than a lower threshold number of elements of the second set.
16 . The method of claim 15 , wherein the upper threshold number of elements and the lower threshold number of elements are based on a distribution parameter based on a security parameter and a number of elements in the second set.
17 . The method of claim 1 , wherein communication between the first party and the second party is not greater than three times a number of elements in a given party's set.
18 . The method of claim 1 , wherein the equation based on the first information and the second information is of a degree less than a number of elements in the first set or the second set.