3
$\begingroup$

Say you have 2N named peers (agents) able to address each other by their name and communicate freely among them. What distributed algorithm could they use in order to randomly pair up? The final situation would be that the agents were able to organize themselves in N random couples. On different runs the random couples should be different.

Important: the algorithm should be "private" in the following sense: at the end of the round, each agent should only know the name of agent it was paired with.

It's also important that the agents have no possible way to influence who they end up paired with.

$\endgroup$
5
  • $\begingroup$ Can you be more precise about what model you're working in and in particular what your constraints are to determine if an algorithm is good? In particular, can you perform leader election on you agents? If not, why? (If you can, the problem seems easy: the leader can just do the selection and tell each agent in which pair they are) $\endgroup$
    – Discrete lizard
    Oct 15 '20 at 10:21
  • $\begingroup$ Thank you for your comment. I can perform leader election, if necessary. I would say that an algorithm is "good" if it ends on average in linear (or sublinear) time using a linear (or sublinear) amount of transmitted bits. The problem with that approach is that the leader gets to know other information than just its own paired agent. In fact, in your scenario, that leader knows ALL the pairs, as opposed to my original post. $\endgroup$ Oct 15 '20 at 10:24
  • $\begingroup$ I'm not exactly sure if I understand your definition of "anonymous". Does the name of an agent differ from its address? If so, is it a problem that the leader knows the addresses of pairs, but not their names? I suppose you want the pairs to be "private" in some sense. However, this still leaves multiple definitions open, as there is always some knowledge that the agents have about the other pairs: they know that their partner is not the partner of anyone else, for example. $\endgroup$
    – Discrete lizard
    Oct 15 '20 at 11:01
  • $\begingroup$ Do you want a protocol such that after each round there is a (possibly empty) "candidate partner" for each agent, and that the only agents that are completely sure (probability 1) that agent A has candidate partner B are the agents A and B? $\endgroup$
    – Discrete lizard
    Oct 15 '20 at 11:01
  • $\begingroup$ No, the name is the same as the address. I added "anonymous" to signify that the only information available to the agent at the end of the round should be the name-address of the paired agent. Each agent should be certain of who its paired agent is. It's not the best word to use. I substitute it with "private" that maybe is a little closer to what I mean. $\endgroup$ Oct 15 '20 at 11:07
2
$\begingroup$

Let's assume the agents are labeled $[0, n)$. Let $w > 2$ be a small constant, e.g. 4. Let $F_k(x)$ be an oblivious pseudo-random function (OPRF).

Let each agent generate random value $s_i$, announce $H(s_i)$ and then choose $r = \bigoplus_i s_i$ to ensure a fair random shared seed (peers checking the hashes).

Initially agent $i$ chooses $X_i = i$. Then, some rounds take place. Use the chosen seed to derive a different $P_r$ and $w$ agents $A_{r,0}, A_{r,1}, \cdots, A_{r,w-1}$ for each round. Then, in round $r$ every agent computes

$$X'_i = (P_r - X_i) \bmod n$$ $$\hat X_i = \max(X_i, X'_i)$$ $$p = H(\hat X_i) \bmod w$$ $$b =\text{get-secret}\left(p, r, \hat{X_i}\right) \bmod 2$$

where $\text{get-secret}(p, r, \hat{X})$ securely contacts agent $A_{r,p}$ and uses the OPRF primitive to compute $F_{K_{p,r}}(\hat{X})$, where $K_{p,r}$ is some never-shared secret round key generated (and stored) by agent $A_{r,p}$. Then, at the end of the round iff $b = 1$ the agent replaces $X_i$ with $X'_i$.

After the round is over the $w$ chosen agents $A$ can (and should) communicate to ensure no one cheated and asked for more than one secret. This ensures everyone only has partial information. If you force the $\text{get-secret}$ requests to be signed by agent $i$ one can even provide evidence another agent tried to cheat.

Do this for a sufficient* number of rounds and the result is that each agent $i$ has a value $X_i$ such that there is a permutation $\sigma(i) = X_i$, yet every agent only knows their own $\sigma(i)$, and is deeply unsure about anyone else's $\sigma(j)$.

However, this just gives us a secret random permutation. But we can use this to get a pairing. Note that if we let $g(i) = i \oplus 1$ (where $\oplus$ is XOR) then $f(i) = \sigma^{-1}(g(i))$ is a pairing (assuming zero-indexed permutations).

How can we compute $\sigma^{-1}$? By noting that each round is it's own inverse, each agent sets $X_i = g(X_i)$, and we run all the rounds again, in reverse order (with the same $P,A$ and $K$ values), again ensuring that no agent requests too many secrets. The end result is that $X_i$ contains the partner for each agent.


* The technique above is inspired by sometimes recurse shuffle. Read the paper for more ideas, and to get some bounds for what is sufficient.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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