US 11,531,782 B1Granted

Systems and methods for finding a value in a combined list of private values

AssigneeTripleBlind, Inc.

InventorsBabak Poorebrahim Gilkalaye, Riddhiman Das, Gharib Gharibi

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system and method are disclosed for each party of a group of m parties to be able to learn an Nth smallest value in a combined list of the values in which each party has separate lists of values. A method includes creating, by each party of a group of m parties, m lists of additive shares associated with each party's respective list of data, distributing, from each party to each other party in the group of m parties, m−1 of the lists of additive shares to yield a respective combined list of additive shares Wi obtained by each party of the m parties, receiving from a trusted party a list of additive shares Vi associated with a hot-code vector V, computing, in a shared space by each party, a respective Ri value using a secure multiplication protocol and comparing, in the shared space, by each party and using secure multi-party comparison protocol, the respective Ri to all elements in the respective combined list of additive shares Wi to yield a total number Pi of values in Wi that are smaller than Ri. The value Pi is used to either end the method or loop back for further processing with new values of Wi and in some cases a new value of N.

Claims19

Dependent claims

A method of enabling separate parties to compute securely an Nth smallest value in a combined list of values from m number of parties W, the method comprising:

(1) creating, by each party of the m parties, m additive shares for each value in a respective list of values for each party of the m parties to yield m lists of additive shares for each party of the m parties;
(2) distributing, from each party of the m parties, m−1 lists of additive shares from the m lists of additive shares for each party by distributing one of the m−1 lists of additive shares to each other party of the m parties to yield a respective combined list of shares Wi having S values for each of the m parties, wherein S equals the total number of values in the combined list of values from the m parties;
(3) receiving, from a trusted party and by each of the m parties, a respective list of additive shares Vi associated with a hot-code vector V comprising a value of 1 randomly assigned a position in V and the rest of the values being 0;
(4) computing, by each party of the m parties and via a SecureMult protocol, Ri=Sum(SecureMult(Wi,Vi,);
(5) applying a comparison protocol to compare, by each party of the m parties, R against all elements in W, such that each party learns a total number of values in W that are smaller than R as a value in shared space Pi, wherein Pi values add up to P and wherein a position or Ri in Wi is equal to Pi+1;
(6) when N=P+1, returning, from each party, a value Ri and concluding the method;
(7) when N>P+1, removing, by each party, all numbers smaller than and Ri, and Ri as well, from each party's Wi and setting N=N−(P+1) to yield a new Wi and new N;
(8) when N<P+1, removing, by each party, all numbers bigger than Ri, and Ri as well, from Wi to yield a new Wi;
and
(9) returning to step (3).

7 more elements

A system for enabling separate parties to compute securely an Nth smallest value in a combined list of values from m number of parties W, the system being operated by one of the parties of the m parties, the system comprising:

a processor;
and
a computer-readable storage device storing instructions which, when executed by the processor, cause the processor to perform operations comprising:
(1) creating m additive shares for each value in a respective list of values for each party of the m parties to yield m lists of additive shares for each party of the m parties;
(2) distributing m−1 lists of additive shares from the m lists of additive shares for each party by distributing one of the m−1 lists of additive shares to each other party of the m parties to yield a respective combined list of shares Wi having S values for each of the m parties, wherein S equals the total number of values in the combined list of values from the m parties;
(3) receiving, from a trusted party, a respective list of additive shares Vi associated with a hot-code vector V comprising a value of 1 randomly assigned a position in V and the rest of the values being 0;
(4) computing, via a SecureMult protocol, Ri=Sum(SecureMult(Wi,Vi,);
(5) applying a comparison protocol to compare, by each party of the m parties, R against all elements in W, to learn a total number of values in W that are smaller than R as a value in shared space Pi, wherein a position of Ri in Wi is equal to Pi+1 and wherein values of Pi add to a value P;
(6) when N=P+1, returning a value Ri and concluding the operations;
(7) when N>P+1, removing all numbers smaller than Ri, and Ri as well, from each party's Wi and setting N=N−(P+1) to yield a new Wi and new N;
(8) when N<P+1, removing all numbers bigger than Ri, and Ri as well, from Wi to yield a new Wi;
and
(9) returning to step (3).

10 more elements

Dependencies are inferred from the claim text.