1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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? $\endgroup$ – poncho Oct 2 at 13:08
  • $\begingroup$ I'm sorry I couldn't word it better, can you suggest a better description? $\endgroup$ – almosnow Oct 2 at 13:24
  • $\begingroup$ 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. $\endgroup$ – poncho Oct 2 at 13:42
  • $\begingroup$ 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 :) $\endgroup$ – almosnow Oct 2 at 13:52
  • $\begingroup$ 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" $\endgroup$ – poncho Oct 2 at 14:27
1
$\begingroup$

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.

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

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.