System and method for matching data sets while maintaining privacy of each data set

• US 9,443,092 B2
• Filed: 11/18/2014
• Issued: 09/13/2016
• Est. Priority Date: 11/18/2014
• Status: Active Grant

• Current Assignee: Pitney Bowes Incorporated (Böwe Systec AG)
• Original Assignee: Pitney Bowes Incorporated (Böwe Systec AG)
• Inventors: Nawaz, Yassir, Olumofin, Femi
• Primary Examiner(s): Siddiqi, Mohammad A
• Application Number:
  US14/543,959
• Publication Number:
  US 20160140348A1
• Time in Patent Office: 665 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 8/61 Installation
• CPC Class Codes: H04L 2209/46 Secure multiparty computation, e.g. millionaire problem
• CPC Class Codes: H04L 2463/062 applying encryption of the keys cryptographic mechanisms or cryptographic arrangements for key distribution using key encryption key H04L9/0822
• CPC Class Codes: H04L 41/0806 for initial configuration or provisioning, e.g. plug-and-play
• CPC Class Codes: H04L 63/067 using one-time keys cryptographic mechanisms or cryptographic arrangements for generation of one-time passwords H04L9/0863
• CPC Class Codes: H04L 63/0815 providing single-sign-on or federations
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/083 involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]
• CPC Class Codes: H04W 12/04 Key management, e.g. using generic bootstrapping architecture [GBA]

Abstract

A system and method that allows two parties to find common records in their data sets without having to actually share the data sets with each other or a third party. Two primitives, perfect hash functions and public key cryptography, are combined in a unique way to obtain a secure and efficient private matching solution. Since the data that is exchanged is always encrypted during the match process, neither party reveals its data to the other party. This solution enables two parties to match sensitive data such as PII (Personally Identifiable Information) or PHI (Protected Health Information) without having to disclose the data to other or to any third party. One or both of the parties only learn of matching records without learning any information about the records that do not match.

Claims

1. A method for determining matching data elements of a first data set and a second data set without having to disclose the first data set and the second data set:

the method comprising;

generating by a first processing device, a perfect hash function PH_A from the first data set;

evaluating, by the first processing device, the perfect hash function, PH_A(a_i), for each element a_i of the first data set;

encrypting, by the first processing device, each element a_i of the first data set using a public key to form an encryption, E(a_i);

sending, by the first processing device, the public key, the perfect hash function, PH_A(a_i), and the encryption, E(a_i), for each element a_i of the first data set to a second processing device;

evaluating, by the second processing device, the perfect hash function, PH_A (b_j) for each element b_j of the second data set;

finding, by the second processing device, all i such that PH_A(b_j)=PH_A(a_i);

computing, by the second processing device, Z_j=r(E(a_i−

b_j))+E(p), using the received public key and where r is a large random number and p is a predetermined variable that comprises a fixed portion k;

sending, by the second processing device, to the first processing device;

decrypting, by the first processing device using the private key, Z_j; and

determining, by the first processing device, that element of the first data set matches element b_j of the second data set if the decryption of Z_j includes the fixed portion k of p and that element a_i of the first data set does not match element b_j of the second data set if the decryption of Z_j does not include the fixed portion k of p.

2. A method for a first party to determine matching data elements of a first data set maintained by the first party and a second data set maintained by a second party without having to disclose the first data set to the second party or receive the second data set from the second party, the method comprising:

generating, by a first processing device, a perfect hash function PH_A from the first data set;

evaluating, by the first processing device, the perfect hash function, PH_A(a_i), for each element a_i of the first data set;

encrypting, by the first processing device, each element a_i of the first data set using a public key to form an encryption, E(a_i);

sending, by the first processing device, the public key, the perfect hash function, PH_A(a_i), and the encryption, E(a_i), for each element a_i of the first data set one or more second processing devices to evaluate the perfect hash function, PH_A (b_j) for each element b_j of the second data set, find all i such that PH_A(b_j)=PH_A(a_i) and compute Z_j=r(E(a_i−

b_j))+E(p) using the received public key, where r is a large random number and p is a predetermined variable that comprises a fixed portion k;

receiving, from the one or more second processing devices, Z_j=r(E(a_i−

b_j)) E(p);

decrypting, by the first processing device, Z_j; and

determining, by the first processing device, that element a_i of the first data set matches element b_j of the second data set if the decryption of Z_j includes the fixed portion k of p and that element a_i of the first data set does not match element b_j of the second data set if the decryption of Z_j does not include the fixed portion k of p.