Distributed knowledge problem

Question

I need a way to distribute knowledge among multiple parties - lets start with two. The idea is while the knowledge is originally created by one party I need to transform it into a situation where no party can access the information without the other's help.

I actually have an idea about how to solve this but cryptography is not my strong suit and I would like to ask you if there is a better way to do it.

Scenario

Alice and Bob each have written their favorite movies on cards (one movie per card). I need a way for them to address each card in a way that neither of them knows what movie is on the card.

Edit: It is totally acceptable to know to whom a card belongs. As for being honest about the reveal, that's what my other question was about. Each party would have to pass a commitment token along with the random number.

Proposed Solution

1. Both parties assign random numbers to each of their movies.
2. They write cards with those numbers, shuffle them and hand it to the other party.
3. The other party assigns new random numbers to each of the received numbers.
4. They write cards with those new numbers, shuffle them and place it openly in the middle.

Now if I'm right, neither of them should know which numbered card corresponds to which movie, yet each card uniquely represents one of those movies.

Extension for more parties

• Option A: The cards go through all parties, each assigning a new number. All parties are required to determine the movie.
• Option B: Each party distributes his number cards equally among the other parties but no further iterations is performed. Only two parties are required to determine a movie but not always the same...

Answer 1

There is an obvious problem with your solution; it allows cheating during the reveal.

Here's how it'd work; suppose Alice's favorite movies are Avatar and Titanic. She assigns a random number 19 to Avatar (along with Commit(Avatar)) and 28 (and Commit(Titanic)) to Titanic. She passes them to Bob, who assigns 42 to 19 (which was originally Avatar), and 37 to 28 (which was original Titanic). Note that he can't include Alice's commitments, otherwise Alice would know which card was which. So, Bob publishes 37 and 42 (in some order).

Now, it comes time to reveal 42. We ask Bob what 42 originally stood for; Bob is supposed to answer 19 (and Commit(Avatar)); however, there's nothing stopping him from answering 28 (and Commit(Titanic)); only he knows the mapping, and it's not detectable if he changes his mind.

The obvious solution is to make Bob do commitments as well. That is, Alice sends Commit_A(Avatar) and Commit_A(Titanic) (the random numbers really don't do anything that the commitments themselves don't); Bob then publishes Commit_B(Commit_A(Avatar)) and Commit_B(Commit_A(Titanic)) in some order; when it comes time to reveal a card, we send Commit_B(Commit_A(Avatar)) to Bob, which opens his commitment (and publishes the random number he used, so others can confirm it), and then sends the Commit_A(Avatar) to Alice, which reveals the original Avator (and, again, she publishes her random number so others can again confirm it).

It generalizes in the obvious way if Carol and Dave also want to play. However, one problem with it (and it's really a problem with the problem statement, not the protocol) is that if Dave decides to quit (either because his computer crashed, or if he is just feeling ornery), then we can't reveal any of the cards. A more sophisticated protocol can be designed that will allow any M of the N parties to reveal a card; however, this is going to be a lot more complicated.