I couldn’t sleep last night so there’s got to be a better title
Alice and Bob (and maybe even Charlie!) want to find common preferences. However, they’re each ashamed of some of their preferences.
Each are only comfortable with another knowing a preference of theirs if that preference is shared by everyone at the table. They also don’t want gossipy Mallory to run a third-party check for them - this has to be possible without trusting anyone or any program with access to the secret data of others. Assume Alice and Bob may be tempted to try and find each others’ secret preferences.
For example:
-
Alice likes
Anime, Comedy, Fantasy, Romance, Thriller -
Bob likes
Anime, Drama, Horror, Romance, Thriller -
Alice is worried Bob will judge their interest in
AnimeandFantasy -
Bob is scared Alice will judge their interest in
Romance -
But both are fine with the other knowing if they are both interested.
Both will discover a mutual interest in Anime and Romance, but Bob will never deduce Alice’s secret interest in Fantasy.
I am interested in both same-room mechanical solutions (such as overlaying sheets of paper with non-preferences painted out, then shining a light through the stack) and online client-server solutions where the server cannot figure out each answer (such as being given an unlabelled ordered set to compare, where Alice and Bob each have the labels - like return {1,1,0,1,0,1,1} AND {1,0,1,0,1,1,1}).
Couldn’t someone just lie? If Alice hates romance and wants to know if Bob is a filthy romance lover, she could just lie and say she likes romance. No matter what system you implement, Alice will now be told “You and Bob both like romance!”
Yeah, won’t that always be a problem if only 2 people are involved? One person can just indicate all preferences and immediately discover what the other person’s are.
Yes, someone can lie. I wonder how effective any countermeasures may be (e.g. honey tokens to detect someone just saying they love everything), but at the end of the day, I think we are forced to assume all answer truthfully if we want any expectation of secrecy.
Thought the same. Alice could just say she likes everything, and then she learns exactly what Bob likes without revealing anything about herself.
Of course Bob may now believe that Alice likes certain things she doesn’t, but Bob will also notice that it’s a bit too lucky that Alice likes everything that he likes.
Yeah, just like most other things that are not computationally verifiable, this has basically zero Byzantine fault tolerance.
Those are called set and you want to be able to operate on those set secretly. Here is an old paper that could point out to many more stuff
