Delegated private set intersection, and applications thereof

A computer-implemented method for determining an intersection between two private data sets, comprising:

• (a) receiving a first value from a first participant and a second value from a second participant, the first value representing a first record from a first private data set and the second value representing a second record from a second private data set;
• (b) calculating, using a plurality of delegate modules, a first keyed hash value of the first value using a virtual private key and to calculate a second keyed hash value of the second value using the virtual private key, wherein each delegate module has a partial key private to the respective delegate modules and wherein the virtual private key is a combination of the partial keys private to each of the delegate modules, wherein the calculating (b) comprises, repeatedly:
• (i) receiving, at a respective delegate module, a first intermediate value based on the first value and a second intermediate value based on the second value,
• (ii) applying, to the first and second intermediate value received, a partial key private to the respective delegate module in (i) to determine a next first and second intermediate value such that the next first and second intermediate value are used to determine the first and second keyed hash value;
• and
• (c) comparing first and second keyed hash value to determine whether the first and second values match.

A non-transitory computer-readable device having instructions stored thereon that, when executed by at least one computing device, cause the at least one computing device to perform operations for determining an intersection between two private data sets, the operations comprising:

• (a) receiving a first value from a first participant and a second value from a second participant, the first value representing a first record from a first private data set and the second value representing a second record from a second private data set;
• (b) calculating, using a plurality of delegate modules, a first keyed hash value of the first value using a virtual private key and to calculate a second keyed hash value of the second value using the virtual private key, wherein each delegate module has a partial key private to the respective delegate modules and wherein the virtual private key is a combination of the partial keys private to each of the delegate modules, wherein the calculating (b) comprises, repeatedly:
• (i) receiving, at a respective delegate module, a first intermediate value based on the first value and a second intermediate value based on the second value,
• (ii) applying, to the first and second intermediate value received, a partial key private to the respective delegate module in (i) to determine a next first and second intermediate value such that the next first and second intermediate value are used to determine the first and second keyed hash value;
• and
• (c) comparing first and second keyed hash value to determine whether the first and second values match.