6
$\begingroup$

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
Love Yes Yes Yes No
Like Yes Yes No No
Tolerate Yes No No No
Hate No No No No

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.

$\endgroup$
6
  • $\begingroup$ Do they only care about the other finding out their opinion if one hates and the other loves? Or would, say, Alice not want Bob to find out she tolerates a song he loves, or she likes a song he hates, etc. $\endgroup$ – bobble Apr 9 at 2:24
  • $\begingroup$ @bobble I edited in some clarification about that. Short version: in cases where the song does go on the playlist, anyone can learn anything. In cases where the song does not go on the playlist, neither person should learn anything other than what's necessarily true due to it not going onto the playlist. $\endgroup$ – Joseph Sible-Reinstate Monica Apr 9 at 2:38
  • $\begingroup$ Can Alice learn that Bob hates a song that she loves? (I didn't see that called out anywhere specifically, sorry if I missed it) $\endgroup$ – bobble Apr 9 at 14:56
  • 1
    $\begingroup$ @bobble If the song she loves doesn't make the final cut, that tells her Bob hates it. So it must be ok for her to learn that $\endgroup$ – StephenTG Apr 9 at 15:54
  • $\begingroup$ That's the reason I'm asking. If she can't find that out, then answers can't stick to using the table-as-given exactly or she would have a chance of finding out. $\endgroup$ – bobble Apr 9 at 16:07
3
$\begingroup$

I have a proposed process, which has the downside of allowing for cheating, but works if both sides want to keep the information transfer within the outlined parameters:

For each song, Alice gets 4 index cards, each with a different one of "Love", "Like", "Tolerate", and "Hate" on them. On the other side of each card, she writes (without Bob looking over her shoulder) whether the song would be included if that card's front side is Bob's opinion (eg if Alice tolerates a song, she'd write "No" on all the cards except "Love"). Alice then leaves the room. Bob looks at the card for each song corresponding to how he feels about the song, and adds the song to the list if it says "Yes" on the back. Bob doesn't look at any card that doesn't match his opinion of the song. Once Bob is done, one of them disposes of the cards without letting him see anything else on them.

This works because:

Alice learns nothing until she sees the final playlist, so she clearly isn't learning extra. Bob, assuming he doesn't cheat, only learns if a song should be on the playlist or not, which is unavoidable anyway.

We can modify this to enforce the secrecy better:

Alice instead places cards/paper with Yes or No inside 4 envelopes per song, with each envelope labelled on one side as above. Instead of leaving when Bob comes to select, Alice simply closes her eyes while Bob shuffles the envelopes and selects the appropriate one (while Alice listens to make sure Bob isn't opening any). Once he's selected it, he holds it such that Alice cannot see the label, then opens it, notes whether it says yes or no, then the process repeats. At the end, Bob disposes of the envelopes while Alice listens to make sure he doesn't open any. This has all the same results of the method above, but Bob can't learn any additional information without Alice catching him cheating.

$\endgroup$
3
  • 1
    $\begingroup$ As I prefaced my answer, this only works if both abide by rules that aren't enforced. From the premise of the question, it seems like they're both primarily concerned with making sure they don't know too much, rather than making sure they don't reveal too much $\endgroup$ – StephenTG Apr 9 at 12:46
  • $\begingroup$ Two things: 1. Rot13(Gur "Ungr" pneq vf haarprffnel, fvapr Obo xabjf vg jbhyq nyjnlf fnl "ab" ba gur onpx). 2. I'd prefer a solution where cheating isn't as easy. Alice and Bob would love to judge each other; they just don't want to be on the receiving end of it. I think this could be modified to be cheat-resistant relatively easy though. $\endgroup$ – Joseph Sible-Reinstate Monica Apr 9 at 13:57
  • $\begingroup$ Even your modified version lets Bob cheat: if he hates a song, he can open one of the other envelopes instead, thus gaining information he shouldn't have. And you can't fix this by making him show Alice the paper, since then she could learn extra information instead, by subtly marking them somehow. $\endgroup$ – Joseph Sible-Reinstate Monica Apr 12 at 19:44
2
$\begingroup$

I've tried to anticipate some nitpicks at the process I present below. Nitpicks are in parentheses and set off from the main method. The core of the method can be found outside the parentheses.

Set-up step:

Alice and Bob should construct some sort of balance. The actual form this balance takes doesn't matter, as long as it's fair and can have a container attached to either end. They'll also need to procure two identical, opaque containers, for that matter. One container (Container A) has a 7g weight placed in it.

(If it's impractical to assume that they have perfect weights, then I hope it's practical to assume that people have objects of identical weight. The method really only needs a mass of 7X - could be 7 batteries, 7 candies, 7 refrigerator magnets, etc.)

Then, they should follow these steps for each potential song:

  1. Alice drops a number of 1g weights into the other container (Container B) corresponding to how much she enjoys the song. Hate = 0g, Tolerate = 2g, Like = 4g, Love = 6g. Bob follows suit. Neither looks inside the container when doing so, and let's say the containers have padded bottoms so you can't hear how many weights there are bopping around in it.

    (If "don't look in the container" is a rule that they can't be expected to follow, say the containers have only a small hole at the top that's just big enough to put in a weight. And the inside is dark enough that you can't see what's inside. This isn't actually that hard to construct; take a smaller cardboard-shipping-box, cover the bottom with cheap foam or a pillow, and cut a little hole in the top. But I digress)

  2. Now, one of them (Alice, say) holds the balance in place so that it can't tip either way. Bob attaches Container A to one side and Container B to the other. Alice releases the balance. If Container A is heavier, then the song doesn't go on the playlist. If Container B is heavier, then the song goes on the playlist.

    (If Bob might be able to guess the weight of Container B when he's transporting it, then let's say we stick an extra 1kg weight in both containers. Telling, say, 1.002kg apart from 1.006kg is much harder than telling 2g apart from 6g. But perhaps the weight of the containers themselves is enough to block this.)

    (To address the comment-nitpick that you can tell the relative masses by watching the balance: Alice and Bob should get a big box. Or create a big box by cutting up smaller boxes and duct-taping the parts together. Or get four pole-supports and a blanket. Then they can block the balance from sight, by placing the box over it or using the supports to cover it with a blanket. They'll do this after the containers are attached. Instead of Alice holding the balance, they rejigger it so it can be held in place with a stick poked in the appropriate area - I can draw a picture, or you can just imagine it. It's possible. Anyhow, they jigger the balance steady with a stick, place the containers on either side, fit the box/blankets over (perhaps they have a small hole for the stick to poke through), and remove the stick. Now they wait a minute or so to make sure the side that would tip has tipped completely, before removing the box/blankets.)

    (Yes this is overkill. But they wanted secrecy!)

  3. Now they repeat. Either they get a fresh Container B, or one dumps the weights out without looking into it or counting the weights as they tumble out.

    (For an actual procedure to prevent peeking, say that my proposed cardboard-shipping-box with foam on the bottom and a small hole on top is used. Say the hole on top has about double the radius of the weights. Simply have Alice watch Bob to ensure no cheaty-looking, and then Bob upturns the box over a container with many, many other weights already. Then the weights will tumble out properly without anyone being able to look or count)

Why does this work?

Let's look at a table of how much mass would be added to Container B for each possibility

| Alice \ Bob |       Love       |       Like       |     Tolerate    |       Hate      |
| ----------- | ---------------- | ---------------- | --------------- | --------------- |
| Love | 12 (> 7 → tip B) | 10 (> 7 → tip B) | 8 (> 7 → tip B) | 6 (< 7 → tip A) |
| Like | 10 (> 7 → tip B) | 8 (> 7 → tip B) | 6 (< 7 → tip A) | 4 (< 7 → tip A) |
| Tolerate | 8 (> 7 → tip B) | 6 (< 7 → tip A) | 4 (< 7 → tip A) | 2 (< 7 → tip A) |
| Hate | 6 (< 7 → tip A) | 4 (< 7 → tip A) | 2 (< 7 → tip A) | 0 (< 7 → tip A) |

Or, in a wordier form:

This method provides no information to either Alice or Bob besides tip A or tip B. Seeing as "tip B" equals "song on playlist" in all cases, and visa versa for A, what they learn is perfectly equivalent to what they would learn from the song being on the playlist, and nothing more.

$\endgroup$
4
  • $\begingroup$ rot13(N jnl gb trg nebhaq "qba'g ybbx ng pbagnvare" vf gb hfr gjb bcndhr pbagnvaref, bar sbe rnpu crefba, naq chg gurz ba gur fnzr fvqr. Jrvtu guvf ntnvafg nabgure gjb vqragvpny pbagnvaref ba gur bgure fvqr gbtrgure jvgu 7t jrvtug.) $\endgroup$ – Tesla Daybreak Apr 10 at 8:01
  • $\begingroup$ This leaks some information: rot13(n onynapr fpnyr jvgu 7 tenzf ba bar fvqr naq 0 ba gur bgure jvyy gvc zber dhvpxyl guna bar jvgu 7 tenzf ba bar fvqr naq 6 ba gur bgure). $\endgroup$ – Joseph Sible-Reinstate Monica Apr 10 at 14:22
  • $\begingroup$ @JosephSible-ReinstateMonica does the edit address your concern? $\endgroup$ – bobble Apr 10 at 15:14
  • $\begingroup$ Yes, it seems to work now. $\endgroup$ – Joseph Sible-Reinstate Monica Apr 10 at 17:25

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.