2
$\begingroup$

Alice, Bob, and Charlie are working on three projects.

Alice is the manager. At the beginning of each day, she chooses one project to work on (this choice is based on her preferences and is not random) and then assigns the other projects to Bob and Charlie. Bob and Charlie demand that this assignment be 50/50 random and anonymous (so Alice does not know who got which of the two projects). Alice accepts this demand, but demands that her original choice be anonymous too (so Bob and Charlie can not know which project Alice has, unless they tell each other their projects to deduce the remaining project).

To accomplish this, at the beginning of each day, Alice writes the two projects she does not want on two cards and puts them face down on a table. Everyone mixes/shuffles the cards until everyone is content that no one knows which is which. Bob picks a card, Charlie gets the other card, and they then work separately on the projects written on their cards.


The only way I see to accomplish this "at a distance with cryptography" is Mental Poker, based on a commuting encryption/decryption method:

Alice shuffles and encrypts both (starting from her two unwanted projects)
-> Bob shuffles and encrypts both
-> Charlie shuffles and encrypts both
-> Alice decrypts both
-> Bob decrypts the first and Charlie decrypts the second
-> In secret, Bob decrypts the second and Charlie decrypts the first

This is a lot of back and forth for every daily assignment - Is there any simpler solution?

Ignoring Charlie, I was thinking Bob could give some seed (generated from a private key) to Alice before everything and then Alice would generate random numbers for Bob (readable with his private key, but unreadable to Alice) which somehow exclude Alice's project...but maybe that is a pipe dream.

$\endgroup$
  • 1
    $\begingroup$ What about: Bob and Charlie broadcast commitments to random bits $b$ and $c$ respectively. Then Alice broadcasts the two messages/projects in plain in a random order. Bob and Charlie then send openings of their commitments to each other but not Alice. If $b\oplus c=0$, Bob takes the first project. Otherwise he takes the second one. That's 3 rounds of you have a broadcast channel. $\endgroup$ – Maeher Jan 18 at 19:45
  • $\begingroup$ @Maeher Bob and Charlie then will know Alice's project, but I want everyone to only know their own project. $\endgroup$ – bobuhito Jan 18 at 19:51
  • $\begingroup$ I don't know if it can be done without lots of back and forth, but it seems that if this can be done then you can build from it a multi-party oblivious transfer where Alice is the sender, and Bob and Charlie are 2 parties that each selects a message from Alice without each party knowing what the other selected, but having both parties influencing their own outputs. $\endgroup$ – yacovm Jan 18 at 21:57
  • $\begingroup$ What are you trying to minimize? communication, conputation? what you suggested seems simple to me. $\endgroup$ – Meir Maor Jan 19 at 5:41
  • $\begingroup$ Let's say I want minimum computation time on x64 cores so that projects can be reassigned as fast as possible (instead of just daily). $\endgroup$ – bobuhito Jan 19 at 13:08
1
$\begingroup$

The obvious way is to use two oblivious transfers. In case you need reminding: an Oblivious Transfer is a protocol where one party (Alice) has a number of secrets (in this case, two), and the other party (Bob or Charlie) gets to pick which one he gets to learn, but he doesn't learn the other (and Alice doesn't learn which one he picked). There are several known protocols that implement this.

Here is how it would work:

Bob and Charlie randomly agree on a random bit $b$

Alice takes the two tasks she doesn't want, and randomly labels them $T_0$ and $T_1$

Bob then performs an oblivious transfer with Alice, obtaining the task $T_b$

Charlie then performs an oblivious transform with Alice (but using the bit $1-b$ rather than $b$ in the oblivious transfer), obtaining the task $T_{1-b}$

Because of the guarantees that OT provides, neither Alice, Bob nor Charlie know any of the tasks other than their own.

Now, one obvious issue is that, if Bob or Charlie wanted to cheat, they could use the wrong value of $b$, and learn the task given to the other guy. However, if they did that, they wouldn't learn their own, and so if we assume that they find that unacceptable, this isn't an issue. It is possible to insert a zero knowledge proof that would ensure that they're not doing that (the details of which would depend on the OT protocol used); however I don't know if you need to do that.

| improve this answer | |
$\endgroup$
  • $\begingroup$ The "Mental Poker" method I gave does avoid the cheating issue you point out, but I'm willing to agree that no one would cheat like this. It seems your method can reuse the same RSA keys every day (the "Mental Poker" method I gave needed to generate new RSA keys for all 3 parties every day!), so I like it. I bet there's still a more efficient trick, so want to leave this question open for a few days before marking an answer. $\endgroup$ – bobuhito Jan 19 at 5:19
  • $\begingroup$ This doesn't seem simpler, you just used a short name to a complex part (oblivious transfer). $\endgroup$ – Meir Maor Jan 19 at 5:38
  • $\begingroup$ @MeirMaor: in some sense, it is partially true (it does appear to simpler in total than mental poker); on the other hand, by encapsulating some of the complexity in already defined logic (which isn't that much more complicated than standard public key encryption), I would argue that the above description is much simpler... $\endgroup$ – poncho Jan 19 at 19:21

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.