Delegated private set intersection, and applications thereof
AssigneeQed-It Systems Ltd.
InventorsAurélien Renaud François Nicolas, Daniel Messod Benarroch Guenun, Arbel Deutsch Peled, Ori Wallenstein
Life of this patent
Estimating the term…
Abstract
Embodiments disclosed herein describe computing private set intersection (PSI) between various parties using delegation to other devices and in one round of interaction (request and response). The various parties involved and their associated computing devices are referred to herein as participants. The protocol is forward-secure and completely hides the data of participants from an eavesdropper. Because the protocol only uses a single round of interaction, it is more efficient and does not require each participant to have servers that remain online continuously.
Claims23
A system for determining an intersection between two private data sets, the system comprising:
- one or more processors;
- and
- at least one memory including at least one non-transitory computer-readable medium storing a software application executable by the one or more processors, wherein the software application includes:
- a proxy module configured to receive 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;
- a plurality of delegate modules that together are configured to calculate 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 each delegate module is configured (i) to receive, at a respective delegate module of the plurality of delegate modules, a first intermediate value based on the first value and a second intermediate value based on the second value and (ii) to apply, to the first and second intermediate values received, a partial key private to the respective delegate module to determine next first and second intermediate values such that the next first and second intermediate values are used to determine the first and second keyed hash values;
- and
- a matcher module configured to compare the first and second keyed hash values to determine whether the first and second values match.
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 of the plurality of delegate modules and wherein the virtual private key is a combination of the partial keys private to each of the plurality of delegate modules, wherein the calculating (b) comprises, repeatedly:
- (i) receiving, at a respective delegate module of the plurality of delegate modules, 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 values received, a partial key private to the respective delegate module in (i) to determine next first and second intermediate values such that the next first and second intermediate values are used to determine the first and second keyed hash values;
- and
- (c) comparing the first and second keyed hash values 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 a second keyed hash value of the second value using the virtual private key, wherein each delegate module has a partial key private to respective delegate modules of the plurality of 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 of the plurality of delegate modules, 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 values received, a partial key private to the respective delegate module in (i) to determine next first and second intermediate values such that the next first and second intermediate values are used to determine the first and second keyed hash values;
- and
- (c) comparing the first and second keyed hash values to determine whether the first and second values match.
Dependencies are inferred from the claim text.