Alice and Bob are planning a long car trip and need to come up with a playlist for it. For any given song, they have one of four opinions on it: "That's, like, my favorite song ever" (love), "I like that song" (like), "I'll listen to this, but you owe me" (tolerate), or "I'd rather poke my eardrums out" (hate). To best respect each other's preferences, here's the rules they agreed on for which songs make it onto the playlist:
|Alice \ Bob||Love||Like||Tolerate||Hate|
But here's their dilemma: they're both very self-conscious of their tastes in music. In particular, Alice is worried that Bob will judge her if he finds out that she loves a song he hates, and vice versa. Thus, neither person should learn any more than necessary about the other's opinion of songs that don't get added to the playlist. (For songs that do get added to the playlist, it doesn't matter whether or not they learn each other's exact opinions.) Given a certain song, how can they figure out whether to put it on their playlist, without needing a trusted third party or computer?
Clarifying what can and can't be revealed:
- If Alice hates a song, she must not learn anything at all about Bob's opinion of it.
- If Alice tolerates a song and Bob doesn't love it, she'll learn that he doesn't love it, but she must not learn anything about his opinion of it beyond that.
- If Alice likes a song and Bob either tolerates or hates it, she'll learn that his opinion is one of those two, but she must not learn which.
And ditto swapping Alice and Bob's places. If I didn't say something can't be revealed above, then it can be revealed.
Another clarification: Alice and Bob will both cheat if they can, as long as doing so doesn't prevent the other person from ending up with the correct answer at the end of the protocol.