4
$\begingroup$

For a "Murder Mystery Party", one person is chosen anonymously to be the murderer (i.e., only the murderer knows who the murderer is) by shuffling cards with everyone randomly taking a private card (one card has "You Are The Murderer!" written on it).

How can I do this cryptographically over an open communication channel without trusting any third party?

I'm hoping this simple problem has a simple solution that doesn't involve full mental poker or oblivious transfer methods. Is there a trick that somehow combines inputs from everyone (which include the randomness used for the selection so that everyone can trust that the process was random) to publish something that only one "winner" would recognize?

$\endgroup$
1
$\begingroup$

With some assumptions I think you can do this with a simple protocol.

We will break i into two parts: attempt an allocation which may succeed with reasonable liklyhood. And verify it. If verification fails try again.

The first step we can do by each party randomly selecting for himself if he is the chosen one with probability 1/n.

Verification we do with secure multiparty summation. Sum the bits of all parties and if it is 1 verification succeeds. and any other value it fails. First we need to establish 2 way secure channels(e.g using DH key exchange). A simple summation would be for one party to pick a random R add it to his bit and pass along, where each party adds it's bit and passses along until finally the first party removes R and reveals. This can be broken by a collosion of 2. Alternativly, each party secret shares it's bit by distributing to all parties a random share which sum up to their bit. Then sum up all shares from all parties to reveal total sum.

This however allows a member to force himself to be selected or not.

To deal with this problem we can have everyone commit to a random value $X_i$ and then together they pick a random $R$. Each player will use their secret combined with the shared random ${X_i} + R$ as a random seed. This allows at the end of the game to verify everyone picked random numbers fairly. Picking a shared random $R$ can be done by each party picking a random $R_i$ and publishing a commitment to it and then all parties reveal. take the sum or the xor of all as $R$.

Success probability of the first phase is $(1-1/n)^{n-1}$ which approaches 1/e . So we are likely to success after only a handful of iterations.

| improve this answer | |
$\endgroup$
  • $\begingroup$ The secret share verification works for me (I wanted to be resistant to any collusion number), but I'm still hoping for some simpler trick since mental poker is probably faster than your two-step method if, for example, there are only 4 people. $\endgroup$ – bobuhito Mar 7 at 18:55
  • $\begingroup$ mental poker seems much more complicated to me. Requiring multiple encryption steps. I'm not even sure how it goes with many players. The scheme I proposed has some commitments at the beginning and setting up pairwise channels. And the iteration require only picking random numbers and summation. With n=4 probability of success is 42% So just over two rounds expected. However obviously complexity is hard to measure. speed wise, if mental poker won't need pairwise channels it will be faster but otherwise slower(not sure what it needs). $\endgroup$ – Meir Maor Mar 7 at 20:04

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.