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

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.

• "it doesn't reveal which one did they pick or which ones were picked by the others." - if no one knows who picked which number, what's the point? Do you mean that everyone learns their own number, but not anyone else's? – poncho Oct 2 at 13:08
• I'm sorry I couldn't word it better, can you suggest a better description? – almosnow Oct 2 at 13:24
• A better description of the problem would depend on what problem you're trying to solve. What is the problem? Remember: we're not mind-readers; you need to be explicit. – poncho Oct 2 at 13:42
• Please read my question carefully and then tell me what is the best interpretation of the problem you can make out. From there I could work on a description that avoids any misunderstanding that arises :) – almosnow Oct 2 at 13:52
• The most literal interpretation I can see: "pick $m$ different numbers so that nobody knows (not even the ones doing the picking) which ones were picked" – poncho Oct 2 at 14:27

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.

• This looks good enough, thank you @Changyu !!! – almosnow Oct 2 at 20:56