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

Patent metadata

Field	Value
Publication number	US-2016140348-A1
Application number	US-201414543959-A
Country	US
Kind code	A1
Filing date	Nov 18, 2014
Priority date	Nov 18, 2014
Publication date	May 19, 2016
Grant date	—

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.

First claim

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, Z j 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 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.

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.

Assignees

• Pitney Bowes Inc

Inventors

• Nawaz Yassir
• Olumofin Femi

Classifications

• H04L67/10

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• H04L41/0806

  for initial configuration or provisioning, e.g. plug-and-play · CPC title

• H04L2209/46

  Secure multiparty computation, e.g. millionaire problem · CPC title

• H04L67/02

  based on web technology, e.g. hypertext transfer protocol [HTTP] · CPC title

• H04L63/145

  the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms · CPC title