# US 2021/0240841 A1 · Delegated private set intersection, and applications thereof > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2021/0240841 A1 - Document ID: US20210240841A1 - Status: Published application - Kind: A1 - Application number: 17/121,282 - Filed: 2020-12-14 - Published: 2021-08-05 - Earliest claimed: 2020-02-03 - Assignees: Qed-It Systems Ltd. - Applicants: QED-it Systems Ltd. - Inventors: Aurélien Renaud François Nicolas; Daniel Messod BENARROCH GUENUN; Arbel Deutsch PELED; Ori WALLENSTEIN - Web page: https://patentgrep.com/patent/US20210240841A1 ## CPC - G06F 21/602: {Providing cryptographic facilities or services} - G06F 21/6245: {Protecting personal data, e.g. for financial or medical purposes} - H04L 9/008: {involving homomorphic encryption} - H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC} - H04L 9/3221: {interactive zero-knowledge proofs} - H04L 63/0281: {Proxies} - H04L 63/0464: {using hop-by-hop encryption, i.e. wherein an intermediate entity decrypts the information and re-encrypts it before forwarding it} - H04L 9/50: {using hash chains, e.g. blockchains or hash trees} - H04L 2209/76: Proxy, i.e. using intermediary entity to perform cryptographic operations - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## 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. ## Claims ### Claim 1 A system for determining an intersection between two private data sets, the method comprising: 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 the respective delegate module, 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 value received, a partial key private to the respective delegate module 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 a matcher module configured to compare first and second keyed hash value to determine whether the first and second values match. ### Claim 2 (depends on 1) The system of claim 1, wherein the matcher module is a centralized, non-trusted entity. ### Claim 3 (depends on 1) The system of claim 1, wherein the plurality of delegate modules are configured to generate a zero knowledge proof proving that the first and second keyed hash values were correctly calculated. ### Claim 4 (depends on 3) The system of claim 3, wherein the proxy module is configured to validate the proof. ### Claim 5 (depends on 1) The system of claim 1, wherein the proxy module is configured to receive a first private data set comprising the first value and a second private data set comprising the second value, wherein plurality of delegate modules calculate a key hash value for each value in the first and second private data set, and wherein the matcher module compares the calculated key hash values to determine which values in the first and second private data sets match. ### Claim 6 (depends on 1) The system of claim 1, wherein the first and second value are normalized into a common format. ### Claim 7 (depends on 1) The system of claim 1, wherein the applying (ii) comprises applying a collision resistant hash function. ### Claim 8 (depends on 1) The system of claim 1, wherein the applying (ii) comprises applying a collision resistant hash function. ### Claim 9 (depends on 1) The system of claim 1, wherein the first record has a first identifier and the second record has a second identifier, and wherein the matcher module is configured to, when the first and second values are determined to match, select the first identifier to return to the first participant and the second identifier to return to the second participant. ### Claim 10 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. ### Claim 11 (depends on 10) The method of claim 10, wherein comparing (c) is conducted by a centralized, non-trusted entity. ### Claim 12 (depends on 10) The method of claim 10, further comprising generating a zero knowledge proof proving that the first and second keyed hash values were correctly calculated. ### Claim 13 (depends on 10) The method of claim 10, further comprising validating the zero knowledge proof ### Claim 14 (depends on 10) The method of claim 10, wherein the receiving (a) comprises a first private data set comprising the first value and a second private data set comprising the second value, wherein the calculating (b) comprises calculate a key hash value for each value in the first and second private data set, and wherein the matcher module compares the calculated key hash values to determine which values in the first and second private data sets match. ### Claim 15 (depends on 10) The method of claim 10, wherein the first and second values are normalized into a common format. ### Claim 16 (depends on 10) The method of claim 10, wherein the applying (ii) comprises applying a collision resistant hash function. ### Claim 17 (depends on 1) The system of claim 1, wherein the first record has a first identifier and the second record has a second identifier, and further comprising, when the first and second values are determined to match: returning the first identifier to the first participant; and returning the second identifier to return to the second participant. ### Claim 18 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. ### Claim 19 (depends on 18) The device of claim 18, wherein the comparing (c) is conducted by a centralized, non-trusted entity. ### Claim 20 (depends on 18) The device of claim 18, the operations further comprising generating a zero knowledge proof proving that the first and second keyed hash values were correctly calculated. ### Claim 21 (depends on 20) The device of claim 20, the operations further comprising validating the zero knowledge proof. ### Claim 22 (depends on 18) The device of claim 18, wherein the receiving (a) comprises a first private data set comprising the first value and a second private data set comprising the second value, wherein the calculating (b) comprises calculate a key hash value for each value in the first and second private data set, and wherein the matcher module compares the calculated key hash values to determine which values in the first and second private data sets match. ### Claim 23 (depends on 18) The device of claim 18, wherein the first and second values are normalized into a common format. ### Claim 24 (depends on 18) The device of claim 18, wherein the applying (ii) comprises applying a collision resistant hash function.