METHOD OF COMPARING PRIVATE DATA WITHOUT REVEALING THE DATA
First Claim
Patent Images
1. A method for comparing two sets of private data without revealing the data, the method comprising the steps of:
- computing, by a first party, a first private matrix (A1) according to the equation A1=d1·
d1T where d1 is a first private data expressed as a column vector and d1T is its corresponding transpose;
finding a first eigenvalue (λ
d1) and a corresponding unity normalized first eigenvector (Vd1) of the first private matrix (A1);
computing, by a second party, a second private matrix (A2) according to the equation A2=d2·
d2T where d2 is a second private data expressed as a column vector and d2T is its corresponding transpose;
finding a second eigenvalue (λ
d2) and a corresponding unity normalized second eigenvector (Vd2) of the second private matrix (A2);
computing a bisector vector (x) in the equation (d1·
d1T+d2·
d2T)x=λ
d1Vd1+λ
d2Vd2 without the first party or the second party revealing d1, λ
d1, Vd1, d2, λ
d2 or Vd2;
determining whether or not (1) an angular deviation between the first eigenvector (Vd1) and the second eigenvector (Vd2) is within a threshold, or (2) a distance between Vd1 and Vd2 is within the threshold, wherein;
if the threshold is satisfied, the first private data and second private data are deemed sufficiently similar;
if the threshold is un satisfied, the first private data and second private data are deemed dissimilar.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
17 Claims
-
1. A method for comparing two sets of private data without revealing the data, the method comprising the steps of:
-
computing, by a first party, a first private matrix (A1) according to the equation A1=d1·
d1T where d1 is a first private data expressed as a column vector and d1T is its corresponding transpose;finding a first eigenvalue (λ
d1) and a corresponding unity normalized first eigenvector (Vd1) of the first private matrix (A1);computing, by a second party, a second private matrix (A2) according to the equation A2=d2·
d2Twhere d2 is a second private data expressed as a column vector and d2T is its corresponding transpose; finding a second eigenvalue (λ
d2) and a corresponding unity normalized second eigenvector (Vd2) of the second private matrix (A2);computing a bisector vector (x) in the equation (d1·
d1T+d2·
d2T)x=λ
d1Vd1+λ
d2Vd2 without the first party or the second party revealing d1, λ
d1, Vd1, d2, λ
d2 or Vd2;determining whether or not (1) an angular deviation between the first eigenvector (Vd1) and the second eigenvector (Vd2) is within a threshold, or (2) a distance between Vd1 and Vd2 is within the threshold, wherein; if the threshold is satisfied, the first private data and second private data are deemed sufficiently similar; if the threshold is un satisfied, the first private data and second private data are deemed dissimilar. - View Dependent Claims (2, 3)
-
-
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, by a first party, a first private matrix (A1) according to the equation A1=d1·
d1 T where d1 is a first private data expressed as a column vector and d1T is its corresponding transpose;finding a first eigenvalue (λ
d1) and a corresponding unity normalized first eigenvector (Vd1) of the first private matrix (A1);computing, by a second party, a second private matrix (A2) according to the equation A2=d2·
d2Twhere d2 is a second private data expressed as a column vector and d2T is its corresponding transpose; finding a second eigenvalue (λ
d2) and a corresponding unity normalized second eigenvector (Vd2) of the second private matrix (A2);computing, jointly by the first party and second party, a bisector vector (x) in the equation (d1·
d1T+d2·
d2T)x=λ
d1Vd1+λ
d2Vd2 without the first party or the second party revealing d1, λ
d1, Vd1, d2, λ
d2 or Vd2;determining, by the second party, whether or not (1) an angular deviation or (2) a distance between Vd1 and Vd2 is within the threshold, wherein; if the threshold is satisfied, the first private data and second private data are deemed sufficiently similar; if 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. - View Dependent Claims (5, 6, 7, 8, 9, 10, 11, 12)
-
-
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 (A1) according to the equation A1=d1·
d1T where d1 is a first private data expressed as a column vector and d1 T is its corresponding transpose;finding a first eigenvalue (λ
d1) and a corresponding unity normalized first eigenvector (Vd1) of the first private matrix (A1);computing, by a second party, a second private matrix (A2) according to the equation A2=d2·
d2Twhere d2 is a second private data expressed as a column vector and d2T is its corresponding transpose; finding a second eigenvalue (λ
12) and a corresponding unity normalized second eigenvector (Vd2) of the second private matrix (A2);computing, jointly by the first party and second party, a bisector vector (x) in the equation (d1·
d1T+d2·
d2T)x=λ
d1Vd1+λ
d2Vd2 without the first party or the second party revealing d1, λ
d1, Val, d2, λ
d2 or Vd2;
determining, by the second party, whether or not (1) an angular deviation or (2) a distance between Vd1 and Vd2 is within the threshold, wherein; if the threshold is satisfied, the first private data and second private data are deemed sufficiently similar; if 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 X,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. - View Dependent Claims (14, 15, 16, 17)
-
Specification