What is a distributed algorithm for generating random “private” pair-matchings?

Question

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.

Answer 1

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.