Is there an algorithm that allows to distribute elements securely between parties?

Question

Let's say we have a set of numbers $n = \{ 1, 2, 3, 4, 5, \ldots \}$ and $m$ players ($m < \operatorname{sizeof}(n)$, of course).

I want to know if there's a way for all $m$'s to pick different numbers from $n$ in a way that it doesn't reveal which one did they pick or which ones were picked by the others.

Answer 1

It is doable. Assuming all parties are semi-honest and you have a public key encryption scheme allows threshold key generation and threshold decryption, as well as re-encryption, that is:

• $keyGen(\lambda,m)$: given the security parameter $\lambda$ and an integer $m$, output a public key $pk$ and $m$ shares of the secret key, each share is given to a player (each player only knows its own share). The secret key is $sk$ and the $i$-th share is $s_i$.
• $Enc(pk;m,r)$: encrypt $m$ with random $r$, using the public key $pk$.
• $Dec((s_1,\cdots, s_m);c,i)$: $m$ players jointly decrypt a ciphertext c, and output it to the $i$-th party.
• $Reenc(pk;c,r)$: Given $c=Enc(pk;m,r')$, re-encrypt it with a random number $r$, so that the output is a valid ciphertext of the original plaintext (i.e. $Enc(pk;m,r'')$).

Elgamal satisfies the above requirements.

Then the players do the following:

1. They run $keyGen$ jointly to get the public key and shares of secret key.
2. The first player $P_1$ encrypt each of $n$ numbers, permute the list of the ciphertexts randomly, passes the permuted list to $P_2$.
3. Then $P_i$ re-encrypts each ciphertext in the list it received and permute the list randomly, and passes the permuted list to $P_{i+1}$.
4. $P_m$ re-encrypts each ciphertext in the list it received and permute the list, and publish the final list.
5. Each party pick a different ciphertext in the list.
6. From $i=1$ to $m$, the players jointly decrypt $P_i$'s ciphertext and reveal it to $P_i$.

If the parties are malicious, zero-knowledge proofs need to be in place to ensure the parties follow the protocol.