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

1. A method of enabling separate parties to compute securely an N th 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 W i 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 V i 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, R i =Sum(SecureMult(W i ,V i ,);

(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 P i , wherein P i values add up to P and wherein a position or R i in W i is equal to P i +1;

(6) when N=P+1, returning, from each party, a value R i and concluding the method;

(7) when N>P+1, removing, by each party, all numbers smaller than and R i , and R i as well, from each party's W i and setting N=N−(P+1) to yield a new W i and new N;

(8) when N<P+1, removing, by each party, all numbers bigger than R i , and R i as well, from W i to yield a new W i ; and

(9) returning to step (3).

2. The method of claim 1 , wherein the hot-code vector V has a number of values equal to S.

3. The method of claim 1 , wherein the comparison protocol comprises a SecureCompare protocol.

4. The method of claim 1 , wherein the method loops from step (9) to step (3) until N=P i +1.

5. The method of claim 1 , wherein each party does not know what numbers are being compared.

6. The method of claim 1 , wherein an owner of a value in the combined list only learns that the value in the combined list W is smaller or bigger than a number the owner of the value does not know from the combined list W.

7. The method of claim 3 , wherein the SecureMult protocol and the SecureCompare protocol operate on a Ring R set equipped with two binary operations.

8. The method of claim 7 , wherein the Ring R=[Z] 2 64.

9. The method of claim 3 , wherein the SecureMult protocol and the SecureCompare protocol comprise multi-party computation primitives enabling each party to perform multiplication and comparison securely.

10. A system for enabling separate parties to compute securely an N th 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 W i 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 V i 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, R i =Sum(SecureMult(W i ,V i ,);

(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 P i , wherein a position of R i in W i is equal to P i +1 and wherein values of P i add to a value P;

(6) when N=P+1, returning a value R i and concluding the operations;

(7) when N>P+1, removing all numbers smaller than R i , and R i as well, from each party's W i and setting N=N−(P+1) to yield a new W i and new N;

(8) when N<P+1, removing all numbers bigger than R i , and R i as well, from W i to yield a new W i ; and

(9) returning to step (3).

11. The system of claim 10 , wherein the hot-code vector V has a number of values equal to S.

12. The system of claim 10 , wherein the comparison protocol comprises a SecureCompare protocol.

13. The system of claim 10 , wherein the method loops from step (9) to step (3) until N=P i + 1 .

14. The system of claim 10 , wherein each party does not know what numbers are being compared.

15. The system of claim 10 , wherein an owner of a value in the combined list only learns that the value in the combined list W is smaller or bigger than a number the owner of the value does not know from the combined list W.

16. The system of claim 12 , wherein the SecureMult protocol and the SecureCompare protocol operate on a Ring R set equipped with two binary operations.

17. The system of claim 16 , wherein the Ring R=[Z] 2 64.

18. The system of claim 12 , wherein the SecureMult protocol and the SecureCompare protocol comprise multi-party computation primitives enabling each party to perform multiplication and comparison securely.

19. A method of determining an Nth smallest value in a list of combined values, the method comprising:

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 W i obtained by each party of the m parties; receiving from a trusted party a list of additive shares V i associated with a hot-code vector V;

computing, in a shared space by each party, a respective R i value using a secure multiplication protocol;

applying, in the shared space, by each party a secure multi-party comparison protocol to R i and W i , to yield a total number in shared space of P i of values in W i that are smaller than R i , wherein adding P i values equals P; and

using P to either (1) return R i when N=P+1 and end the method; (2) remove all numbers smaller and R i , and R i as well, from Wi and set a new value of N and return to an earlier step in the method until N=P+1; or (3) remove all numbers bigger than R i , and R i as well, from W i and return to an earlier step in the method until N=P+1.