Method of comparing private data without revealing the data

• US 8,776,250 B2
• Filed: 07/09/2012
• Issued: 07/08/2014
• Est. Priority Date: 07/08/2011
• Status: Active Grant

• Current Assignee: City College of New York
• Original Assignee: City College of New York
• Inventors: Sy, Bon K., Krishnan, Arun Prakash Kumara
• Primary Examiner(s): Pham, Luu
• Assistant Examiner(s): Baum, Ronald
• Application Number:
  US13/544,351
• Publication Number:
  US 20130014270A1
• Time in Patent Office: 729 Days
• Field of Search: 726/26
• US Class Current: 726/26
• CPC Class Codes: G06F 18/2135 based on approximation criteria, e.g. principal component analysis
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 21/32 using biometric data, e.g. fingerprints, iris scans or voiceprints
• CPC Class Codes: G06V 10/75 Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/3231 Biological data, e.g. fingerprint, voice or retina network architectures or network communication protocols for supporting authentication of entities using biometrical features in a packet data network H04L63/0861

Abstract

Disclosed in this specification is a method and program storage device for comparing two sets of private data without revealing those private data. If the comparison deems the two data sets sufficiently similar, helper data may be provided to permit reconstruction of one of the private data sets without transmission of that private data set.

Claims

1. A method for comparing two sets of private data without revealing the data, the method comprising the steps of:

computing, using a first computer by a first party, a first private matrix (A₁) according to the equation A₁=d₁·

d₁^T where d₁ is a non-zero first private data expressed as a column vector and d₁^T is its corresponding transpose;

finding, a first eigenvalue (λ

_d1) and a corresponding unity normalized first eigenvector (V_d1) of the first private matrix (A₁);

computing, using a second computer by a second party, a second private matrix (A₂) according to the equation A₂=d₂·

d₂^T

where d₂ is a non-zero second private data expressed as a column vector and d₂^T is its corresponding transpose;

finding a second eigenvalue (λ

_d2) and a corresponding unity normalized second eigenvector (V_d2) of the second private matrix (A₂);

computing, using the first computer and the second computer, a non-zero bisector vector (x) in the equation (d₁·

d₁^T+d₂·

d₂^T)x=λ

_d1V_d1+λ

_d2V_d2 by exchanging encrypted matrix d₁·

d₁^T;

encrypted vector λ

_d1V_d1;

encrypted matrix d₂·

d₂^T; and

encrypted vector λ

_d2V_d2 respectively, without the first party or the second party revealing d₁, λ

_d1, V_d1, d₂, λ

_d2 or V_d2;

determining whether or not (1) an angular deviation between the first eigenvector (V_d1) and the second eigenvector (V_d2) is within a threshold, or (2) a distance between V_d1 and V_d2 is within the threshold, wherein;

if the determining within the threshold is satisfied, the first private data and second private data are deemed sufficiently similar;

if the determining within the threshold is un satisfied, the first private data and second private data are deemed dissimilar.

2. The method as recited in claim 1, further comprising the step of digitizing, by the first party, a personal biometric trait to produce the first private data.

3. The method as recited in claim 1, wherein the angular deviation is given by 2*Arc Tan(e/V) where e=x−

V, and V is a non-zero number that is either the first eigenvector V_d1 or the second eigenvector V_d2.

4. A method for comparing two sets of private data without revealing those private data and reconstructing one of the private data sets, the method comprising the steps of:

computing, using a first computer by a first party, a first private matrix (A₁) according to the equation A₁=d₁·

d₁^T where d₁ is a non-zero first private data expressed as a column vector and d₁^T is its corresponding transpose;

finding a first eigenvalue (λ

_d1) and a corresponding unity normalized first eigenvector (V_d1) of the first private matrix (A₁);

computing, using a second computer by a second party, a second private matrix (A₂) according to the equation A₂=d₂·

d₂^T

where d₂ is a non-zero second private data expressed as a column vector and d₂^T is its corresponding transpose;

finding a second eigenvalue (λ

_d2) and a corresponding unity normalized second eigenvector (V_d2) of the second private matrix (A₂);

computing, using the first computer and the second computer, jointly by the first party and second party, a non-zero bisector vector (x) in the equation (d₁·

d₁^T+d₂·

d₂^T)x=λ

_d1V_d1+λ

_d2V_d2 by exchanging encrypted matrix d₁·

d_i^T;

encrypted vector λ

_d1V_d1;

encrypted matrix d₂·

d₂^T; and

encrypted vector λ

_d2V_d2 respectively, without the first party or the second party revealing d₁, λ

_d1, V_d1, d₂, λ

_d2 or V_d2;

determining, by the second party, whether or not (1) an angular deviation or (2) a distance between V_d1 and V_d2 is within the threshold, wherein;

if the determining within the threshold is satisfied, the first private data and second private data are deemed sufficiently similar;

if the determining within the threshold is un satisfied, the first private data and second private data are deemed dissimilar;

transmitting from the second party to the first party, if the threshold is satisfied, helper data that includes λ

_d2 plus a mathematical operator and permits the first party to reconstruct the second party'"'"'s private data by combining the helper data with the first private data.

5. The method as recited in claim 4, wherein the mathematical operator is dividing by d₂^T·

x and the helper data is therefore λ

_d2/d₂^T·

x.

6. The method as recited in claim 4, wherein the helper data comprises √

{square root over (λ

_d2)}.

7. The method as recited in claim 4, wherein the step of computing the bisector vector (x) comprises the first party performing the steps of:

encrypting with a first Paillier key (k₁) and send E(A₁,k₁) and E(λ

_d1V_d1,k₁) to the second party wherein E(A₁,k₁) is the encryption of A1 using Paillier public key k1;

receiving from the second party a Paillier-encrypted E(A₂,k₂) and E(λ

_d2V_d2,k₂) where k₂ is a second Paillier key;

computing E(P₁(A₁+A₂),k₂), where P₁ is a random first matrix;

sending E(P₁(A₁+A₂),k₂) to the second party;

computing E(Y,k₂)=E(P₁(λ

_d1V_d1+λ

_d2V_d2)v^t,k₂), where v^t is a random first vector;

sending E(Y,k₂) to the second party;

sending E((v^t)<sup>−

1</sup>,k₁) to the second party, where (v^t)<sup>−

1</sup> is the Moore-Penrose Pseudoinverse of (v^t);

receiving E(X₁,k₂)=E((P₁(A₁+A₂))<sup>−

1</sup>P₁(λ

_d1V_d1+λ

_d2V_d2)v^t,k₂) from the second party and compute an encrypted solution E(x,k₂) by multiplying E(X₁,k₂) homomorphically with (v^t)<sup>−

1</sup>;

sending the encrypted solution E(x,k₂) to the second party;

receiving a second encrypted solution E(x,k₁) from the second party where the second party obtains E(x,k₁) by multiplying E((v^t)<sup>−

1</sup>,k₁) homomorphically with P₁(A₁+A₂))<sup>−

1</sup> P₁(λ

_d1V_d1+λ

_d2V_d2)v^t to arrive at E(P₁(A₁+A₂))<sup>−

1</sup> P₁(λ

_d1V_d1+λ

_d2V_d2)v^t·

(v^t)<sup>−

1</sup>,k₁)=E(x,k₁);

decrypting E(x,k₁) using the first Paillier key to obtain the bisector vector (x).

8. The method as recited in claim 4, wherein the step of computing the bisector vector (x) comprises the second party performing the steps of:

receiving from the first party E(A₁,k₁) and E(λ

_d1V_d1,k₁), where k₁ is a first Paillier key;

sending to the first party a Paillier-encrypted E(A₂,k₂) and E(λ

_d2V_d2,k₂) where k₂ is a second Paillier key;

receiving from the first party E(P₁(A₁+A₂),k₂), where P₁ is a random first matrix;

decrypting E(P₁+A₂),k₂) to P₁(A₁+A₂);

computing R=(P₁(A₁+A₂))<sup>−

1</sup> where R is the Moore-Penrose Pseudoinverse of P₁(A₁+A₂);

receiving E(Y,k₂) from the first party and decrypting E(Y,k₂) to obtain Y, where Y=P₁(λ

_d1V_d1+λ

_d2V_d2)v^t where v^t is a random first vector;

receiving E((v^t)<sup>−

1</sup>,k₁) from the first party, where (v^t)<sup>−

1</sup> is the Moore-Penrose Pseudoinverse of (v^t);

computing E(x,k₁)=E(R*Y*(v^t)<sup>−

1</sup>,k₁)

receiving an encrypted solution E(x,k₂) from the first party and decrypt it using the second Paillier key to obtain the bisector vector (x);

sending E(x,k₁) to the first party.

9. The method as recited in claim 4, wherein the step of computing the bisector vector (x) comprises the first party performing the steps as recited in claim 7 and the second party performing the steps as recited in claim 8.

10. The method as recited in claim 4, wherein the step of computing the bisector vector (x) using a Privacy-preserving cooperative scientific computation protocol.

11. The method as recited in claim 4, wherein the first private data is a first biometric signature and the second private data is a second biometric signature.

12. The method as recited in claim 4, wherein the first private data is a first fingerprint and the second private data is a second fingerprint.

13. A program storage device readable by machine, tangibly embodying a program of instructions executable by machine to perform the method steps for comparing two sets of private data without revealing those private data and reconstructing one of the private data sets, the method comprising the steps of:

computing, by a first party, a first private matrix (A₁) according to the equation A₁=d₁·

d₁^T where d₁ is a non-zero first private data expressed as a column vector and d₁^T is its corresponding transpose;

finding a first eigenvalue (λ

_d1) and a corresponding unity normalized first eigenvector (V_d1) of the first private matrix (A₁);

computing, by a second party, a second private matrix (A₂) according to the equation A₂=d₂·

d₂^T

where d₂ is a non-zero second private data expressed as a column vector and d₂^T is its corresponding transpose;

finding a second eigenvalue (λ

_d2) and a corresponding unity normalized second eigenvector (V_d2) of the second private matrix (A₂);

computing, jointly by the first party and second party, a non-zero bisector vector (x) in the equation (d₁·

d₁^T+d₂·

d₂^T)x=λ

_d1V_d1+λ

_d2V_d2 by exchanging encrypted matrix d₁·

d₁^T;

encrypted vector λ

_d1V_d1;

encrypted matrix d₂·

d_d1^T; and

encrypted vector λ

_d2V_d2 respectively, without the first party or the second party revealing d₁, λ

_d1, V_d1, d₂, λ

_d2 or V_d2;

determining, by the second party, whether or not (1) an angular deviation or (2) a distance between V_d1 and V_d2 is within the threshold, wherein;

if the determining within the threshold is satisfied, the first private data and second private data are deemed sufficiently similar;

if the determining within the threshold is un satisfied, the first private data and second private data are deemed dissimilar;

transmitting from the second party to the first party, if the threshold is satisfied, helper data that includes λ

_d2 plus a mathematical operator and permits the first party to reconstruct the second party'"'"'s private data by combining the helper data with the first private data.

14. The program storage device as recited in claim 13, wherein the mathematical operator is dividing by d₂^T·

x and the helper data is therefore λ

_d2/d₂^T·

x.

15. The program storage device as recited in claim 13, wherein the heper data comprises √

{square root over (λ

_d2)}.

16. The program storage device as recited in claim 13, wherein the step of computing the bisector vector (x) comprises the first party performing the steps of:

encrypting with a first Paillier key (k₁) and send E(A₁,k₁) and E(λ

_d1V_d1,k₁) to the second party wherein E(A₁,k₁) is the encryption of A1 using Paillier public key k1;

receiving from the second party a Paillier-encrypted E(A₂,k₂) and E(λ

_d2V_d2,k₂) where k₂ is a second Paillier key;

computing E(P₁(A₁+A₂),k₂), where P₁ is a random first matrix;

sending E(P₁(A₁+A₂),k₂) to the second party;

computing E(Y,k₂)=E(P₁(λ

_d1V_d1+λ

_d2V_d2)v^t,k₂), where v^t is a random first vector;

sending E(Y,k₂) to the second party;

sending E((v^t)<sup>−

1</sup>,k₁) to the second party, where (v^t)<sup>−

1</sup> is the Moore-Penrose Pseudoinverse of (v^t);

receiving E(X₁,k₂)=E((P₁(A₁+A₂))<sup>−

1</sup>P₁(λ

_d1V_d1+λ

_d2V_d2)v^t,k₂) from the second party and compute an encrypted solution E(x,k₂) by multiplying E(X₁,k₂) homomorphically with (v^t)<sup>−

1</sup>;

sending the encrypted solution E(x,k₂) to the second party;

receiving a second encrypted solution E(x,k₁) from the second party wherein the second party obtains E(x,k₁) by multiplying E((v^t)<sup>−

1</sup>,k₁) homomorphically with P₁(A₁+A₂))<sup>−

1</sup> P₁(λ

_d1V_d1+λ

_d2V_d2)v^t to arrive at E(P₁(A₁+A₂))<sup>−

1</sup> P₁(λ

_d1V_d1+λ

_d2V_d2)v^t·

(v^t)<sup>−

1</sup>,k₁)=E(x,k₁);

decrypting E(x,k₁) using the first Paillier key to obtain the bisector vector (x).

17. The program storage device as recited in claim 13, wherein the step of computing the bisector vector (x) comprises the second party performing the steps of:

receiving from the first party E(A₁,k₁) and E(λ

_d1V_d1,k₁), where k₁ is a first Paillier key;

sending to the first party a Paillier-encrypted E(A₂,k₂) and E(λ

_d2V_d2,k₂) where k₂ is a second Paillier key;

receiving from the first party E(P₁(A₁+A₂),k₂), where P₁ is a random first matrix;

decrypting E(P₁+A₂),k₂) to P₁(A₁+A₂);

computing R=((P₁(A₁+A₂)))<sup>−

1</sup> where R is the Moore-Penrose Pseudoinverse of P₁(A₁+A₂);

receiving E(Y,k₂) from the first party and decrypting E(Y,k₂) to obtain Y, where Y=P₁(λ

_d2V_d2+λ

_d2V_d2)v^t where v^t is a random first vector;

receiving E((v^t)<sup>−

1</sup>,k₁) from the first party, where (v^t)<sup>−

1</sup> is the Moore-Penrose Pseudoinverse of (v^t);

computing E(x,k₁)=E(R*Y*(v^t)<sup>−

1</sup>,k₁)

receiving an encrypted solution E(x,k₂) from the first party and decrypt it using the second Paillier key to obtain the bisector vector (x);

sending E(x,k₁) to the first party.