Love, Money & Poker: the vices of cryptography.
Alice wants to tell Bob she’s madly in love with him. However, she’s afraid of rejection and will only put herself out there if Bob reciprocates the love that she feels for him. To save Alice from the horrible feeling of rejection, we can use multi-party computation in order to calculate if there is a match without revealing any broken hearts.
Our first step to modern romance is to create a magic black box in which Alice and Bob put their input. If they will allow themselves to succumb into love, then the input will be 1. If they are more interested to walk their lives alone (or with someone more suitable), then the input will be 0. Better luck next time!
Alice’s input is either going to be a=0 (as much as Alice loves Bob, she wants to focus on herself first) or a=1 (Alice has her wedding woes ready). Similarly for Bob, b=0 if he is not interested and b=1 if he is ready for this big commitment.
Our black box here does the simple AND operation as demonstrated in the picture. If you are interested in the intricacies of creating such black boxes in real life, you should look into garbled circuits. Beware, the example here is just a simplified demonstration of why secure multi-party computations are needed.
Can you guess which were the inputs of Alice and Bob here?
Another popular multi-party computation example is the Millionaire problem. Imagine two millionaires, Donald Trump and Richard Brandson, trying to measure up their wealth and check who has the fattest stacks of cash without revealing the actual number. Do you still remember the magical black box that acted as the matchmaker for Alice and Bob? Well, if we slightly modify the mysterious algorithms within it, then we can also solve the Millionaire problem.
The final demonstration of multi-party computation problems is Mental poker. Alice, Bob and Carol (our dining cryptographers) are stuck at home in different parts of the world because of the coronavirus outbreak. They are bored twiddling their thumbs and want to exercise their mental power. After some discussion, they decide to play poker over the mail. The question that is asked is the following:
“How can we make sure no player is stacking the deck or peeking at other players’ cards when we are shuffling the deck ourselves?”
Imagine each individual card is locked up in an envelope with 3 locks on it, each lock belonging to a different player. Alice, Bob and Carol have 1 key each and each key opens all 52 corresponding locks on the envelopes.
Let’s say Alice starts off with all the 52 cards securely locked in envelops with all of the players’ keys. She can then pick 5 envelopes and unlock her lock on all of them, then she sends it to Bob. Similarly, she unlocks her locks on 5 other envelopes and sends them to Carol. Finally, she picks 5 envelopes for herself and without unlocking them, she sends them to Carol.
If you catch the drift, Bob will eventually end up with 5 envelopes that are only locked with the key that belongs to him. Alice and Carol will also be left with 5 envelopes each that can be unlocked with the key that belongs to them. Finally, everyone will open their envelopes to get the cards without revealing the contents to anyone else.
The moral of the story is that privacy-preserving computation is your multi-faceted friend that can find you a partner, count your millions and entertain you during the pandemic.
