Randomly assign n elements to n agents such that each agent only knows its own element

Question

Problem

I'm working on an app that involves shuffling and distributing playing cards to players. As a challenge, I tried to solve this problem in a way that doesn't require a trusted intermediary.

In other terms, the task is to find a distributed algorithm that

• uniquely assigns $n$ agents numbers $1..n$
• allows each agent to know nothing about the assignment but its own
• when revealing the assignment, allows other players to verify the assignment

We also assume that knowing other's assignment is an advantage for each agent, and revealing its own prematurely a disadvantage. Agents are also assumed to be able to talk with each other in a way hidden from all other agents.

Partial solution

The solution I came up with works only under the assumption that adversaries do not collaborate.

The idea is to create a set of $n$ nonces, and assign each agent exactly one nonce. The set is then passed from agent to agent in an agreed upon order, hidden from all others, until each agent received the set exactly once. Each time an agent receives the set, it swaps its nonce with a new one, memorizes the new nonce, and confirms receival of the set to the others. This entire procedure is done twice, at which point, all agents have received the set at least once after all other agents swapped their nonces, making it impossible to recognize and hence map the nonces to the other agents.

When the last agent receives the set the second time, it shares it with everyone, and all agents confirm to the others that their nonce is contained in the set. The agents then assign a number to each nonce in the set based on an agreed upon random seed, giving us the required unique assignment.

To allow ownership verification, instead of the nonces, agents put the hash value of their nonce on the set, revealing the actual nonce only when verification is required.

---

The problem with this solution is that if adversaries are allowed to collaborate, each time an adversary receives the set, they can compare their versions, identify changes and potentially derive which nonce belongs to other agents, allowing them to know what number got assigned to them.

All ideas are appreciated!

Answer 1

This problem is part of a set of problems known as Mental Poker.

There is an excellent and small article by Shamir, Rivest and Adleman that describe a practical way about how to implement such algorithm.

The abstract is gold:

Can two potentially dishonest players play a fair game of poker without using any cards (e.g. over a phone)?

This paper provides the following answers:

1. No. (Rigorous mathematical proof supplied.)
2. Yes.(Correct & complete protocol given.)

Basically, from an information-theoretic point of view, playing such a game is impossible without a trusted third party, but it is feasible to design a protocol using well-known hard to reverse cryptographic functions.

---

The algorithm will work as following:

Suppose you have $n$ nonces (numbers from $1$ to $n$). Each participant in the protocol has access to secret functions $e_i$ and $d_i$ which are used to encrypt and decrypt data. This functions should satisfy few properties, which we will analyze later.

The first participant is given the full set of nonces. It encrypts each nonce with its secret function $e_1$, shuffles them randomly, and passes the resulting data to second participant.

Second participant will do the same, but in this case it doesn't have nonces, but a random permutation of the encrypted nonces. It will also encrypt each element with its own secret function $e_2$ and shuffle the data again.

Then third participant, and so on, until all participants have shuffled and encrypted the data with its secret function.

Overall the setup process is:

data = [1..n]
for i in [1..n]:
    data = [e_i(nonce) for nonce in data]
    shuffle(data)

After this setup, each element of data are the nonces encrypted with all secret functions $e_i$ in a random order unknown to any participant.

Notice that at this point is impossible for each participant to deduce each nonce without the help of other participants. And it is enough that one of the participants to shuffle the data completely random to remove any possible bias in the resulting order, independently if some malicious participant tries to bias the order.

Participant $i$-th is assigned the nonce at position $i$. To recover such nonce, participant $i$ asks each other participant $j \neq i$ to decrypt the value with its secret function $d_j$ in turns. At the end participant $i$ will have its nonce only encrypted with its own secret function $e_i$ so it can recover it using $d_i$.

Recovering nonce $i$:

nonce_i_encrypted = data[i]
for j in [1..n]:
    if j == i:
        continue
    nonce_i_encrypted = d_j(nonce_i_encrypted)

nonce_i = d_i(nonce_i_encrypted)

At the end of this procedure each participant knows its own nonce, but no other participant know anything about it.

After using this values for your current problem a player can claim they are really in control of such nonce, by either publishing the secrets functions $e_i$ and $d_i$, so everyone can compute locally all the values, or decrypting the value data[i] after the first step but before the second step, publishing and then using this value as the input in the second step to fully decrypt it.

The functions $e_i$ and $d_i$ should have the following properties:

1. $e_i(x)$ is the encrypted version of a message $x$ under key $i$,
2. $d_i(e_i(x)) = x$ for all messages $x$ and keys $i$,
3. $e_i(e_j(x)) = e_j(e_i(x))$ for all messages $x$ and keys $i$ and $j$,
4. Given $x$ and $e_i(x)$ it is computationally impossible for a cryptanalyst to derive $i$, for all $x$ and $i$,
5. Given any messages $x$ and $y$, it is computationally impossible to find keys $i$ and $j$ such that $e_i(x) = e_j(y)$.

As stated in the paper, most of this assumptions are somehow common except for property 3), which tells the encryption functions must commute.

They propose a simple encryption scheme that satisfies these properties. Let's say all participants agree on some large prime number $P$ (it is ok if it fixed in the protocol). And each participant secretly choose a random number $k_i$ such that $gcd(k_i, P - 1) = 1$. Let's say $q_i$ is such value that $k_i \cdot q_i \equiv 1 \mod(P -1)$. Then participant $i$ can use secret functions:

$$e_i(x) = x^{k_i} \mod(P)$$ $$d_i(y) = y^{q_i} \mod(P)$$

Some caveats about this algorithm: Participants can't cheat in such a way that colluding benefits them in learning the nonce about the other peer (unless of course $n-1$ participants collude, and only one nonce is remaining). However, malicious participants can attack the protocol by no participating, effectively stalling the dealing process, since a lot of actions are required from each participants while they are dealing the nonces. They can also produce gibberish, but this can be mitigated extending the protocol to detect which participant was the culprit and penalizing such participant at a higher level.

---

I implemented this algorithm for a poker game in NEAR blockchain. You can see the code in rust here. Notice there isn't any trusted third party in a blockchain, but there is a trusted computing environment which all participants can use as a mechanism to run this protocol.