This crypto bite shows an application of Secure Multiparty Computation (MPC) that is useful in Real Life, called The Game of Like. Is is a physical implementation of MPC using a game of cards.
Secure Dating
Alice and Bob just had their first date, and they are thinking about a second date. Of course, there are four possible outcomes:
- Alice and Bob both want a second date (fantastic!)
- Alice wants a second date, but Bob isn't interested (how could he, this insensitive clod?!)
- Alice isn't interested, but Bob would really like to see her again (Bob's being friendzoned)
- Neither Alice nor Bob are interested in meeting again (well, it wasn't meant to be anyway).
In the first and fourth cases, neither Alice nor Bob would mind learning the answer directly from their friend. But the second and third cases are the ones that are really awkward, because they involve the rejected party losing face and the rejecter feeling guilty.
If only a protocol existed, that somehow blurred the lines by only returning a binary predicate: "second date yes/no", then there would be an escape from this conundrum for Alice and Bob.
Suppose we had case 2.: Alice's feelings will get hurt by Bob's rejection, but she could save face by pretending to Bob (and to anyone else including to herself), that she too wasn't interested, i.e. that case 4. was the reason for no-date... even though it wasn't. Bob could feel less guilty of having hurt Alice's feelings, by pretending that she too wasn't interested, i.e. that case 4. was the second date breaker. Both Alice and Bob genuinely don't know whether case 2. or case 4. was the reason for the second date not going to happen.
Since this scenario is perfectly symmetrical, you can apply the same reasoning on cases 3. and 4. being indistinguishable.
Of course, there exists a trivial protocol, which involves a trusted third party: Alice and Bob could both secretly tell Carol whether they want a second date, and then, Carol will publicly announce the result, i.e. second date yes or no. The big question is: will Carol keep Alice's and Bob's decisions to herself, or is she a gossipy person after all?
Without a trusted third party, Alice and Bob need another solution. This is where secure multiparty computation enters the scene!
What both Alice and Bob want is to collectively compute the predicate:
bool second_date(const bool alices_reply, const bool bobs_reply);without Alice knowing bobs_reply, and without Bob knowing alices_reply. In other words: neither party knows the other party's input to the predicate. Is this at all possible? It may seem weird, but it is! If you remember the Diffie-Hellman Key Exchange, both parties could collectively compute a shared key \(g^{ab}\) without knowing the other party's private key \(b\) or \(a\) respectively. We have a similar situation here.
The Game of Like
Alice and Bob thus decide to play the Game of Like, which, if you think about it, amounts to computing the AND predicate (where as usual 0 is "no" and 1 is "yes"):
| Alice | Bob | 2nd Date? |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The Game of Like is a game of cards. The initial textbook solution required five cards[B89] and is the one that Tal Rabin showed in the talk that inspired this crypto bite. There exists a more complicated solution with four cards[MKS12] which was discovered over two decades later. It was thought that four cards was the minimum. Interestingly, students of computer science at Cornell University came up with many other solutions, involving four, three, two, and even just one card. To illustrate, we'll show a couple of solutions from [MWS15].
Important assumption: In all following cases, the game assumes semi-honest players, i.e. that the players may be curious, but that they follow the rules and don't cheat.
The Textbook Five Cards Solution (Bert den Boer)
This is the original Five Cards Trick by Bert den Boer[B89] at EUROCRYPT '89 that started it all.
Both Alice and Bob are given two cards: ♣ and ♥. There is one public card ♥ on the table. They are told to encode their answers 0 and 1 like this:
| Alice | Bob | |
| 0 | ♥, ♣ | ♣, ♥ |
| 1 | ♣, ♥ | ♥, ♣ |
After they've encoded their answer, Alice places her input cards on the table. Next, the public ♥ is added, on the top of Alices cards. Finally, Bob places his cards on top. All cards are placed face down on the table, so that the players can't see what's on them.
Alice and Bob now take turns privatly cycle-shifting the cards (without looking at them, of course). They do so privately, so that the other player doesn't know the cards where cycled. They can cycle the cards as often and in any of both directions as they like so long as the other player doesn't know the amount nor the directions of the cyclic permutations; all that matters is that they don't swap two cards. Those random cyclic permutations are also achieved by what is called cutting the cards.
Finally, all cards are revealed and placed in a circle. If there are three ♥ in a row, i.e.: ♥, ♥, ♥, it is a second date, else it isn't. Indeed, if we imagine the final result arranged in a circle, this is what we get:
| 0 | 0 | ♥, ♣, ♥, ♣, ♥ |
| 0 | 1 | ♥, ♣, ♥, ♥, ♣ |
| 1 | 0 | ♣, ♥, ♥, ♣, ♥ |
| 1 | 1 | ♣, ♥, ♥, ♥, ♣ |
It can be seen that no matter how often we cycle the rows, three consecutive ♥ are only possible if both Alice and Bob encoded 1. Note that in the table above, you need to keep in mind that each cell in the last column "wraps around", i.e. is conceptually arranged in a circular fashion. Instead of, say, ♣, ♥, ♥, ♥, ♣, it could also be any cyclic rotation like, say, ♥, ♣, ♣, ♥, ♥, and there would still be three hearts in a (cyclic) row.
The Four Cards Solution (Mizuki et al.)
This solution is somewhat more involved than the Five Cards Game. It was shown at ASIACRYPT 2012[MKS12]. Please refer to that paper for a description.
Other Solutions by Computer Science Students
As mentioned above, while it took over two decades for cryptologists to improve upon the Five Cards game, turning it into a somewhat complicated Four Cards game, Cornell's students of Computer Science enrolled in "CS4830: Introduction to Cryptography" in 2015 managed to come up with creative improvements with four, three, two, and even one card, as part of an exercise. This is an amazing feat, that warranted a paper[MWS15] at IACR. In the following, we very briefly summarize some of those variations.
A Four Cards Solution (Manvith Narahari)
Encoding:
| Alice | Bob | |
| 0 | ♣, ♥ | ♣, ♥ |
| 1 | ♥, ♣ | ♥, ♣ |
Alice places her two cards face down on the table. Bob then places his two cards face down on top of Alice's cards. The order of the cards on the table is (from bottom, i.e. the table) to the top: Alice's first card, Alice's second card, Bob's first card, Bob's second card.
Now, Bob leaves the room, leaving Alice alone with the cards. If her answer is 1, she does nothing. In the other case, she swaps the two middle cards (of course without looking!). Now, Bob returns.
As in the Five Cards game, Alice and Bob took turns privatly cycle-shifting the deck of cards (i.e. cutting the cards) by a random amount.
Finally, the cards area revealed (e.g. placing them in a circle as before). There will be a second date if and only if no two identical cards are adjacent to each others, i.e. that there are no ♣, ♣ and no ♥, ♥. Indeed:
| inputs | after Bob leaves the room | revealed cards |
| (0, 0) | ♣, ♥, ♣, ♥ | ♣, ♣, ♥, ♥ |
| (0, 1) | ♥, ♣, ♣, ♥ | ♥, ♣, ♣, ♥ |
| (1, 0) | ♣, ♥, ♥, ♣ | ♣, ♥, ♥, ♣ |
| (1, 1) | ♥, ♣, ♥, ♣ | ♥, ♣, ♥, ♣ |
A Three Cards Solution (Susan Zonghui Li)
In this game, there are three identical cards with a vertical arrow ↑ on the front side. One of the three cards is a public card laying on the table with the arrow pointing up: ↑.
Alice and Bob each get one card. Now, they encode 0 by privatly turning the card 180 degrees, so that the arrow points down ↓, and they encode 1 by (secretly) keeping the arrow pointing up ↑. Of course, the other player doesn't know the arrow direction of his/her peer.
Now, both players put their card face down on the table. The public card is also added face down to the deck. This is how it looks like, if we peeked at the cards, which the players aren't allowed to do, of course:
| inputs | public card | Alice's card | Bob's card |
| (0, 0) | ↑ | ↓ | ↓ |
| (0, 1) | ↑ | ↓ | ↑ |
| (1, 0) | ↑ | ↑ | ↓ |
| (1, 1) | ↑ | ↑ | ↑ |
By now, you've probably guessed how the game is played. Each player will privatly and randomly cycle-shift (shuffle) the whole deck, of course without swapping cards nor turning them upside down. Then, each player privatly and randomly flips the whole deck (i.e. turning it 180 degrees upside down, so that the direction of all arrows gets reversed) 0 or 1 time, so that the whole deck of cards is either flipped upside-down, or not flipped at all (but in both cases cyclicly shuffled by a random amount unknown to both players).
Finally all cards are revealed. There will be a second date, if and only if all three arrows point in the same direction, i.e. either ↑, ↑, ↑ or ↓, ↓, ↓.
A Two Cards Solution (Manvith Narahari)
Here's again a solution by Manvith Narahari for the Two Cards game. We have two cards, each with an arrow pointing down ↓. Both card are placed face down on the table.
Bob leaves the room. If Alice's answer is 0, she does nothing. Otherwise, she flips the second card (without looking!), reverting the arrow's direction from↓ to ↑. Then she leaves the room and Bob is back. If his answer is 0, he does nothing, otherwise, he swaps both cards (without looking!), i.e. he puts the top card below the bottom card, but he doesn't flip the card(s).
Finally, when Alice is back, one of the players reveals only the first (top) card. If and only if the arrow points up ↑, there will be a second date. Indeed (in the following table, the card at the top of the deck is the left arrow):
| inputs | initial deck | after Alice's move | after Bob's move |
| (0, 0) | ↓↓ | ↓↓ | ↓↓ |
| (0, 1) | ↓↓ | ↓↓ | ↓↓ |
| (1, 0) | ↓↓ | ↓↑ | ↓↑ |
| (1, 1) | ↓↓ | ↓↑ | ↑↓ |
A One Card Solution (Peter Mocarski)
Here, there is only one square card with an arrow. The arrow could point up ↑, down ↓, left ←, or right →. We'll place it arrow up ↑ face down on the table.
Bob leaves the room. If Alice's answer is 0, she does nothing. Otherwise, she rotates the card (without looking!) 90 degrees clockwise. The she leaves the room, and Bob comes back. If Bob's answer is 0, he too does nothing. Otherwise, he rotates the card (again without looking) 90 degrees clockwise. You've noticed that here, both players follow the same protocol!
Finally, only the bottom portion of the card is folded up, and revealed to the players. There will be a second date, it and only if an arrow tip shows there (i.e. if the arrow points down ↓). Indeed:
| inputs | initial position | after Alice's move | after Bob's move |
| (0, 0) | ↑ | ↑ | ↑ |
| (0, 1) | ↑ | ↑ | → |
| (1, 0) | ↑ | → | → |
| (1, 1) | ↑ | → | ↓ |
The Bigger Picture
The Game of Like is a physical implementation and an example of Secure Multiparty Computation (MPC). Recall that in MPC, multiple parties \(P_1, P_2, \dots, P_n\) want to collectively compute a function \(y := f(x_1, x_2, \dots, x_n)\), where the input \(x_i\) is only known by \(P_i\) for all \(i \in \{1, 2, \dots, n\}\). In other words, each party \(P_i\) is oblivious to the other parties' inputs \(P_j \colon j \ne i\).
In the Game of Like, the function \(f\) happens to be the Boolean AND: \(y := f(x_1, x_2) := x_1 \wedge x_2\). The parties are \(P_1 = \) Alice and \(P_2 = \) Bob, and the requirement is that Alice doesn't know Bob's decision \(x_2\) and Bob doesn't know Alice's decision \(x_1\). Yet, both Alice and Bob will at the end of the computation know \(y\), the Boolean result, where true means that both agree to a second date, and false means that there won't be a second date.
It is worth stressing that at no point during the computation, including at its end, one party's input was revealed to the other party. This is a necessary condition for MPC.
In the next crypto bite, we'll see how to MPC compute \(f\), where \(f\) is the sum of its inputs.
If you jumped directly to this page, you may want to learn more about Secure Multiparty Computation.
Source
The Game of Like with Five Cards was used as a lecture opener showing a real world application of Secure Multiparty Computation (MPC) by IBM's Tal Rabin at Technion Computer Engineering 2014 summer school. Part 1, up to 07:20.
Literature
- [B89] Bert den Boer: More Efficient Match-Making and Satisfiability. The Five Card Trick. In: Lecture Notes in Computer Science LNCS 434, Advances in Cryptology, EUROCRYPT89., pp 208-217. (springer.com, full pdf)
- [MKS12] Takaaki Mizuki, Michihito Kumamoto, Hideaki Sone: The Five-Card Trick Can Be Done with Four Cards. In: Lecture Notes in Computer Science LNCS 7658, Advances in Cryptology, ASIACRYPT2012., pp 598-606. (full pdf via iacr.org)
- [MWS15] Antonio Marcedone, Zikai Wen, Elaine Shi: Secure Dating with Four or Fewer Cards (A Short Note on Teaching Cryptography). (iacr.org, full pdf)
