1
$\begingroup$

Scenario:

  • We have a central server $S$.
  • We have a number of peripheral servers $P_i$
  • We have some individuals $U_j$
  • A given individual may be "known" to one or more peripheral servers. Each peripheral server generates unique IDs for the individuals it knows and stores a map $f_i: U_j \to \textrm{ID}$ and the corresponding inverse $f_i^{-1}$
  • A peripheral server may share its IDs but may never share the identities of the individuals it knows.
  • The peripheral servers can communicate securely with $S$.
  • The peripheral servers regularly transmit to $S$ a map from IDs to some data.

Problem:

$S$ wants to determine whether $P_1$'s ID $a$ corresponds to the same individual $u$ as $P_2$'s ID $b$ without ever knowing the value of $u$. If so, it will merge the data from the different peripheral servers. (Details of the merge method are out of scope). Is this possible?

In essence this is "mental snap", or perhaps zero-knowledge set intersection.

Rejected approach:

  • The domain of individuals is too small to simply send hashes to $S$ and compare the hashes: this would allow identifying the individuals by brute force.
Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Could you please expand some on your problem statement? Specifically, I'm wondering who is allowed to know what and who trusts who. Clearly $S$ cannot learn the value of $u$, but should $P_1$ and $P_2$ know each others $u$ values? Should the peripheral servers learn whether or not there was a match? Can $P_1$ and $P_2$ determine the answer between the two of them and tell $S$ the answer (i.e., does $S$ trust them to tell the truth in that case)? $\endgroup$
    – mikeazo
    Commented Oct 19, 2012 at 11:36

1 Answer 1

Reset to default
1
$\begingroup$

Yup, should be possible. Look at multiparty secure computation protocols.

In particular, you might want to look at secure protocols for private set intersection. $P_1$ and $P_2$ can use such a protocol to find the individuals that are in the intersection of a set known to $P_1$ and a set known to $P_2$. Then, they can let $S$ know whether there is any intersection and what the correspondence between IDs is

Specifically: $P_1$ has a set of individuals ($f_1^{-1}(a)$), and $P_2$ has another set ($f_2^{-1}(b)$); now a private set intersection protocol lets us check whether these sets have any elements in common, without revealing anything else about the sets. In such a protocol, the set of individuals never leaves $P_1$ or $P_2$, but we still have a way to learn whether $P_1$'s set $P_1$ has any overlap with $P_2$'s set. The details are, well, detailed, but if you are interested, look up any reference on private set intersection.

This approach scales beyond pairwise comparison of individual IDs; if the server has a set of IDs on $P_1$ and a set of IDs on $P_2$, you can use this approach to find whether there is any overlap between these sets and if so, what the correspondence is between the IDs.

Improve this answer
$\endgroup$
8
  • $\begingroup$ No, he wants to find the corresponding pairs of IDs. $\:$ (On the other hand, the reference to $\hspace{1 in}$ multiparty secure computation is correct and highly relevant.) $\:$ $\endgroup$
    – user991
    Commented Oct 17, 2012 at 21:55
  • $\begingroup$ @RickyDemer, Right, I mis-spoke. I've fixed it. What I intended is that you apply private set intersection to the set of individuals (a subset of $U$), not the set of IDs, but somehow what came out of my fingers didn't match what was I intended. My mistake! $P_1$ has a set of individuals ($f_1^{-1}(a)$), and $P_2$ has another set ($f_2^{-1}(b)$); a private set intersection protocol lets us check for non-empty intersection; the set of individuals never leaves $P_1$ or $P_2$, but we have a way to learn whether $P_1$'s set $P_1$ has any overlap with $P_2$'s set. $\endgroup$
    – D.W.
    Commented Oct 18, 2012 at 5:49
  • $\begingroup$ Forgive my lack of knowledge on private set intersection. Does private set intersection returns whether or not the intersection is empty or does it return the intersection? If it is the latter, then this will not work. If it is the former, then it seems like a valid solution. $\endgroup$
    – mikeazo
    Commented Oct 18, 2012 at 11:19
  • $\begingroup$ @mikeazo, it returns the intersection. (But it could be modified, e.g., by pre-hashing all elements or something.) Why do you say this will not work? $\endgroup$
    – D.W.
    Commented Oct 18, 2012 at 15:32
  • $\begingroup$ Wouldn't the value of $u$ be known then to $S$. $f_1^{-1}(a)=u$ and $f_2^{-1}(b)=u$. I.e., these are sets of a single element. The intersect would be $u$ which reveals the value of $u$ to the server. Or am I missing something? $\endgroup$
    – mikeazo
    Commented Oct 18, 2012 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.