Is secure remote snap possible? 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.
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.